Alice and Bob are playing games again. This game has nothing to do with stones. It is actually a card game.

There are n cards on the table, each with two integers (one is red, and the other one is blue) written on it. At the beginning of each round, two integers, L and R, will be given. Alice will pick an integer x such that L ≤ x ≤ R and tell her choice to Bob. After knowing the integer x, Bob will then choose a card from the table. The score of this round will be equal to rx + b, where r is the red integer on the chosen card and b is the blue integer on the chosen card.

Both Alice and Bob are free to check the cards on the table and the integers written on them before they make their decisions.

To make the game more interesting, some changes can be made before a certain round. There are two possible changes:

1. Add another card with a red integer and a blue integer written on it onto the table.
2. Remove a card from the table.

Alice wants to maximize the score of each round, while Bob wants to minimize it. If both of them play the game optimally, can you find out the final score for each round?

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains two integer n (1 ≤ n ≤ 5 × 10⁴) and q (1 ≤ q ≤ 5 × 10⁴), indicating the number of cards on the table at the beginning, and the number of operations.

For the following n lines, the i-th line contains two integers r_i and b_i (-10⁹ ≤ r_i, b_i ≤ 10⁹), indicating that initially there is a card with a red integer r_i and a blue integer b_i written on it on the table.

For the following q lines, each line contains three integers op (0 ≤ op ≤ 2), a and b (-10⁹ ≤ a, b ≤ 10⁹).

• If op equals 0, you are asked to calculate the final score of a round, where L = a and R = b is given. It's guaranteed that a ≤ b on this occasion.
• If op equals 1, a card with a red integer a and a blue integer b written on it will be put onto the table.
• If op equals 2, a card with a red integer a and a blue integer b written on it will be removed from the table. It's guaranteed that this card exists on the table. If there are multiple cards on the table which satisfy the condition, only one of them will be removed.

It's guaranteed that neither the sum of n nor the sum of q over all test cases will exceed 2 × 10⁵.

We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.

Output

For each operation 0 output one line, indicating the final score of that round.

Sample Input

2
2 7
-1 2
2 3
0 -1 1
2 -1 2
0 -1 1
2 2 3
1 1 2
1 -2 -1
0 -1 1
2 3
1 1
1 1
0 1 3
2 1 1
0 1 3

Sample Output

2
5
1
4
4

The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple