Piet

题意翻译

题目描述 --- Piet是最著名的视觉深奥编程语言之一。Piet中的程序由彩色像素块构建，并使用相当复杂的规则进行解释。在本题中，我们将使用带有简化规则的Piet语言子集。该程序将由彩色和黑色像素组成的矩形图像。每个像素的颜色将由0到9之间的整数给出，包括0表示黑色。像素块被定义为相同颜色（不是黑色）的像素矩形。保证所有连接的相同颜色的彩色像素组将形成矩形块。黑色像素组可以形成任意形状。程序使用指令指针（IP）的移动来解释，该指针由三部分组成：-电流块指针（BP）；请注意，块内没有电流像素的概念；-方向指针（DP），可以指向左、右、向上或向下；-块选择器（CP），可以根据DP给出的方向指向左或向右；在绝对值中，CP可以与DP相差90度或顺时针。最初，BP指向包含程序左上角的块，DP指向右侧，CP指向左侧（见下图中的橙色方块）。程序解释的一个步骤以以下方式改变IP的状态。解释器找到当前颜色块最远的DP边缘。从构成此边缘的所有像素中，解释器选择CP方向最远的像素。之后，BP试图朝着DP的方向从这个像素移动到下一个像素。如果下一个像素属于彩色块，则该块将成为当前块，IP的其他两个部分保持不变。它的下一个像素是黑色或程序之外，BP保持不变，但IP的另外两个部分会发生变化。如果CP指向左侧，现在指向右侧，DP保持不变。如果CP指向右，现在指向左，DP顺时针旋转90度。这样BP永远不会指向黑块（保证程序的左上角像素不会是黑色的）。你得到了一个Piet程序。在n步骤后，您必须弄清楚程序的哪个块将是最新的。

题目描述

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.

输入输出格式

输入格式

The first line of the input contains two integer numbers $ m $ ( $ 1<=m<=50 $ ) and $ n $ ( $ 1<=n<=5·10^{7} $ ). 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.

输出格式

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

输入输出样例

输入样例 #1

2 10
12
43

输出样例 #1

1

输入样例 #2

3 12
1423
6624
6625

输出样例 #2

6

输入样例 #3

5 9
10345
23456
34567
45678
56789

输出样例 #3

5

说明

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.