순위

프로 게이머 협회는 등록된 $N$명 선수의 순위를 관리한다. 각 선수의 순위는 지금까지 얻은 점수를 모두 더한 랭킹 포인트로 정해지며, 랭킹 포인트가 높을수록 순위도 높다(1위가 가장 높다).

랭킹 포인트가 가장 높은 선수(들)의 순위는 1위이다. 그 밖의 선수의 순위는 자신보다 랭킹 포인트가 엄격히 큰 선수의 수에 1을 더한 값이다. 즉 랭킹 포인트가 같은 선수끼리는 순위가 같고, 다음 순위는 앞선 동점자 수만큼 건너뛴다.

선수는 1번부터 $N$번까지 번호로 구분한다. 예를 들어 $N = 5$이고 1번부터 5번 선수의 현재 랭킹 포인트가 차례로 $(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)$이 된다.

협회는 선수들의 경기 결과를 수시로 반영한다. 지금까지 반영된 결과를 바탕으로, 특정 시점에 주어진 선수의 현재 순위를 구하는 질의를 처리하는 프로그램을 작성하라.

입력은 표준 입력으로 주어진다. 첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스의 첫 줄에는 선수의 수 $N$ ($1 \le N \le 100000$)이 주어지며, 선수는 1번부터 $N$번까지 번호로 구분한다. 둘째 줄에는 경기 결과와 질의를 합한 개수 $M$ ($1 \le M \le 200000$)이 주어진다. 이어지는 $M$개의 줄에는 경기 결과 또는 질의가 한 줄에 하나씩, 다음 두 형식 중 하나로 주어진다.

• R j k : 선수 $j$가 점수 $k$를 얻었음을 뜻하며, 선수 $j$의 랭킹 포인트에 $k$를 더한다($k$는 1 이상의 정수).
• Q j : 그 시점까지 누적된 랭킹 포인트를 기준으로 선수 $j$의 현재 순위를 묻는다.

각 테스트 케이스가 시작할 때 모든 선수의 랭킹 포인트는 0이다. 입력을 모두 반영한 뒤에도 어떤 선수의 랭킹 포인트도 $1000000000$을 넘지 않는다.

표준 출력으로 출력한다. 각 테스트 케이스의 각 질의(Q)에 대해, 물어본 선수의 현재 순위를 질의가 나온 순서대로 한 줄에 하나씩 출력한다.