TopCoder

Thumb mikasa mikoto furikae
Omelet
ㄏ一ㄏ一 $$AC \approx (111111111)_2$$

User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

34.8% (16/46)

Description

現在有一個遊戲,它的規則是有一個(2n-1)×(2n-1)的棋盤,劃分成如上圖般的螺旋形。

剛開始盤面上有 k 顆石頭,兩位玩家輪流行動。

每個玩家每次要移動一顆石頭,且只能將那顆石頭朝中心的方向移動,移動多少格都可以,兩個石頭可以放在同一格中。

當然,已經被移到中心的石頭就不能再被移動了。

只要某個人無法再移動任何石頭,他就輸了。

現在給你剛開始石頭放的位置,請問先手還是後手有必勝策略呢?

Input Format

本題有多筆測試資料。

第一行有兩個正整數 n, T ,表示棋盤大小以及接下來有多少組測試資料。( 0 < n, T <= 1000 )

接下來的每組測試資料:

第一行有一個整數 k ,表示棋盤上有 k 個石頭。( 0 <= k <= 100,000,000 )

接下來有 k 行,第 i 行有兩個正整數 a, b,表示第 i 個石頭在座標為(a,b)的地方。

( 座標以左上角為(1,1),由上到下x座標遞增,由左到右y座標遞增。)

Output Format

對於每組測資,請輸出一行"A Win!"或"B Win."或"Tie!"或"Tie!!",分別表示先手有必勝策略、後手有必勝策略、兩人都沒有必勝策略或是兩人都有必勝策略。

Sample Input

3 1
2
2 1
2 3

Sample Output

A Win!

Hints

Problem Source

原TIOJ1480 / 建中校內培訓第六次模擬考試。
Problem Setter:hallogameboy、peter50216

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4
4 1500 65536 262144 5
5 1500 65536 262144 6
6 1500 65536 262144 7
7 1500 65536 262144 8
8 1500 65536 262144 9
9 1500 65536 262144 10
10 1500 65536 262144 11