愛文是一顆喜歡旅行的芒果，這天，愛文決定去方塊國來一場說走就走的旅行。

方塊國是一個由 $N \times N$ 個方形城市構成的國度，像一個邊長是 $N$ 的棋盤一樣整齊排列成方陣，其中每一列從北到南編號，每一行從西到東編號，第 $i$ 列第 $j$ 行的城市以座標 $(i, j)$ 表示。當芒果在城市 $(i, j)$ 時，他可以移動到東、南、西、北任一個相鄰的城市，如下圖所示。

芒果手上有一張地圖，地圖上每一個城市可以塗上不同的顏色，一開始地圖上的所有城市的顏色都是 1 號顏色。我們規定所有顏色以一個不大於 $M$ 的正整數表示，而且方塊國邊界外的城市均視為顏色 0。芒果從城市 $(x_0, y_0)$ 出發，每一天，他會觀察他所在城市及相鄰城市的顏色、把現在所在城市塗上一個新的顏色、然後移動到相鄰的四個城市之一。

為了確保旅程充滿未知的驚喜，他事先制定了許多規則，並決定一直按照這些規則移動，直到他的旅程結束。每一條規則由六個整數 $c_N, c_E, c_S, c_W, c_X, c_Y$ 及一個大寫字母 $D$（$D$ 是 NESW 其中之一）表示。芒果會檢查北邊、東邊、南邊、西邊、以及目前所在城市的顏色組合，當這五個顏色依序恰好為 $c_N, c_E, c_S, c_W, c_X$ 的時候，芒果將會先在地圖上把目前所在城市塗成顏色 $c_Y$ 之後，往字母 $D$ 所代表的方向移動到相鄰城市。

舉例來說，若 $N=4, x_0=2, y_0=1$，現在的地圖顏色分佈與芒果制定的規則如下：

這一天，芒果在紅框標示的城市中，他會檢查周圍的城市顏色，並尋找有沒有 $(c_N, c_E, c_S, c_W, c_X) = (2, 2, 3, 0, 1)$ 的規則，注意西邊的城市在方塊國邊界外所以視為顏色 0。芒果會使用規則二，移動後地圖狀態如下：

芒果就要出發了，現在他已經決定好了所有的移動規則、起始城市的座標、和這次旅行的天數，你能幫芒果模擬他的旅程、事先預測他結束旅程時會待在哪個城市嗎？不過，因為計畫總是有可能出錯的，假如芒果旅行到一半就會先離開方塊國、或者會遇到沒有在任何規則中的城市顏色組合，他也希望你能事先提醒他。