Description
(文長，慎入)
時值西元2025年
人類補完計畫再次啟動
人類補完委員會為此需要招募全世界頂尖的人才
因此他們在網路上向全世界的工程師下了戰帖
覺得這個計畫相當中二的你
情不自禁地點開了人類補完計畫的人才招募網頁
打開網頁的瞬間
「你能在這些碎片之中拼湊出希望嗎?」斗大的標題映入眼簾
螢幕上接著出現了一個相當復古的拼圖遊戲
玩法很簡單，給你一張原始的矩形圖片，這張圖片被劃分成M列N行的區域(列是橫的row，行是直的column)
將最右下角的區域拿走之後，並將剩下M*N-1個區域重新排列，形成遊戲的初始狀態
玩家可以執行的操作就只有將緊鄰空格上下左右的圖片移動至空格的位置而已
透過一連串的操作，直到M*N-1個區域的排列與原始圖片相同時，玩家獲得勝利
(如果沒玩過或看不懂敘述，以下用圖片被劃分成2列2行的區域為例)
這個遊戲一開始難度不高
因為只是2列2行的劃分而已，對你來說根本毫無智商可言
秒殺進入第二關之後，接下來是4列4行的劃分，但對你來說也是一塊蛋糕
不費吹灰之力地 你來到了第九十九關(不小心玩上癮了)
在第九十九關開始之前，系統出現以下訊息
「天將降大任於斯人也，必先苦其心志，勞其筋骨，餓其體膚，空乏其身...」
「偉大的勇士啊！這是最後一道試煉了，突破人類的界限接近神的領域吧！」
看完如此OOXX的開場白之後，此時的你發現大事不妙了，因為這一關你必須用60吋大螢幕才能玩得起來
原始圖片竟然被裁切成576列1024行的區域，根本是整人遊戲
但是愈是困難的問題，就愈是引起你的興趣(這就是工程師之魂啊～～)
經過仔細分析與思考後，你發現只剩下作弊竄改遊戲資料與寫程式交由電腦解題這兩種選擇
當然，字典裡不存在作弊這個字眼的你，毫不猶豫地選擇了寫程式這個方案
但是又經過一番思索之後，你發現如果單純採取暴力搜索法，最差的情況下可能太陽系都毀滅了電腦還找不出答案
於是你開始上網找尋資料，不眠不休地翻閱各種期刊論文，嘗試著將演算法進行優化
不幸的是，三天三夜過去了仍絲毫不見任何進展
已經精疲力盡的你意識漸漸模糊，此時腦海中浮現了十年前的場景
「這不是我踏上不歸路的時候嗎？真是令人懷念啊，在競程基礎班的那段時光。」夢中你喃喃自語著
「還記得才第二次上課就上機到晚上11點，差點就把課退掉了，呵呵」
「咦？為什麼會花這麼多時間呢？」
「喔我想起來了，那一天的上機題目是有關逆序數對(Inversion Pair)」
「仔細一想，逆序數對...」
「...」
「有了！BINGO！！！」你突然從夢中驚醒，眼中閃爍著希望的光芒
「接下來就剩下證實假說了，根據我的推估，最後一關應該是無解的」
接著你以驚人的打字速度在半分鐘內寫好程式，並且建立576列1024行的圖片資訊當作程式的input
果真不出所料，最後一關實際上是無解的
為了表達不滿，你向委員會寄了一封電子郵件，內容主要是抨擊這個遊戲設計者的惡趣味
三天之後，補完眠你起了個大早，打開信箱發現了委員會給你的回信
「勇士啊！你能進入最後的關卡確實不錯，但是請證明你的論點，否則我們只能將你視為能力不足。」
原來是你之前寄信時只顧著批評遊戲設計者，而忘記把你在夢中想到的推論與實際上實作出來的程式碼作為夾帶檔案寄出
於是你又開始用驚人的打字速度記錄下在夢中想到關於本問題的輔助定理
==========
定義 - 序列
原始圖片可以用M列N行的整數矩陣表示(M>=2, N>=2)，由左至右、由上至下，從1開始遞增編號
因為之後需要把右下角的區域拿掉，我們令矩陣右下角的元素為0
對於拼圖在某個時間點的狀態，我們一樣可以用整數矩陣來表示，矩陣的每個元素就對應著原始圖片的區域編號
但為了以下定理討論方便，我們不用矩陣的形式，改用序列的形式表示，這個序列是由矩陣一列接著一列得出
※以下引理、定理所說的序列，都是從此定義出發
==========
引理1 - 若交換序列中任意兩元素的位置，則序列的逆序數對個數的奇偶性會改變
證明很簡單，不另外贅述
推論：每經過一次合法操作，序列的逆序數對個數的奇偶性改變
==========
引理2 - 要保持序列最後的元素0位置不變，必須經過偶數次合法的操作
證明很簡單，不另外贅述
==========
引理3 - 若序列A與序列B由相同元素組成且最後的元素都是0且逆序數對個數的奇偶性不一致，則不可能透過合法操作將A轉換成B
根據引理1、2，得證
==========
引理4 - 若序列A與序列B由相同元素組成且最後的元素都是0且逆序數對個數的奇偶性一致，則存在有限次合法操作的方法將A轉換成B
需要用到離散數學課程學到的"等價類(equivalence class)"的概念
我們先將可以透過合法操作互相轉換的序列A與序列B歸為同一個等價類
可以用窮舉的方法證明2*2矩陣得出的序列只有2個等價類
進一步地，可以推廣至M*N的矩陣(M>=2, N>=2)得出的序列也只有兩個等價類
搭配引理3，我們知道其中一個等價類是逆序數對個數為偶數的序列，另一個是逆序數對個數為奇數的序列
至此，引理4證明完畢
※由於證明過程稍嫌複雜，此處僅列出證明方向，有興趣深入探討者，請自行查閱相關文獻
==========
定理 - 若拼圖遊戲初始狀態的序列與原始圖片的序列，兩者逆序數對個數的奇偶性一致時，則拼圖遊戲有解。反之，奇偶性不一致時，則拼圖遊戲無解。
因為遊戲開始與遊戲結束時，序列的最後一個元素必定是0，根據引理3、4，定理成立
==========
至於程式碼的部分，因為你在補眠的時候，你的妹妹進來房間動過你的電腦，不小心被刪掉了
但是妹妹是無價之寶，所以你寧願犧牲自己的時間也不忍心怪罪於她
反正也不花你幾秒鐘，請你重新再打一次吧！
究竟人類補完計畫會如何發展呢？沒有AC，就沒有未來。
你的一小步，是人類的一大步！
Input
本題有多筆測資，請以EOF作為輸入終止條件
每筆測資的第一列是兩個整數M,N(2<=M<=1024,2<=N<=1024)，中間會以一個空白字元分隔
表示原始圖片被劃分成M列N行
接下來會有M列輸入，這M列之中除了最後一列只有(N-1)個數字以外，每列都有N個數字，數字間會以一個空白字元分隔
這(M*N-1)個數字代表遊戲初始狀態的整數矩陣(編號範圍由題目敘述的定義可得出)，值得注意的是矩陣右下角編號為0的空格區域並不會在輸入中出現
測資之間會一個換行字元('\n')隔開
測資保證不會有像是編號重複、編號不在正常範圍諸如此類不合理的情況出現
讀測資時請儘量用scanf，使用cin並不是沒有TLE的可能性，請特別留意
Output
對於每一筆測資請判斷該組拼圖是否為無解。
若無解則輸出"WTF? No solution?"，若有解則輸出"WTF? How to solve it?"