You have a generator that randomly generates a uniformly distributed random number in range [1,m] and a monitor that monitors the generator and gives an alert when some conditions are met. If at the i-th second, a condition is given to the monitor, then the monitor will give an alert at the j-th second reporting that the condition given at the i-th second is met. Here j is the minimum integer such that the numbers generated by the generator from the i-th second to the j-th second and in range [li,ri] equals to ci. Otherwise, the generator will generate a number ai. However, the monitor stops working now. We need you to write a program to give the alerts.
输入描述:
The first line contains an integer T, the number of test cases.
For each test case, the first line contains an integer m and n. The following n lines describe events. The i-th line describe the event happens at the i-th second. If the event is to give a condition, then it contains a character ”C” followed by li, ri and ci. Otherwise, the event is to generate a number and it contains a character ”G” followed by bi. ai, the number generated at the i-th second equals to the XOR sum of bi and the moments of all conditions met before i-th second.
It is guaranteed that 1 ≤ m ≤ 104 and 1 ≤ n ≤ 2×105.
输出描述:
For each test case, the output starts with a line ”Case #i:” where i is the test case number, starting from 1. Then you need to report the alerts in order. If some conditions are met at the i-th second, output a line containing i and moments when these conditions were given. Output moments in increasing order.
示例1
输入
复制
1
6 5
C 1 3 1
C 3 5 2
G 4
G 1
G 3
G 2
说明
At the 1st second, a condition is given. We need to make an alert when 1 number in range [1, 3] are generated.
At the 2nd second, a condition is given. We need to make an alert when 2 number in range [3, 5] are generated.
At the 3rd second, a number is generated. It is 4 because no condition is met before. We don’t need to make any alert because no condition is met after 4 is generated.
At the 4th second, a number is generated. It is 1 because no condition is met before. We need to make an alert because condition at 1st second is met after 1 is generated.
At the 5th second, a number is generated. Because condition at the 1st second is met before, the actual number generated should be 3 xor 1 which is 2. We don’t need to make any alert because no condition is met after 2 is generated.
At the 6th second, a number is generated. Because condition at the 1st second is met before, the actual number generated should be 2 xor 1 which is 3. We need to make an alert because condition at the 2nd second is met after 3 is generated.