After being unable to solve the daily Wordle, Jamie is teased by a few of his close friends. Not taking this lying down, he decides to challenge them to a Wordle duel. In this duel, each party will select a custom ~5~-letter word for the other party to guess. To maximize his chance of winning, Jamie should choose a difficult to guess word. He's compiled a list of possible candidates, but can you help him find the hardest word to guess?

The difficulty of a word depends on ~2~ parameters. The first is the types of characters in the word — a word with the character x, for example, may be harder to guess than a word with the letter e. The second parameter is the number of repeated characters. Words with fewer unique characters are harder to guess.

We define difficulty of a word to guess as:

$$\displaystyle \sum_{i=0}^{4} d_i \times (6 - u) $$

where ~d_i~ is the difficulty of the ~i~th character in the word and ~u~ is the number of unique characters of word.

If two words have the same difficulty value, the lexicographically smaller word is the harder of the two.

Can you help Jamie find the hardest word to guess from his candidate list?

Input

The first line consists of ~26~ integers ~d_i~ ~(1 \leq d_i \leq 10^5)~, the difficulty score of the characters. That is, the first integer corresponds to the difficulty of the letter a, the second corresponds to the difficulty of b, and so on.

The next line consists of an integer ~n~ ~(1 \leq n \leq 500)~, the number of words in Jamie's candidate list.

The next ~n~ lines consist of ~5~-letter words consisting of lowercase alphabetical characters.

Output

Print the hardest word to guess from the list of candidates.

Example

Input 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
aucpl
level

Output 1

level

aucpl has a difficulty score of ~5~.

level has a difficulty score of ~15~.