어느 아이돌 서바이벌 오디션 프로그램에서 매치별 투표 결과를 기록합니다. 중간 점검을 위해 '가장 많은 표를 획득한 1등 참가자'와 '가장 적은 표를 획득한 탈락 위기 참가자'의 표 차이를 매번 실시간으로 추적하려고 합니다.

매치마다 참가자들의 이름과 추가로 획득한 득표수가 실시간 로그로 들어올 때, 매치가 끝난 시점마다 현재 누적 전체 1등과 최하위의 점수 차이를 계산하여 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 서바이벌에 참여한 총 참가자 수 K가 주어진다. 둘째 줄에 K명 참가자들의 이름이 공백으로 구분되어 주어진다. (초기 모든 참가자의 누적 점수는 0점이다.) 셋째 줄에 실시간 투표 기록 로그의 개수 M이 주어진다. 넷째 줄부터 M개의 줄에 걸쳐 투표 결과 로그가 참가자이름 득표수 형태로 한 줄에 하나씩 순서대로 주어진다.

참가자 이름은 알파벳 대소문자가 구분되는 10자 이하의 문자열이다. 매 로그마다 주어지는 득표수는 1 이상 10,000 이하의 자연수이다.

출력

투표 로그가 한 줄씩 들어와 처리될 때마다, 해당 시점의 (현재 누적 1등의 점수) - (현재 누적 최하위의 점수)를 한 줄씩 계산하여 총 M개의 줄을 출력한다.

제약 조건

• 2 ≤ K ≤ 50
• 1 ≤ M ≤ 1,000
• 1 ≤ 득표수 ≤ 10,000

예제 입력

3
Amy Ben Choi
4
Amy 100
Ben 150
Choi 80
Amy 90

예제 출력

100
150
70
110