Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3967
Card Game

Time Limit: 2 Seconds      Memory Limit: 131072 KB

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 LxR 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?


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 × 104) and q (1 ≤ q ≤ 5 × 104), 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 ri and bi (-109ri, bi ≤ 109), indicating that initially there is a card with a red integer ri and a blue integer bi written on it on the table.

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

  • 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 ab 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 × 105.

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++.


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

Sample Input

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


Author: WENG, Caizhi
Source: The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status