9034번 - 순위

프로 게이머 협회는 등록된 N 명의 선수들에 대한 순위를 유지한다. 선수들의 순위는 게임을 치를 때마다 얻는 점수에 의해 결정된다. 점수를 누적한 값은 랭킹 포인트가 되고, 랭킹 포인트가 높을수록 순위도 높다. 가장 높은 랭킹 포인트를 가진 선수(들)은 순위가 1 이다. 나머지 선수의 순위는 자신보다 한 단계 높은 랭킹 포인트를 가진 선수(들)의 순위에다 해당 선수들의 수를 더한 값이다. 선수들을 1 부터 N 까지의 번호로 구분하자. 예를 들어, N=5 명의 현재 랭킹 포인트가 1 번 선수부터 차례대로 (10, 15, 20, 8, 12) 라고 하면, 선수들의 순위는 차례대로 (4, 2, 1, 5, 3) 이다. 이제 어떤 대회를 통해 일부 선수들이 다음과 같은 점수를 얻었다고 하자. 각 쌍은 (선수 번호, 획득한 점수)이다.

(1, 25), (2, 20), (5, 10)

대회가 종료된 후, 선수들의 기존 랭킹 포인트에 새로 획득한 점수가 더해진 랭킹 포인트는 각각 (35, 35, 20, 8, 22)가 된다. 따라서 선수들의 순위는 이제 (1, 1, 4, 5, 3) 이다.

협회에서는 선수들의 게임 결과를 수시로 발표한다. 발표된 결과를 바탕으로 선수들의 순위 정보를 구하여 어떤 시점에 주어진 선수의 현재 순위를 출력하는 질의를 처리할 수 있는 프로그램을 작성하시오.

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트케이스의 첫 줄에는 선수들의 수를 나타내는 정수 N (1 ≤ N ≤ 100,000)이 주어진다. 선수들은 1 부터 N 까지의 번호로 구분된다. 둘째 줄에는 선수들의 게임 결과와 질의의 총 개수를 나타내는 정수 M (1 ≤ M ≤ 200,000)이 주어진다. 셋째 줄부터 M 개의 줄에는 선수의 게임 결과(획득한 점수) 또는 질의가 각 줄에 하나씩 주어진다. 각 줄의 내용은 "R j k" 또는 "Q j"이다. "R j k"는 선수 j 가 획득한 점수가 k 임을 나타내고, "Q j"는 선수 j 의 순위를 묻는 질의이다. 여기서 k 는 1 이상의 정수이다. 질의에 대한 답은 질의가 나온 시점까지 획득한 점수들을 누적한 랭킹 포인트에 의한 순위를 말한다. 각 테스트 케이스의 초기 랭킹 포인트는 모두 0 이라고 가정하고, 입력을 통해서 누적된 최종 랭킹 포인트는 어떤 선수도 1,000,000,000 을 넘지 않는다고 가정하라.

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트케이스의 각 질의에 대해 순서대로 한 줄에 하나씩 답을 출력한다.