你有一个随机生成器和一个监控器。生成器会随机生成一个在 $[1, m]$ 范围内均匀分布的随机数；监控器则负责监控生成器，并在满足某些条件时发出警报。

如果在第 $i$ 秒向监控器给出了一个条件，那么当该条件满足时，监控器将在第 $j$ 秒发出警报，报告在第 $i$ 秒给出的条件已满足。这里 $j$ 是满足以下条件的最小整数：生成器在第 $i$ 秒到第 $j$ 秒之间（包含边界）生成的、且数值在区间 $[l_i, r_i]$ 内的随机数个数等于 $c_i$。

如果第 $i$ 秒发生的事件不是给出条件，则生成器会生成一个数字 $a_i$。

然而，现在监控器停止了工作。我们需要你编写一个程序来发出 these 警报。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例：

第一行包含两个整数 $m$ 和 $n$。

接下来的 $n$ 行描述了事件。第 $i$ 行描述了在第 $i$ 秒发生的事件：

• 如果该事件是给出条件，则包含一个字符 C，后跟 $l_i$、$r_i$ 和 $c_i$。
• 否则，该事件是生成一个数字，包含一个字符 G，后跟 $b_i$。在第 $i$ 秒实际生成的数字 $a_i$ 等于 $b_i$ 与在第 $i$ 秒之前已满足的所有条件的给定时刻（即这些条件被给出的秒数）的异或和（XOR sum）。

保证 $1 \le m \le 10^4$ 且 $1 \le n \le 2 \times 10^5$。

输出格式

对于每个测试用例，输出首先以一行 Case #i: 开始，其中 $i$ 是测试用例的编号，从 1 开始。

然后你需要按时间顺序报告警报。如果某些条件在第 $i$ 秒被满足，则输出一行，包含 $i$ 以及这些条件被给出的时刻。这些时刻按升序排列。

样例

输入格式 1

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

输出格式 1

Case #1:
4 1
6 2

说明

在第 1 秒，给出一个条件。当在区间 $[1, 3]$ 内生成了 1 个数字时，我们需要发出警报。

在第 2 秒，给出一个条件。当在区间 $[3, 5]$ 内生成了 2 个数字时，我们需要发出警报。

在第 3 秒，生成了一个数字。由于之前没有条件被满足，该数字为 4。在生成 4 之后没有条件被满足，因此我们不需要发出任何警报。

在第 4 秒，生成了一个数字。由于之前没有条件被满足，该数字为 1。在生成 1 之后，第 1 秒给出的条件被满足，因此我们需要发出警报。

在第 5 秒，生成了一个数字。因为第 1 秒给出的条件在之前已被满足，实际生成的数字应为 $3 \oplus 1 = 2$。在生成 2 之后没有条件被满足，因此我们不需要发出任何警报。

在第 6 秒，生成了一个数字。因为第 1 秒给出的条件在之前已被满足，实际生成的数字应为 $2 \oplus 1 = 3$。在生成 3 之后，第 2 秒给出的条件被满足，因此我们需要发出警报。