Bob is trying to solve a crossword puzzle, but he doesn't have the patience to do it. So naturally, he wants you to write a program to help him.

Bob has compiled a list of ~N~ distinct valid words and ~M~ unordered pairs of synonyms from that list. The distance between words ~x~ and ~y~ is the length of the shortest sequence of words ~w_1, w_2, \dots, w_k~ such that ~w_1 = x~, ~w_k = y~, and ~w_i~ and ~w_{i + 1}~ are synonyms for all ~1 \le i < k~. If no such sequence exists, the words are unrelated; otherwise, they are related.

In the puzzle, Bob is given ~Q~ clues of the form a b, where a is a valid word and b is an uppercase English letter. The answer to each clue is the word that has the shortest distance from a, of all the valid words starting with b that are related to a. If none of the words starting with b are related to a, there is no answer. If multiple answers are possible, the correct one is the lexicographically lowest of them.

Please help Bob solve the puzzle!

Constraints

Subtask 1 [25%]

~2 \le N \le 300~
~1 \le M \le 500~
~1 \le Q \le 300~

Subtask 2 [25%]

~2 \le N \le 2\,000~
~1 \le M \le 5\,000~
~1 \le Q \le 2\,000~

Subtask 3 [50%]

~2 \le N \le 100\,000~
~1 \le M \le 200\,000~
~1 \le Q \le 100\,000~

Input Specification

The first line contains three space-separated integers, ~N~, ~M~, and ~Q~.
The next ~N~ lines each contain one string consisting of no more than ~10~ uppercase English letters, the ~i~-th valid word.
The next ~M~ lines each contain two distinct space-separated strings, a pair of synonyms. Each pair appears at most once.
The final ~Q~ lines each contain one valid word followed by one uppercase English letter, the ~i~-th clue.

Output Specification

~Q~ lines. The ~i~-th line should contain one valid word—the answer to the ~i~-th clue—or -1 if there is no answer. If there are multiple valid answers, output the lexicographically lowest one.

Sample Input

6 4 4
AA
AB
AC
CCC
BBB
EA
AA CCC
AB BBB
AC CCC
CCC BBB
BBB A
BBB B
CCC A
BBB E

Sample Output

AB
BBB
AA
-1

---