슬라이드 회로

Gooli는 구릉 지대에 B개의 건물을 가진 거대한 회사다. 5년 전 Gooli는 직원들이 한 건물에서 다른 건물로 이동할 수 있게 하는 슬라이드를 지었고(양방향이 아니다), 이로써 건물 사이에 슬라이드를 짓는 전통이 시작되었다. 현재 S개의 슬라이드가 있다.

Melek은 Gooli의 교통 담당 책임자이자 문제 풀이를 즐기는 사람이다. 그녀는 슬라이드를 계속 재미있게 사용할 수 있도록 유지하는 일을 맡았다. 그녀가 떠올린 아이디어는 일부 슬라이드를 비활성화해서 회로만 남기는 것이었다. 회로란 두 개 이상의 건물 b1, b2, ..., bk의 집합으로, 각 i에 대해 건물 bi에서 건물 bi+1로 활성화된 슬라이드가 정확히 하나 있고, 건물 bk에서 건물 b1로 활성화된 슬라이드가 정확히 하나 있다. 잘못된 방향으로 가는 것을 막기 위해, 이 건물들 중 어느 곳에서도 나가거나 들어오는 다른 슬라이드는 활성화되어 있으면 안 된다. 슬라이드의 상태는 각 건물이 정확히 하나의 회로에 속하면 fun이라고 한다.

Gooli 캠퍼스의 슬라이드는 1부터 S까지의 정수로 번호가 매겨져 있다. Melek은 enable과 disable 두 가지 연산을 지원하는 슬라이드 제어 콘솔을 만들었다. 두 연산 모두 ℓ, r, m 세 매개변수를 받고, ℓ ≤ x ≤ r이고 x가 m의 배수인 각 슬라이드 x에 대해 연산을 수행한다. enable 연산은 연산 직전에 영향을 받는 모든 슬라이드가 비활성화 상태일 때만 유효하다. 마찬가지로 disable 연산은 연산 직전에 영향을 받는 모든 슬라이드가 활성화 상태일 때만 유효하다.

다음 그림은 가능한 상태와 연산의 연속을 보여준다. 배치에는 3개의 건물과 3개의 슬라이드가 있다. 슬라이드는 비활성화 상태일 때 연한 회색, 활성화 상태일 때 진한 회색이다.

1. 초기 상태. 모든 슬라이드가 비활성화되어 있다.	2. ℓ = 1, r = 2, m = 1인 enable 연산 후.	3. ℓ = 3, r = 3, m = 1인 enable 연산 후.	4. ℓ = 1, r = 3, m = 2인 disable 연산 후.
5. ℓ = 1, r = 3, m = 3인 disable 연산 후.		6. ℓ = 1, r = 2, m = 2인 enable 연산 후.

불행히도 Melek의 고양이 Sult가 콘솔을 발견하고 여러 유효한 enable 및 disable 연산을 수행하기 시작했다. Sult가 콘솔 연산을 수행할 때마다 Melek은 현재 비활성화된 슬라이드를 정확히 하나 활성화해서 슬라이드 상태를 fun으로 만들 수 있는지 알고 싶어한다. Melek이 실제로 이 슬라이드를 활성화하지는 않는다.

위 그림에서 첫 번째, 세 번째, 마지막 연산 후에는 Melek이 유일하게 비활성화된 슬라이드를 활성화해서 fun 상태로 만들 수 있다. 두 번째 연산 후에는 문제가 두 가지 있다. 하나는 현재 비활성화된 슬라이드가 없어서 Melek이 아무것도 활성화할 수 없다는 것이다. 또한 상태가 이미 fun이므로, 비활성화된 슬라이드가 더 있더라도 무언가를 활성화하면 fun이 아닌 상태가 된다. 네 번째 연산 후에는 비활성화된 슬라이드가 두 개 있지만, 어느 것을 활성화해도 fun 상태가 되지 않는다.

모든 슬라이드는 처음에 비활성화되어 있고, Sult가 연산을 하나씩 수행한다. Sult의 각 연산 후에, Melek이 어떤 비활성화된 슬라이드를 활성화하면 슬라이드 상태를 fun으로 만들 수 있는지 판별하라.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그다음 T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 B, S, N 세 정수를 포함하는 한 줄로 시작한다. 각각 건물의 수, 슬라이드의 수, 처리할 연산의 수다. 그다음 S개의 줄이 이어진다. 이 중 i번째 줄에는 두 정수 Xi와 Yi가 있으며, 번호가 i인 슬라이드가 건물 Xi에서 건물 Yi로 간다는 뜻이다. 마지막으로 N개의 줄이 연산을 나타낸다. j번째 줄에는 문자 Aj와 세 정수 Lj, Rj, Mj가 있으며, j번째 연산을 설명한다. Aj는 연산의 종류를 나타내며, 대문자 E는 enable, 대문자 D는 disable이다. 연산은 번호가 Mj의 배수이면서 Lj 이상 Rj 이하인 슬라이드에 수행된다.

각 테스트 케이스마다 Case #x: y1 y2 … yN을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, yj는 처음 j개의 콘솔 연산으로 만들어진 슬라이드 상태를 비활성화된 슬라이드 하나를 활성화해서 fun 상태로 만들 수 없으면 대문자 X이다. 그렇지 않으면 yj는 yj번째 슬라이드를 활성화하면 처음 j개의 콘솔 연산으로 만들어진 상태가 fun 상태가 된다는 것을 나타내는 정수다.

• 모든 i에 대해 1 ≤ Xi ≤ B.
• 모든 i에 대해 1 ≤ Yi ≤ B.
• 모든 i에 대해 Xi ≠ Yi.
• 모든 i ≠ j에 대해 (Xi, Yi) ≠ (Xj, Yj).
• 모든 j에 대해 Aj는 대문자 E 또는 대문자 D.
• 모든 j에 대해 1 ≤ Lj ≤ Rj ≤ S.
• 모든 j에 대해 1 ≤ Mj ≤ S.
• 각 연산은 유효하다.

예제 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}.