Italian brainrot

Who would win if Tung Tung Tung Tung Tung Tung Tung Tung Tung Sahur fought Tralalero Tralala? After watching Instagram Reels all day, Donghyun decided to write a program that determines which Italian brainrot character wins in fights.

You may freely decide which character wins in a fight between two characters. However, your imagination must satisfy the following condition.

For any three distinct characters $A$, $B$, and $C$, if character $B$ wins against character $A$, and character $C$ wins against character $B$, then character $C$ must win against character $A$.

You are given the names of $N$ Italian brainrot characters and $Q$ queries. For each query, print which character wins.

All answers must come from one fixed valid imagination. If there are multiple valid answers, you may print any one of them. If the same character is given twice in a query, that character wins.

The input is given in the following format.

$N\ Q$
$S_1$
$S_2$
$\vdots$
$S_N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_Q\ B_Q$

$S_i$ is the name of the $i$-th character. $A_i$ and $B_i$ are the two character names in the $i$-th query.

Print $Q$ lines.

On the $i$-th line, print the name of the character that wins in the $i$-th query. All printed answers must be consistent with one fixed valid imagination.

• $1 \le N, Q \le 1\,000$.
• Every character name is a nonempty string consisting only of lowercase English letters.
• All character names are distinct.
• The sum of the lengths of all character names does not exceed $10\,000$.
• Every name appearing in a query is one of the given character names.