간달프, 빌보, 그리고 난쟁이들이 안개 산맥을 넘으려다 붙잡히자, 대(大)고블린은 간달프에게 한 가지 제안을 한다. 둘이서 고블린이 고안한 게임을 하자는 것이다. 간달프가 이기면 모두 풀려나지만, 대고블린이 이기면 간달프는 모리아의 보물을 되찾는 일을 도와야 한다. 간달프가 이길 수 있는지 판단하는 것이 여러분의 과제다.
게임은 크기가 매번 다른 직사각형 체커판 위에서 진행된다. 판에는 흰색 말과 검은색 말이 각각 한 플레이어에게 배정되어 임의의 위치에 놓여 있다. 각 행에는 흰색 말이 최대 한 개, 검은색 말이 최대 한 개 있다. 흰색 플레이어가 먼저 시작하며, 두 플레이어는 번갈아 자신의 말을 민다. 한 턴에 플레이어는 자신의 말 하나를 골라, 그 말이 놓인 행을 따라(행 사이 이동은 없다) 비어 있는 아무 칸으로 민다. 이때 다른 말을 뛰어넘을 수 없고, 판 밖으로 나갈 수도 없다.
자기 차례에 어떤 말도 움직일 수 없는 플레이어가 패배한다.
예를 들어 아래 왼쪽 배치를 생각해 보자. 첫 수에서 흰색은 맨 윗행의 흰색 말을 오른쪽 끝까지 밀 수 있고, 그러면 상대는 움직일 수 없게 되어 흰색이 이긴다. 두 번째 게임에서는 겉보기에 흰색에게 매우 유리해 보이지만 흰색이 진다. 흰색이 두는 모든 수가 검은색에게 응수할 여지를 만들어 주고, 결국 흰색 말들은 모두 반대편(왼쪽) 벽에 막혀 버리기 때문이다.
| 흰색이 이기는 배치 | 흰색이 지는 배치 |
|---|---|
![]() | ![]() |
| 흰색은 맨 윗 말을 오른쪽 끝까지 밀어 이긴다 | 흰색의 모든 수가 검은색에게 수를 만들어 주어 결국 검은색이 이긴다 |
첫 줄에는 테스트 케이스의 수($\le 20$)가 주어진다. 테스트 케이스들은 하나씩 이어서 주어진다.
각 테스트 케이스의 첫 줄에는 네 정수 $M$(행의 수), $N$(열의 수), $P$(흰색 말의 수), $Q$(검은색 말의 수)가 주어지며, $0 \le M, N \le 300$, $0 \le P, Q \le M$이다. 다음 $P$개의 줄은 흰색 말의 위치를 나타낸다. 그중 $i$번째 줄에는 두 정수 $r_i$와 $c_i$($1 \le r_i \le M$, $1 \le c_i \le N$)가 주어지며, $i$번째 흰색 말이 $r_i$행 $c_i$열에 있음을 뜻한다. 이어지는 $Q$개의 줄은 같은 형식으로 검은색 말의 위치를 나타낸다.
각 테스트 케이스마다 한 줄을 출력한다.
W,B,T를 출력한다.