Generator and Monitor

Time Limit: 32000/16000 MS (Java/Others)

Memory Limit: 70000/70000 K (Java/Others)

Description

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 [ $l_i, r_i$ ] equals to $c_i$ . Otherwise, the generator will generate a number $a_i$ . However, the monitor stops working now. We need you to write a program to give the alerts.

Input

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 $l_i , r_i$ and $c_i$ . Otherwise, the event is to generate a number and it contains a character ”G” followed by $b_i$ . $a_i$ , 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 ≤ $10^4$ and 1 ≤ n ≤ 2 × $10^5$ .

Output

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.

Sample Input

1 6 5 C 1 3 1 C 3 5 2 G 4 G 1 G 3 G 2

Sample Output

Case #1: 4 1 6 2
Hint
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.

Hint

jiangzijing2015

Source

2016ACM/ICPC亚洲区青岛站-重现赛(感谢中国石油大学)

提交代码