Word Translation Lookup

You are given a very long list of direct word-to-word translations between languages. Each entry has the form: word $S_1$ in language $A$ corresponds to word $S_2$ in language $B$.

Write a program that answers queries of the form: find every translation of word $S$ from language $A$ into language $B$.

The translation relation is transitive: word $S_2$ in language $B$ is a translation of word $S_1$ in language $A$ whenever there is a chain of (word, language) pairs, each two adjacent pairs being direct translations of each other, that leads from $(S_1, A)$ to $(S_2, B)$.

Formally, there must exist a sequence of (word, language) pairs $(X_i, J_i)$ such that $(S_1, A)$ is a direct translation of $(X_1, J_1)$, $(X_1, J_1)$ is a direct translation of $(X_2, J_2)$, $\dots$, and $(X_k, J_k)$ is a direct translation of $(S_2, B)$.

The direct-translation relation is symmetric: each entry in the list means the two words are translations of each other.

The first line contains the number of test sets $Z$ ($1 \le Z \le 10$).

Each test set is given as follows.

• The first line contains $N$, the number of direct translations ($1 \le N \le 40000$).
• Each of the next $N$ lines contains four words $S_1$, $A$, $S_2$, $B$, meaning word $S_1$ in language $A$ and word $S_2$ in language $B$ are direct translations of each other.
• The next line contains $M$, the number of queries ($1 \le M \le 10000$).
• Each of the next $M$ lines contains a query of three words $S$, $A$, $B$.

Every word in the input has length at most $20$ and consists only of lowercase English letters ($a$-$z$). Words on a line are separated by a single space.

For each query $(S, A, B)$, print one line.

• Print ? if no translation of word $S$ into language $B$ can be inferred.
• Otherwise print all translations of word $S$ into language $B$ in lexicographic order, separated by commas and no spaces.

Because every word is trivially connected to itself, when $A = B$ the queried word $S$ is itself included in the answer.

You may assume the total amount of data you need to print does not exceed $20\,\text{MB}$.