검색어 추천

호텔 예약 사이트에 도시 이름 추천 기능을 넣으려고 한다. 손님이 도시 이름의 앞부분을 입력하면, 그 문자열로 시작하는 도시 가운데 인기 점수가 높은 세 곳을 보여 준다.

이 사이트는 하루에 수백만 건의 검색을 처리하므로 서버 부담을 줄이려고 제한을 하나 두었다. 입력한 문자열로 시작하는 도시 이름이 1,000개 이하일 때만 추천 목록을 만들고, 1,000개보다 많이 일치하면 목록 대신 일치한 개수를 알려 준다.

이 추천 기능을 구현하시오.

입력의 앞부분은 도시 데이터다. 첫째 줄에 도시의 수 $N$이 주어진다. ($1 \le N \le 500{,}000$)

다음 $N$개의 줄에는 도시 이름과 인기 점수 $S$가 쉼표 하나로 구분되어 이름,S 형태로 주어진다. ($1 \le S \le 100$) 도시 이름에 쉼표는 들어가지 않는다. 도시 데이터는 도시 이름의 오름차순으로 정렬되어 있다.

입력의 뒷부분은 질의 데이터다. 도시 데이터 다음 줄에 질의의 수 $Q$가 주어지고 ($1 \le Q \le 300{,}000$), 이어지는 $Q$개의 줄에 질의 문자열이 한 줄에 하나씩 주어진다.

각 질의마다 먼저 질의를 그대로 한 줄에 출력하고, 이어서 결과를 출력한다. 결과는 세 가지 가운데 하나다.

1. 질의로 시작하는 도시 이름이 1,000개 이하이면 그 도시를 최대 세 개까지 이름,점수 형태로 한 줄에 하나씩 출력한다. 인기 점수가 높은 순서로 출력하고, 점수가 같으면 도시 이름의 오름차순으로 출력한다.
2. 질의로 시작하는 도시 이름이 1,000개보다 많으면 일치하는 도시의 개수만 출력한다. 다른 글자나 소수점은 붙이지 않는다.
3. 질의로 시작하는 도시 이름이 하나도 없으면 N/A를 출력한다.

도시 이름은 입력에 있는 대소문자 그대로 출력한다.

대소문자는 구분하지 않는다. 질의와 도시 이름을 비교할 때도, 점수가 같은 도시를 이름 순으로 정렬할 때도 마찬가지다.