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 2000$
$1\le M\le 5000$
$1\le Q\le 2000$

Subtask 3 [50%]

$2\le N\le 100000$
$1\le M\le 200000$
$1\le Q\le 100000$

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