시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 7 2 2 28.571%

문제

In the game of Scrabble you are given a number of tiles with letters on them. The challenge is to create a word using some (or all) of these tiles. Write a program which, with the help of a dictionary, determines the longest word you can make with the given letters. Those of you who know this game may note that we ignore the board upon which the letters are placed, as well as the value of the letters.

입력

The input file consists of:

  • one line with an integer n (1 ≤ n ≤ 100 000): the number of words in the dictionary.
  • n distinct lines, each with one word consisting of between 2 and 10 lower-case letters.
  • one line with an integer c (1 ≤ c ≤ 10 000): the number of test cases.
  • c lines, each with a string consisting of between 2 and 10 lower-case letters: the letters you have to make a word with.

The words in the dictionary are given in alphabetical order.

출력

Per test case:

  • one line with the longest word from the dictionary you can make with the given letters. If there are multiple words, give the first one in alphabetical order. If there are no words you can make, output the word ”IMPOSSIBLE”.

예제 입력

6
algorithm
balloon
bapc
code
submit
utrecht
5
abcdeop
abcdeoq
chuttep
chutter
iamhotgirl

예제 출력

bapc
code
IMPOSSIBLE
utrecht
algorithm

힌트