Rankings

A pro gamer association maintains a ranking of its $N$ registered players. Each player's standing is decided by ranking points, the sum of every point the player has earned so far: the more ranking points, the higher the standing (rank 1 is the best).

The player (or players) with the most ranking points are rank 1. Every other player's rank equals the number of players who have strictly more ranking points, plus one. In other words, players with equal ranking points share the same rank, and the next rank skips ahead by the number of tied players.

Players are numbered from 1 to $N$. For example, if $N = 5$ and the current ranking points of players 1 through 5 are $(10, 15, 20, 8, 12)$, then their ranks are $(4, 2, 1, 5, 3)$.

Now suppose that in some tournament a few players earn the following points, where each pair is (player number, points earned):

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

After the tournament, adding the new points to the existing ranking points gives $(35, 35, 20, 8, 22)$, so the ranks become $(1, 1, 4, 5, 3)$.

The association applies match results continually. Write a program that, based on the results applied so far, answers queries asking for a given player's current rank at that moment.

Input is given on standard input. The first line contains the number of test cases $T$ ($1 \le T \le 20$).

For each test case, the first line contains the number of players $N$ ($1 \le N \le 100000$); players are numbered from 1 to $N$. The second line contains $M$ ($1 \le M \le 200000$), the total number of match results and queries. Each of the next $M$ lines holds one result or one query, in one of the two forms below.

• R j k : player $j$ earned $k$ points; add $k$ to player $j$'s ranking points ($k$ is an integer at least 1).
• Q j : ask for player $j$'s current rank, based on the ranking points accumulated up to that point.

At the start of each test case every player has 0 ranking points. Even after all input is applied, no player's ranking points exceed $1000000000$.

Print to standard output. For each query (Q) in each test case, print the current rank of the queried player, one per line, in the order the queries appear.