전령들

아주 먼 옛날, 어느 왕국에 $N$명의 상인이 살고 있었다. 그들이 하던 일은 오늘날의 상인과 다르지 않았다. 물건을 최대한 싸게 사서 최대한 비싸게 파는 것이다. 다만 거래에 쓰는 도구는 지금과 달랐다. 상인들 사이의 모든 연락은 전령을 통해 이루어졌다.

전령은 상인들 사이로 편지를 나른다. 각 편지는 정확히 한 상인(발신자)이 다른 한 상인(수신자)에게 보내는 것이다. 상황, 날씨, 전령의 기분과 체력에 따라 편지가 전달되는 데는 잠깐, 조금 더 긴 시간, 또는 아주 오랜 시간이 걸릴 수 있다. 모든 상인은 자신의 서신을 일지에 기록한다. 편지를 보내면 보낸 즉시, 편지를 받으면 받은 즉시 그 사실을 시간 순서대로 적어 둔다. 따라서 각 일지는 사건들의 수열이며, 각 사건은 다음 두 가지 형태 중 하나이다.

• 보냄($w$): 어떤 편지 $w$를 보냈다.
• 받음($w$): 어떤 편지 $w$를 받았다.

정밀한 시계가 없었기에 상인들은 각 사건이 일어난 시각은 적지 않았다.

수상한 거래가 여러 차례 이어지자, 왕의 감사관들은 일부 상인이 밀거래, 첩보, 사기, 투기를 벌인다고 의심하기 시작했다. 왕은 시장에서 벌어진 사건들의 인과 순서를 밝히기 위해 상인들의 서신을 대대적으로 조사하라고 명령했다.

모든 상인의 일지 내용이 주어질 때, 임의의 두 편지에 대해 어느 쪽이 먼저 보내졌는지 판별하는 프로그램을 작성할 수 있는가? 편지 $a$가 편지 $b$보다 먼저 보내졌다는 것은, 사건들(즉 일지의 기록들)의 수열 $x_1, x_2, \ldots, x_k$가 존재하여 다음을 만족한다는 뜻이다.

• $x_1 = \text{보냄}(a)$
• $x_k = \text{보냄}(b)$
• 이웃한 두 사건 $x_i, x_{i+1}$마다 다음 중 적어도 하나가 성립한다.
  • $x_i$와 $x_{i+1}$이 같은 상인의 일지에서 연속한 두 사건이다. (그러므로 $x_i$가 $x_{i+1}$보다 먼저 일어났다.)
  • 어떤 편지 $w$에 대해 $x_i = \text{보냄}(w)$이고 $x_{i+1} = \text{받음}(w)$이다. 즉 $x_{i+1}$은 $x_i$에서 보낸 편지를 받는 사건이다. (그러므로 $x_i$가 $x_{i+1}$보다 먼저 일어났다.)

첫 줄에 테스트 집합의 개수를 나타내는 자연수 $Z$ ($1 \le Z \le 1$)가 주어진다. 이어서 각 집합이 차례로 주어진다. (테스트 집합은 항상 정확히 하나이다.)

각 테스트 집합의 첫 줄에는 공백으로 구분된 두 자연수 $N$과 $K$ ($1 \le N \le 100$; $1 \le K \le 100000$)가 주어진다. 각각 상인의 수와 질의의 수이다. 이어지는 $N$개의 줄에는 상인들의 일지가 하나씩 주어진다.

하나의 일지는 그 일지에 기록된 사건의 개수를 나타내는 자연수 $S_i$로 시작하고, 그 뒤에 $S_i$개의 정수 $w_1, w_2, \ldots, w_{S_i}$가 공백으로 구분되어 온다. $w_i$가 양수이면 식별자 $w_i$인 편지를 보냈다는 뜻이고, 음수이면 식별자 $|w_i|$인 편지를 받았다는 뜻이다. 각 편지의 식별자는 유일하며 $1$ 이상 $C$ 이하이다. 여기서 $C$는 상인들이 주고받은 편지의 총 개수이다. 편지의 식별자는 보낸 순서를 나타내지 않으며 단지 이름표일 뿐이다. $C$는 입력에 직접 주어지지 않지만 $1 \le C \le 100000$임이 보장된다.

이어지는 $K$개의 줄에는 질의가 하나씩 주어진다. 각 질의는 서로 다른 두 편지의 식별자를 공백 하나로 구분한 것이다.

입력이 모순되지 않음이 보장된다. 즉 어떤 두 편지 $a, b$에 대해서도 $a$가 $b$보다 먼저 보내졌다는 것과 $b$가 $a$보다 먼저 보내졌다는 것이 동시에 추론되는 일은 없다.

테스트 집합에 대해 질의가 주어진 순서대로 정확히 $K$개의 줄을 출력한다. 각 질의에 대해 먼저 보내진 편지의 식별자를 출력하고, 일지만으로는 어느 편지가 먼저 보내졌는지 정할 수 없으면 물음표 ? 하나를 출력한다.

위 그림은 상인들의 일지와 그 사이를 오가는 편지가 사건들의 선후 관계를 어떻게 정하는지 나타낸다.