슬라이드 회로

Gooli는 구릉지에 $\mathbf{B}$개의 건물을 소유한 거대 기업이다. 오 년 전, Gooli는 직원들이 한 건물에서 다른 건물로 이동할 수 있도록 슬라이드를 건설했으며(슬라이드는 양방향이 아니다), 이를 계기로 건물 사이에 슬라이드를 건설하는 전통이 시작되었다. 현재 $\mathbf{S}$개의 슬라이드가 존재한다.

Melek은 Gooli's Head of Transportation이자 문제 해결을 좋아하는 사람이다. 그녀는 슬라이드를 즐겁게 이용할 수 있도록 관리하는 임무를 맡았다. 그녀가 생각해 낸 방법은 일부 슬라이드를 비활성화하여 회로만 남기는 것이었다. 회로란 둘 이상의 건물로 이루어진 집합 $b_1, b_2, ..., b_k$으로, 각 $i$에 대해 건물 $b_i$에서 건물 $b_{i+1}$로 가는 슬라이드가 정확히 하나 활성화되어 있고, 건물 $b_k$에서 건물 $b_1$로 가는 슬라이드가 정확히 하나 활성화되어 있는 것을 말한다. 잘못된 방향으로 가는 일을 방지하기 위해, 이 건물들에서 출발하거나 이 건물들로 도착하는 다른 어떤 슬라이드도 활성화되어서는 안 된다. 각 건물이 정확히 하나의 회로에 속하면 슬라이드의 상태를 재미있다고 한다.

Gooli 캠퍼스의 슬라이드에는 1 이상 $\mathbf{S}$ 이하의 정수 번호가 붙어 있다. Melek은 활성화와 비활성화라는 두 연산을 지원하는 슬라이드 제어 콘솔을 만들었다. 두 연산은 모두 세 매개변수 $\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이 슬라이드의 상태를 재미있게 만들기 위해 활성화할 수 있는 비활성화된 슬라이드가 있다면 어떤 것인지 구한다.

제한

메모리 제한: 1 GB. 모든 $i$에 대해 $1 \le \mathbf{X_i} \le \mathbf{B}$. 모든 $i$에 대해 $1 \le \mathbf{Y_i} \le \mathbf{B}$. 모든 $i$에 대해 $\mathbf{X_i} \ne \mathbf{Y_i}$. 모든 $i \neq j$에 대해 $(\mathbf{X_i}, \mathbf{Y_i}) \neq (\mathbf{X_j}, \mathbf{Y_j})$. 모든 $j$에 대해 $\mathbf{A_j}$은 대문자 E 또는 대문자 D이다. 모든 $j$에 대해 $1 \le \mathbf{L_j} \le \mathbf{R_j} \le \mathbf{S}$. 모든 $j$에 대해 $1 \le \mathbf{M_j} \le \mathbf{S}$. 각 연산은 유효하다.

테스트 세트 1 (Visible Verdict)

시간 제한: 10초. $1 \le \mathbf{T} \le 100$. $2 \le \mathbf{B} \le 100$. $2 \le \mathbf{S} \le 1000$. $1 \le \mathbf{N} \le 1000$.

테스트 세트 2 (Hidden Verdict)

시간 제한: 120초. $1 \le \mathbf{T} \le 30$. $2 \le \mathbf{B} \le 3 \times 10^4$. $2 \le \mathbf{S} \le 3 \times 10^5$. $1 \le \mathbf{N} \le 3 \times 10^5$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 처리할 건물, 슬라이드, 연산의 수를 각각 나타내는 세 정수 $\mathbf{B}$, $\mathbf{S}$, $\mathbf{N}$이 포함된 줄로 시작한다. 이어서 $\mathbf{S}$개의 줄이 주어진다. 이 중 $i$⁠-⁠번째 줄에는 두 정수 $\mathbf{X_i}$와 $\mathbf{Y_i}$가 주어지며, 이는 번호가 $i$인 슬라이드가 건물 $\mathbf{X_i}$에서 건물 $\mathbf{Y_i}$로 이어진다는 뜻이다. 마지막으로 $\mathbf{N}$개의 줄이 연산을 나타낸다. 이 중 $j$⁠-⁠번째 줄에는 문자 $\mathbf{A_j}$와 세 정수 $\mathbf{L_j}$, $\mathbf{R_j}$, $\mathbf{M_j}$이 주어지며, $j$⁠-⁠번째 연산을 설명한다. $\mathbf{A_j}$은 활성화 연산을 대문자 E로, 비활성화 연산을 대문자 D로 나타낸다. 이 연산은 번호가 $\mathbf{M_j}$의 배수인 동시에 $\mathbf{L_j}$ 이상 $\mathbf{R_j}$ 이하인 슬라이드에 수행한다.

각 테스트 케이스마다 Case #$x$: $y_1\ y_2\ \dots\ y_\mathbf{N}$을 포함하는 한 줄을 출력한다. 여기서 $x$은 1부터 시작하는 테스트 케이스 번호이며, 처음 $j$번의 콘솔 연산으로 만들어진 슬라이드 상태에서 비활성화된 슬라이드를 정확히 하나 활성화하여 재미있는 상태로 만들 방법이 없다면 $y_j$는 대문자 X이다. 그렇지 않다면 $y_j$는 처음 $j$번의 콘솔 연산으로 만들어진 상태에서 $y_j$⁠-⁠번째 슬라이드를 활성화하면 재미있는 상태가 된다는 것을 나타내는 정수여야 한다.

예제 케이스 #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\}$.