34075번 - 세그먼트 트리보다도 바・로・너・♡

문제

초코민트보다도 바・로・너・♡

— 쿠로사와 루비, AiScReam

채강은 솔브드 학교의 스쿨 아이돌 그룹 PRODUCE $\mathbf{{10}^1}$의 열렬한 팬이다. 채강은 여기에 너무 과몰입한 나머지, 멤버들이 선호하는 모든 취향을 따르기로 결심했다. 가장 먼저 할 것은 좋아하는 알고리즘을 따라하는 것이다.

솔브드 학교에서 배울 수 있는 알고리즘의 종류는 총 $N$가지로, $i$번째 알고리즘의 난이도는 정수 $D_i$로 나타낼 수 있다. 모든 알고리즘의 이름은 서로 다르다.

PRODUCE $\mathbf{{10}^1}$에는 총 $M$명의 멤버들이 있다. $i$번째 멤버의 티어 $T_i$는 그 멤버의 알고리즘 실력을 나타내는 정수이다. 모든 멤버들의 이름은 서로 다르다.

각 멤버는 알고리즘의 난이도가 자신의 티어에 가까울수록 더 좋아한다. 즉, 어떤 알고리즘의 난이도가 $d$라면, $i$번째 멤버는 $\left| d - T_i \right|$가 작은 알고리즘일수록 더 좋아한다. 만약 $\left| d - T_i \right|$의 값이 같다면, 이름이 사전 순으로 먼저 오는 알고리즘을 더 좋아한다. 사전 순의 정의는 노트를 참고하라.

채강은 각 멤버에게 좋아하는 알고리즘을 다음과 같은 쿼리의 형태로 물어보려고 한다.

1. $\color{#e74c3c}{\text{name},円}$- chan!: PRODUCE $\mathbf{{10}^1}$ 소속 멤버의 이름인 $\color{#e74c3c}{\text{name}}$을 불러 이번에 대답할 멤버를 $\color{#e74c3c}{\text{name}}$으로 설정한다. 그 멤버는 hai!를 대답한다.
2. nani ga suki?: 가장 최근에 대답한 멤버가 가장 좋아하는 알고리즘의 이름을 $\color{#e74c3c}{\text{algo}_1},ドル 두 번째로 좋아하는 알고리즘의 이름을 $\color{#e74c3c}{\text{algo}_2}$라고 하자. 그 멤버는 $\color{#e74c3c}{\text{algo}_2,円}$yori mo$\color{#e74c3c}{,円\text{algo}_1}$을 대답한다.

위 쿼리를 수행하는 프로그램을 작성해 보자.

입력

첫 번째 줄에 알고리즘의 개수 $N$이 주어진다. (2ドル\leq N\leq 229$)

다음 $N$개의 줄에 걸쳐, 각 알고리즘의 이름과 난이도가 공백으로 구분되어 주어진다. 알고리즘의 이름은 알파벳 소문자와 언더스코어(_)로만 이루어져 있다. 알고리즘의 이름의 길이는 1ドル$ 이상 50ドル$ 이하이며, 난이도는 1ドル$ 이상 30ドル$ 이하의 정수이다.

그 다음 줄에 멤버의 수 $M$이 주어진다. (1ドル\leq M\leq 10$)

다음 $M$개의 줄에 걸쳐, 각 멤버의 이름과 티어가 공백으로 구분되어 주어진다. 멤버의 이름은 알파벳 소문자로만 이루어져 있다. 멤버 이름의 길이는 1ドル$ 이상 20ドル$ 이하이며, 티어는 0ドル$ 이상 31ドル$ 이하의 정수이다.

그 다음 줄에 쿼리의 수 $Q$가 주어진다. (1ドル\leq Q\leq 101$)

다음 $Q$개의 줄에 걸쳐, 쿼리가 한 줄에 하나씩 주어진다. 첫 번째 쿼리는 항상 1ドル$번 쿼리이다.

출력

각 쿼리에 대해 멤버가 대답한 내용을 한 줄에 하나씩 출력한다.

제한

노트

사전 순으로 먼저 온다는 것은 다음을 의미한다.

1. 두 문자열을 앞 글자부터 차례대로 비교하여 처음으로 다른 글자가 나타났을 때, 그 글자의 아스키 코드가 작은 쪽이 사전 순으로 먼저 온다. 즉, 언더스코어(_)가 알파벳 소문자보다 앞선다.
2. 만약 한 문자열이 다른 문자열의 접두사라면, 더 짧은 문자열이 사전 순으로 먼저 온다.