CF132B.Piet

Piet is one of the most known visual esoteric programming languages. The programs in Piet are constructed from colorful blocks of pixels and interpreted using pretty complicated rules. In this problem we will use a subset of Piet language with simplified rules.

The program will be a rectangular image consisting of colored and black pixels. The color of each pixel will be given by an integer number between 0 and 9, inclusive, with 0 denoting black. A block of pixels is defined as a rectangle of pixels of the same color (not black). It is guaranteed that all connected groups of colored pixels of the same color will form rectangular blocks. Groups of black pixels can form arbitrary shapes.

The program is interpreted using movement of instruction pointer (IP) which consists of three parts:

• current block pointer (BP); note that there is no concept of current pixel within the block;
• direction pointer (DP) which can point left, right, up or down;
• block chooser (CP) which can point to the left or to the right from the direction given by DP; in absolute values CP can differ from DP by 90 degrees counterclockwise or clockwise, respectively.

Initially BP points to the block which contains the top-left corner of the program, DP points to the right, and CP points to the left (see the orange square on the image below).

One step of program interpretation changes the state of IP in a following way. The interpreter finds the furthest edge of the current color block in the direction of the DP. From all pixels that form this edge, the interpreter selects the furthest one in the direction of CP. After this, BP attempts to move from this pixel into the next one in the direction of DP. If the next pixel belongs to a colored block, this block becomes the current one, and two other parts of IP stay the same. It the next pixel is black or outside of the program, BP stays the same but two other parts of IP change. If CP was pointing to the left, now it points to the right, and DP stays the same. If CP was pointing to the right, now it points to the left, and DP is rotated 90 degrees clockwise.

This way BP will never point to a black block (it is guaranteed that top-left pixel of the program will not be black).

You are given a Piet program. You have to figure out which block of the program will be current after n steps.

Piet 是最著名的视觉型深奥编程语言之一。Piet 程序由彩色像素块构成，并依据相当复杂的规则进行解释。本题中，我们将使用 Piet 语言的一个子集，并采用简化的规则。

程序是一个矩形图像，由彩色像素和黑色像素组成。每个像素的颜色用一个介于 $0$ 到 $9$（含）之间的整数表示，其中 $0$ 表示黑色。一个“像素块”被定义为一个由相同颜色（非黑色）像素构成的矩形区域。题目保证：所有同色（非黑色）且连通的像素集合均构成矩形块；而黑色像素组成的连通区域则可呈任意形状。

程序通过“指令指针”（IP）的移动来解释执行，IP 由三部分组成：

• 当前块指针（BP）；注意：在块内部不存在“当前像素”的概念；
• 方向指针（DP），其指向可为左、右、上或下；
• 块选择器（CP），其指向相对于 DP 所指方向而言的左侧或右侧；即，CP 在绝对意义上分别与 DP 呈逆时针或顺时针 $90^\circ$ 夹角。

初始状态下，BP 指向包含程序左上角像素的块，DP 指向右方，CP 指向左方（参见下图中的橙色方块）。

程序解释执行的每一步按如下方式改变 IP 的状态：解释器首先找出当前颜色块在 DP 所指方向上的最远边缘；然后，在构成该边缘的所有像素中，选出在 CP 所指方向上最远的那个像素；接着，BP 尝试从该像素沿 DP 方向移动到下一个像素。若下一个像素属于某个彩色块，则该块成为新的当前块，IP 的其余两部分（DP 和 CP）保持不变；若下一个像素为黑色或位于程序边界之外，则 BP 保持不变，但其余两部分发生变化：若 CP 原本指向左，则现在改为指向右，DP 保持不变；若 CP 原本指向右，则现在改为指向左，且 DP 顺时针旋转 $90^\circ$。

由此，BP 永远不会指向黑色块（题目保证程序左上角像素不为黑色）。

你将获得一个 Piet 程序。你需要确定经过 $n$ 步之后，IP 所指向的是程序中的哪一个块。

The first line of the input contains two integer numbers m (1 ≤ m ≤ 50) and n (1 ≤ n ≤ 5·107). Next m lines contain the rows of the program. All the lines have the same length between 1 and 50 pixels, and consist of characters 0-9. The first character of the first line will not be equal to 0.

输入的第一行包含两个整数 $m$（$1 \leq m \leq 50$）和 $n$（$1 \leq n \leq 5 \cdot 10^7$）。接下来的 $m$ 行包含程序的各行。所有行的长度均相同，介于 $1$ 到 $50$ 像素之间，且仅由字符 0–9 组成。第一行的第一个字符不等于 0。

Output the color of the block which will be current after n steps of program interpretation.

输出程序解释执行 n 步后当前方块的颜色。

In the first example IP changes in the following way. After step 1 block 2 becomes current one and stays it after two more steps. After step 4 BP moves to block 3, after step 7 — to block 4, and finally after step 10 BP returns to block 1.

The sequence of states of IP is shown on the image: the arrows are traversed clockwise, the main arrow shows direction of DP, the side one — the direction of CP.

在第一个示例中，指令指针（IP）按如下方式变化：步骤 1 后，块 2 成为当前块，并在此后两个步骤中保持为当前块；步骤 4 后，BP 移动到块 3；步骤 7 后，BP 移动到块 4；最终，步骤 10 后，BP 返回块 1。

IP 的状态序列如图所示：箭头按顺时针方向遍历；主箭头表示 DP 的方向，侧向箭头表示 CP 的方向。