A certain gentleman shamelessly ate another gentleman’s cake. This inexcusable act led to a long merciless battle between them. Of course, proper gentlemen never fight with their fists – they use carefully chosen insults built of words from Shakespeare’s time. This is how the battle went on:
“Thou atest my cake, thou bawdy doghearted nut-hook!”
“Aye? But thou art a goatish half-faced bugbear.”
“Fain I am not a goatish doghearted puttock as thou.”
“Thou art a bawdy half-faced nut-hook.”
“Thou bawdy doghearted bladder!”
“Thou goatish half-faced puttock!”
“Thou spongy boil-brained bladder!”
“Thou bawdy boil-brained bugbear!”
“Fie, thou winnest!”
A valid insult consists of three words: The first one must be a simple insulting adjective, the second one must be a compound insulting adjective, and the third one must be an insulting noun. For each of these categories we give you a list of available words. Every word has a certain strength; the strength of an insult is the sum of the strengths of its three words.
You are then given a list of insults. For each one of them you have to come up with an appropriate response – an insult which is by 1 unit stronger than the challenging insult. You are not allowed to use the same response more than once.
The input consists of four parts. The first three parts describe the three wordlists that the insults are built from. They have the same structure: The first line contains an integer m denoting the number of words in the wordlist. Then m lines follow; on each line there is a word and its strength (a positive integer). Words consist of lowercase English letters and at most one hyphen (-). Each word is between 1 and 15 characters long (inclusive). The words in all three wordlists are distinct.
The last part of the input describes a list of insults. On the first line there is an integer n denoting the number of insults. On each of the following n lines there are three space-separated words. You are guaranteed that the insults are valid with respect to the former wordlists.
In the easy subproblem B1 we have m = 50 and n = 500. Maximum word strength is 103.
In the hard subproblem B2 we have m = 10 000 and n = 10 000. Maximum word strength is 106.
Output n lines. For each i, the i-th line should contain an insult whose strength is exactly one greater than the strength of the i-th insult in the input. You cannot use the same insult more than once. (I.e., your output must contain n distinct lines.)
You are guaranteed that there is a sufficient amount of appropriate insults.
Input:
3
bawdy 6
goatish 4
spongy 1
3
boil-brained 10
half-faced 6
doghearted 3
3
bladder 7
bugbear 3
puttock 7
7
spongy boil-brained bladder
goatish half-faced bugbear
bawdy half-faced bugbear
spongy doghearted puttock
goatish half-faced bugbear
goatish half-faced bugbear
bawdy doghearted bladderOutput:
bawdy boil-brained bugbear
goatish doghearted bladder
bawdy doghearted puttock
bawdy doghearted bugbear
spongy half-faced puttock
spongy boil-brained bugbear
goatish half-faced bladderThe strengths of the input insults are 18, 13, 15, 11, 13, 13, and 16.
The strengths of the output insults are 19, 14, 16, 12, 14, 14, and 17. Note that we had to use three different insults with strength 14 each.
The conversation in the beginning of this task contains a sequence of valid insults if we consider the wordlists from this sample input and an additional insulting noun ‘nut-hook’ of strength 3. Each insult is an appropriate response to the previous one. There is no valid response to the last insult of strength 19.