Sannvirði

Dröfn Karen은 텔레비전 편성표에 새로 등장한 퀴즈 쇼 Sannvirði를 무척 좋아한다. 그녀가 가장 좋아하는 것은 우승자가 상품을 받았을 때 얼마나 기뻐하는지 보는 것이다. 그녀는 매회 방송을 손꼽아 기다린다.

각 방송은 퀴즈 쇼 진행자가 냉장고, 자동차, 당근, 향수 한 병 등 판매되는 물건 하나를 보여 주면서 시작한다. 모든 참가자는 같은 시간 동안 그 물건을 볼 수 있다. 그런 다음 참가자들은 그 물건의 실제 가치가 얼마인지 추측해야 한다. 정답을 넘지 않으면서 정답에 가장 가까운 값을 추측한 참가자가 우승한다. 참가자들은 동시에 추측하며 다른 참가자들의 추측을 볼 수 없다. 하지만 Dröfn과 같은 시청자들은 모든 정보를 받는다. 방송에서는 각 참가자가 자신의 추측을 설명하는 매우 짧은 인터뷰를 보여 준다.

물론 광고 없는 텔레비전 방송은 있을 수 없다. 우승자를 발표하기 전에 방송은 광고 시간으로 넘어간다. Dröfn은 흥분으로 몸을 떨고 있다. 그녀에게는 물건의 실제 가치에 대한 몇 가지 생각이 있으며, 자신의 생각 중 어느 하나가 정답이라면 어떤 참가자가 우승할지 궁금해한다.

Dröfn의 각 생각에 대한 우승자를 찾을 수 있는가?

채점

그룹 | 점수 | 제한

1 | 10 | $n = 1$, $q = 1$

2 | 15 | $n = 1$, $1 \leq q \leq 1\,000$

3 | 20 | $1 \leq n \leq 1\,000$, $q = 1$

4 | 25 | $1 \leq n \leq 1\,000$, $1 \leq q \leq 1\,000$

5 | 30 | $1 \leq n \leq 200\,000$, $1 \leq q \leq 200\,000$

첫째 줄에는 참가자 수를 나타내는 정수 하나 $n$이 주어진다.

이어서 각 참가자를 설명하는 $n$개의 줄이 주어진다. 참가자에 대한 설명은 공백으로 구분된 이름과 추측값으로 이루어진다. 각 이름은 적어도 $1$개, 최대 $10$개의 영문 소문자로 이루어진다. 각 추측값은 양 끝을 포함하여 $0$ 이상 $10^9$ 이하인 정수이다. 서로 다른 두 참가자가 같은 값을 추측하지 않았다고 가정해도 된다.

이어서 생각의 개수를 나타내는 정수 하나 $q$이 주어진 줄이 나온다.

마지막으로 Dröfn의 생각 하나를 각각 설명하는 $q$개의 줄이 주어진다. 각 생각은 양 끝을 포함하여 $0$ 이상 $10^9$ 이하인 정수이다.

각 생각에 대해 입력에 등장한 순서대로, 그 생각이 정답일 경우 우승하는 참가자의 이름을 출력한다. 해당 생각에 대해 우승하는 참가자가 없다면 :(을 출력해야 한다. 아무도 우승하지 못하면 Dröfn이 슬퍼할 것이기 때문이다.