Messengers

Long ago, in a certain kingdom, there lived $N$ merchants. They did back then what merchants still do today: buy goods as cheaply as possible and sell them as dearly as possible. The tools of the trade, however, were different. All communication between the merchants was carried out by messengers.

A messenger carries a letter between merchants, and each letter goes from exactly one merchant (the sender) to exactly one other merchant (the recipient). Depending on the circumstances, the weather, and the messenger's mood and stamina, delivering a letter could take a moment, a longer moment, or a very long time. Every merchant records their correspondence in a journal: right after sending a letter, and right after receiving one, they write it down, keeping strict chronological order. Each journal is therefore a sequence of events, and every event has one of two forms.

• sent($w$): some letter $w$ was sent.
• received($w$): some letter $w$ was received.

Because the merchants had no precise clocks, they never wrote down the time at which an event happened.

After a run of suspicious deals, the king's inspectors began to suspect some merchants of smuggling, espionage, fraud, and speculation. To reconstruct the cause-and-effect order of events on the market, the king ordered a sweeping audit of the merchants' correspondence.

Given the contents of every merchant's journal, can you decide, for any two letters, which one was sent earlier? We say that letter $a$ was sent before letter $b$ if there is a sequence of events (that is, journal entries) $x_1, x_2, \ldots, x_k$ such that:

• $x_1 = \text{sent}(a)$
• $x_k = \text{sent}(b)$
• for every pair of adjacent events $x_i, x_{i+1}$, at least one of the following holds:
  • $x_i$ and $x_{i+1}$ are consecutive events in the journal of the same merchant (so $x_i$ must have happened before $x_{i+1}$), or
  • $x_i = \text{sent}(w)$ and $x_{i+1} = \text{received}(w)$ for some letter $w$, i.e. $x_{i+1}$ is the receipt of the letter sent in $x_i$ (so again $x_i$ must have happened before $x_{i+1}$).

The first line contains a natural number $Z$ ($1 \le Z \le 1$), the number of test sets; the sets follow one after another. (There is always exactly one test set.)

The first line of a test set contains two space-separated natural numbers $N$ and $K$ ($1 \le N \le 100$; $1 \le K \le 100000$): the number of merchants and the number of queries. Each of the next $N$ lines describes one merchant's journal.

A journal is given as a single natural number $S_i$ (the number of events recorded in it), followed by $S_i$ space-separated integers $w_1, w_2, \ldots, w_{S_i}$. A positive $w_i$ means sending the letter with identifier $w_i$; a negative $w_i$ means receiving the letter with identifier $|w_i|$. Every letter identifier is unique and lies between $1$ and $C$, where $C$ is the total number of letters exchanged. Letter identifiers do not reflect the order in which letters were sent; they are only labels. $C$ is not given explicitly, but it is guaranteed that $1 \le C \le 100000$.

Each of the next $K$ lines contains one query: two distinct letter identifiers separated by a single space.

It is guaranteed that the input is never contradictory, i.e. there is no pair of letters $a, b$ for which one could infer both that $a$ was sent before $b$ and that $b$ was sent before $a$.

For the test set, print exactly $K$ lines, one per query in the given order. For each query, print the identifier of the letter that was sent first, or a single question mark ? if the journals do not determine which of the two was sent earlier.

The figure above shows how the merchants' journals and the letters passing between them determine the happens-before order of events.