Gooli 是一家拥有 $B$ 座建筑的大型公司，位于丘陵地带。五年前，Gooli 修建了滑梯，允许员工从一座建筑前往另一座建筑（滑梯不是双向的），从而开启了在建筑间修建滑梯的传统。目前，共有 $S$ 条滑梯。

Melek 是 Gooli 的交通主管，也是一位解题爱好者。她的任务是确保这些滑梯使用起来令人愉快。她想出的办法是禁用一些滑梯，使得剩下的滑梯仅构成若干个回路。回路是指一组包含两个或更多建筑的集合 $b_1, b_2, \dots, b_k$，对于每个 $i$，从建筑 $b_i$ 到建筑 $b_{i+1}$ 恰好有一条启用的滑梯，并且从建筑 $b_k$ 到建筑 $b_1$ 也恰好有一条启用的滑梯。为了防止误导，这些建筑中不应有其他启用的滑梯。如果每座建筑都恰好属于一个回路，那么滑梯的状态就被称为“有趣”（fun）。

Gooli 园区内的滑梯编号为 $1$ 到 $S$（包含 $1$ 和 $S$）。Melek 创建了一个滑梯控制台，支持两种操作：启用（enable）和禁用（disable）。两种操作都接收三个参数 $\ell, r$ 和 $m$，并对所有满足 $\ell \le x \le r$ 且 $x$ 是 $m$ 的倍数的滑梯 $x$ 执行操作。启用操作仅在所有受影响的滑梯在操作前处于禁用状态时才有效。同样，禁用操作仅在所有受影响的滑梯在操作前处于启用状态时才有效。

下图展示了状态和操作的可能演变过程。该布局有 $3$ 座建筑和 $3$ 条滑梯。滑梯在禁用时为浅灰色，启用时为深灰色。

1. 初始状态。所有滑梯均已禁用。 2. 执行 $\ell = 1, r = 2, m = 1$ 的启用操作后。

3. 执行 $\ell = 3, r = 3, m = 1$ 的启用操作后。 4. 执行 $\ell = 1, r = 3, m = 2$ 的禁用操作后。

5. 执行 $\ell = 1, r = 3, m = 3$ 的禁用操作后。 6. 执行 $\ell = 1, r = 2, m = 2$ 的启用操作后。

不幸的是，Melek 的猫 Sult 发现了控制台，并开始执行若干次有效的启用和禁用操作。在 Sult 执行完每次控制台操作后，Melek 都想知道是否可以通过启用当前恰好一个已禁用的滑梯来使滑梯状态变得“有趣”。注意，Melek 实际上并不会启用该滑梯。

在上图中，我们可以看到在第一次、第三次和最后一次操作后，Melek 可以启用唯一的那个已禁用滑梯并达到“有趣”状态。在第二次操作后，存在两个问题。一个问题是当前没有已禁用的滑梯，因此 Melek 无法启用任何滑梯。此外，该状态本身已经是“有趣”的，所以即使有额外的已禁用滑梯，启用任何滑梯也会导致状态不再“有趣”。在第四次操作后，有两个已禁用的滑梯，但启用其中任何一个都无法产生“有趣”的状态。

所有滑梯最初都是禁用的，然后 Sult 依次执行其操作。在 Sult 的每次操作后，确定 Melek 可以启用哪个已禁用的滑梯（如果有的话）来使滑梯状态变得“有趣”。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $B, S$ 和 $N$，分别表示建筑数量、滑梯数量和要处理的操作数。接下来 $S$ 行，第 $i$ 行包含两个整数 $X_i$ 和 $Y_i$，表示编号为 $i$ 的滑梯从建筑 $X_i$ 通向建筑 $Y_i$。最后 $N$ 行表示操作。第 $j$ 行包含一个字符 $A_j$ 和三个整数 $L_j, R_j$ 和 $M_j$，描述第 $j$ 次操作。$A_j$ 使用大写字母 E 表示启用，大写字母 D 表示禁用。该操作针对所有编号同时满足是 $M_j$ 的倍数且在 $L_j$ 到 $R_j$ 之间的滑梯执行。

输出格式

对于每个测试用例，输出一行 Case #x: y1 y2 … yN，其中 $x$ 是测试用例编号（从 1 开始），$y_j$ 是一个大写字母 X，表示在执行前 $j$ 次控制台操作后，无法通过启用恰好一个已禁用的滑梯来使状态变得“有趣”。否则，$y_j$ 应为一个整数，表示启用第 $y_j$ 条滑梯可以使前 $j$ 次控制台操作后的状态变得“有趣”。

数据范围

内存限制：1 GB。 $1 \le X_i \le B$，对于所有 $i$。 $1 \le Y_i \le B$，对于所有 $i$。 $X_i \neq Y_i$，对于所有 $i$。 $(X_i, Y_i) \neq (X_j, Y_j)$，对于所有 $i \neq j$。 $A_j$ 为大写字母 E 或 D，对于所有 $j$。 $1 \le L_j \le R_j \le S$，对于所有 $j$。 $1 \le M_j \le S$，对于所有 $j$。 每次操作均有效。

子任务 1

时间限制：10 秒。 $1 \le T \le 100$。 $2 \le B \le 100$。 $2 \le S \le 1000$。 $1 \le N \le 1000$。

子任务 2

时间限制：120 秒。 $1 \le T \le 30$。 $2 \le B \le 3 \times 10^4$。 $2 \le S \le 3 \times 10^5$。 $1 \le N \le 3 \times 10^5$。

样例

样例输入 1

2
3 3 5
1 2
2 3
3 1
E 1 2 1
E 3 3 1
D 1 3 2
D 1 3 3
E 1 2 2
5 8 10
1 5
5 3
4 1
3 2
2 4
2 5
2 1
1 4
E 1 8 2
D 4 8 2
E 3 5 1
E 1 1 3
E 1 1 1
E 5 8 2
D 1 8 3
D 5 8 4
D 4 5 1
E 3 4 1

样例输出 1

Case #1: 3 X 2 X 3
Case #2: 3 X 1 1 X X X 3 X 5

说明

样例 #1 即为题目描述中展示的案例。 样例 #2 的建筑和滑梯布局如下图所示：

每次操作后启用的滑梯集合为： $\{2, 4, 6, 8\}$ $\{2\}$ $\{2, 3, 4, 5\}$ $\{2, 3, 4, 5\}$ $\{1, 2, 3, 4, 5\}$ $\{1, 2, 3, 4, 5, 6, 8\}$ $\{1, 2, 4, 5, 8\}$ $\{1, 2, 4, 5\}$ $\{1, 2\}$ $\{1, 2, 3, 4\}$