141 - The Spot Game

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

請參考下列幾種佈局：



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

Input and Output

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

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

Sample input

2
1 1 +
2 2 +
2 2 -
1 2 +
2
1 1 +
2 2 +
1 2 +
2 2 -
0

Sample output

Player 2 wins on move 3
Draw

原文出處