Robot

There were many robots in a robotics lab. Some robots had very high IQ (IQ means task performance). All robot completed a task within a certain period of time. The lab manager wanted some tasks to be completed by these robot, but the manager could not find the minimum time to complete all the tasks.

Note:  The manager could remove any robot from them or add new robots to the lab.

Here,

Robot                   IQ          Task Complete time

Robot R1               3            3,6,9,12,15....

Robot R2                8            8,16,24,32....

The Robot (R1) had IQ-3 which means that robot (R1) can complete a task after every 3 seconds, here R1 can complete 1st task in 3s, 2nd task in 6s, 3rd task in 9s etc. (Note: Lower IQ gives higher performance)

If we have to complete 4 tasks by these robot then we need minimum 9 seconds. Here 1st robot gives 3 tasks and 2nd robot gives 1 task at this time.  We can use one or more robots at a time to complete a task.

Similarly,

Number of Task - Minimum time

2                             6s

3                             8s

4                            9s

Implement each required function by referring to following function description.

Add (int R, int IQ)

This function add the robot in the lab (1 ≤ R ≤ 1000000000), (1 ≤ IQ ≤ 3000).

All robot are unique id.

Remove (int R)

This function remove the robot with id R in the lab. (But if any robot isn’t exist in the lab then we don’t need this opration)

FindMinimumTime (int task)

This function return minimum time to complete all the task (1 ≤ task ≤ 5000)

Input

The first line contains one integer t (1 ≤ t ≤ 50) — the number of test cases.

The first line of each test case contains two integer N(1<=N<=1000) and Q(1<=Q<=10000) — number of robots that already present in the lab and number of query.

The N  line contains two integers Ri and IQi ( 1<= i <=N)

Next Q lines contain queries in the form described in the statement.

For each query the first input k (1<=k<=3) where k denotes the number of functionality.

(k=1 means Add function, k=2 means Remove and k=3 means FindMinimumTime function).

Output

For each test case, print one number in a line – referring to above function description.

Sample

1
2 5
101 3
10003 8
3 3
1 10448 105
3 7  
2 10003
3 4

8
16
12

Note: Add function call maximum 5000 times.