Problem : 347 - A. 小紫愛玩2048

小紫是個有點害羞的平凡高中生，她平常沒事的時候喜歡玩2048。
2048是個在4*4的盤面上玩的遊戲，盤面上會有許多數字方塊，它的遊戲畫面長這樣：

圖片來源：http://gabrielecirulli.github.io/2048/
2048的規則很簡單，一開始盤面上有許多方塊，每一個方塊上都有一個數字。每一次操作
你可以從上、下、左、右四個方向選擇一個方向，並把所有方塊都往你所選的方向推過去，如果有兩個數字同樣為x的方塊撞在一起的話，這兩個方塊會合併為2x，且你會獲得2x的分數，而這個遊戲的目標就是產生出一個數字為2048的方塊。如果有超過兩個數字一樣的方塊撞在一起，那麼會優先合併移動方向那一邊的兩個方塊。例如：假設目前盤面的某一部分為 2 2 2，此時若將所有方塊往右推，那麼盤面就會變為 2 4，並且獲得4分。每次操作後都會隨機產生一個方塊，該數字有90%的機率為2，而有10%的機率為4。但如果這次的操作沒有合併任何方塊也沒有移動任何方塊，這次的操作就不會出現新方塊。在本題中，所有新出現的方塊的數字皆為2。
但由於她玩2048一直輸，所以她想要請你幫她寫一個程式，讓她練習2048。這個程式需要支援以下的操作：
1. “Up x y” 將所有方塊往上推，並在(x, y)的位置產生一個2。
2. “Down x y” 將所有方塊往下推，並在(x, y)的位置產生一個2。
3. “Left x y” 將所有方塊往左推，並在(x, y)的位置產生一個2。
4. “Right x y” 將所有方塊往右推，並在(x, y)的位置產生一個2。
5. “Undo x” 復原剛剛做過的x個操作，並不會復原其他的Undo，若x為0則什麼事也不會發生。(註)
最左上角的座標視為(1, 1)、最左下角的座標視為(4, 1)、最右下角座標視為(4, 4)，其餘請參照範例輸入。由於不是每一次的操作都會產生新的方塊(如果沒有改變盤面就什麼也不會發生)，如果這次的操作不會改變盤面，那麼就忽略這次的操作(但會被Undo)。由於你只需要寫出一個練習用的程式，因此就算已經贏得遊戲(出現2048)或是已經輸了這場遊戲(無法移動方塊)，也要繼續執行操作。
保證一切輸入合理，新產生的方塊不會在已經有方塊的地方(該次操作無法改變盤面除外)，且保證起始盤面中的所有數字皆為不超過1024的2的正整數次方。

註：為求題意精確，在此再次強調Undo的功能：
1. 可能會出現Undo 0，就當作什麼也沒發生。
2. Undo並不會復原其他的Undo操作。
3. 無法改變盤面的操作應該被忽略，但此操作仍然會被Undo復原。