
ZOJ Problem Set  3967
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? InputThere 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^{4}) and q (1 ≤ q ≤ 5 × 10^{4}), indicating the number of cards on the table at the beginning, and the number of operations. For the following n lines, the ith line contains two integers r_{i} and b_{i} (10^{9} ≤ r_{i}, b_{i} ≤ 10^{9}), 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^{9} ≤ a, b ≤ 10^{9}).
It's guaranteed that neither the sum of n nor the sum of q over all test cases will exceed 2 × 10^{5}. 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++. OutputFor each operation 0 output one line, indicating the final score of that round. Sample Input2 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 Output2 5 1 4 4 Author: WENG, Caizhi Source: The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple 