
ZOJ Problem Set  3765
Now you have N lights in a line. Don't worry  the lights don't have color. The only status they have is on and off. And, each light has a value, too. There is a boring student in ZJU. He decides to do some boring operations to the lights:
Please help this boring guy to do this boring thing so that he can have time to find a girlfriend! InputThe input contains multiple test cases. Notice there's no empty line between each test case. For each test case, the first line of the a case contains two integers, N (1 ≤ N ≤ 200000) and Q (1 ≤ Q ≤ 100000), indicating the number of the lights at first and the number of the operations. In following N lines, each line contains two integers, Num_{i} (1 ≤ Num_{i} ≤ 1000000000) and Status_{i} (0 ≤ Status_{i} ≤ 1), indicating the number of the light i and the status of it. In following Q lines, each line indicating an operation, and the format is described above. It is guaranteed that the range of the operations will be appropriate. For example, if there is only 10 lights, you will not receive an operation like "Q 1 11 0" or "D 11". OutputFor each Query operation, output an integer, which is the answer to the query. If no lights are with such status, please output 1. Sample Input3 12 27 1 32 0 9 1 Q 1 3 1 I 3 64 0 Q 2 4 0 Q 2 4 1 I 2 43 1 D 5 Q 1 2 1 M 1 35 Q 1 2 1 R 1 R 3 Q 1 2 1 Sample Output9 32 9 27 35 1 Author: WANG, Xiajun Source: ZOJ Monthly, March 2014 