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 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:
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 (-109 ≤ ri, 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 (-109 ≤ a, b ≤ 109).
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++.
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