Checker Board

Time limit1sMemory limit128 MB

Summary

Each row holds at most one checker per color; players slide their pieces along rows and the one who cannot move loses. Decide whether White wins, Black wins, or the game can run forever.

Level: Hard9 of 10
Topics: Game theory, Greedy, Sorting, Implementation
Solved: No attempts yet

Problem

After capturing Gandalf, Bilbo, and the dwarves as they tried to make their way through the Misty Mountains, the Great Goblin makes Gandalf an offer: the two of them play a game the goblin has devised. If Gandalf wins, everyone goes free; if the Great Goblin wins, Gandalf must help him recover the treasures of Moria. Your task is to help Gandalf decide whether he can win.

The game is played on a rectangular checkerboard (its size varies) that holds white and black checkers — one color for each player — in a given, arbitrary arrangement. In each row there is at most one white checker and at most one black checker. Starting with the white player, the two players take turns sliding their checkers. On a turn a player picks one of their own checkers and slides it along its row (never between rows) to any empty cell; a checker may not jump over another checker, nor slide off the board.

The player who cannot move on their turn loses.

For example, consider the arrangement on the left below. On the first move White can slide the white checker in the top row all the way to the right, leaving the second player with no move, and wins. In the second game, although the position looks very favorable for White, White loses: every move White makes hands Black a reply, and eventually all of White's checkers get blocked against the far (left) wall.

Winning position	Losing position

White wins by sliding the top checker all the way to the right	Every White move creates a move for Black, and Black eventually wins

Input

The first line contains the number of test cases ( $\le 20$ ). The test cases follow one after another.

Each test case begins with a line of four integers $M$ (the number of rows), $N$ (the number of columns), $P$ (the number of white checkers), and $Q$ (the number of black checkers), where $0 \le M, N \le 300$ and $0 \le P, Q \le M$ . The next $P$ lines describe the white checkers: the $i$ -th of them contains two integers $r_i$ and $c_i$ ( $1 \le r_i \le M$ , $1 \le c_i \le N$ ), meaning the $i$ -th white checker sits in row $r_i$ , column $c_i$ . The following $Q$ lines describe the black checkers in the same format.

Output

For each test case, print one line:

W if the white player can win with best play,
B if the other player can win with best play,
T if the game can continue forever, with neither player able to force the other to lose.

Examples5

Example 1

Input

Expected output

W
B

Example 2
Input
```
1
1 5 1 1
1 1
1 5
```
Expected output
```
W
```
Example 3
Input
```
1
1 4 1 1
1 2
1 3
```
Expected output
```
B
```
Example 4
Input
```
1
2 5 1 1
1 2
2 4
```
Expected output
```
T
```

Example 5

Input

Expected output

W
B
T
W
B
B