Q141 - The Spot Game

放 石頭遊戲(The game of Spot)在一塊 NxN 的板子上進行,如下圖為N=4的板子。遊戲的玩法是兩個玩家輪流放一塊石頭在空的格子上,或是可以從板子上拿一塊石頭起來,遊戲的進行中可以發現,板子上 石頭的佈局會不斷變化,當一玩家排出已重複出現過的佈局時,他就算輸了這一局(一種佈局如果將之旋轉90度、180度、270度亦視為相同的佈局)。若在 2N步內未出現過相同的佈局就算和局。

請 參考下列幾種佈局:

若 出現過第一種佈局,則再出現2、3、4種佈局即結束比賽(還有另一種能結束比賽的佈局未畫出),注意,第5種佈局並不能算是相同的佈局。

Input

輸 入會有多組測試資料,一開始會給定板子的大小N (2 <= N <= 50),接下來會有 2N 個移步方式,當然也有可能2N步還沒走完就有人贏得了比賽。每一列會有一個座標位置,並以 + 或 - 來表示新增或移除一塊石頭。你可以假定所有的步驟都是合法的,也就是說,不會在空格子上拿走一塊石塊,也不會重複放置石頭在同一個位置上。輸入的最後會以 N=0 做結束。

Output

請 輸出哪位玩家贏得了比賽,並在哪一步贏得比賽,若平手則輸出 draw。

Sample Input Sample Output
2
1 1 +
2 2 +
2 2 -
1 2 +
2
1 1 +
2 2 +
1 2 +
2 2 -
0
Player 2 wins on move 3
Draw








中 文翻譯:Ruby兔的ACM園地