Piet 是最著名的视觉深奥编程语言之一。 Piet 中的程序是由彩色像素块构建的,并使用相当复杂的规则进行解释。在这个问题中,我们将使用具有简化规则的 Piet 语言子集。
该程序将是由彩色和黑色像素组成的矩形图像。每个像素的颜色将由 0 到 9 之间的整数给出(含 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步之后将是当前的。
输入
输入的第一行包含两个整数 m (1 ≤ m ≤ 50) 和 n (1 ≤ n ≤ 5·107)。接下来的 m 行包含程序的行。所有线条的长度相同,介于 1 到 50 像素之间,并由字符 0 到 9 组成。第一行的第一个字符不会等于 0。
输出
输出经过n步程序解释后当前块的颜色。
示例
输入 #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
注意
在第一个示例中,IP 按以下方式更改。第 1 步之后,块 2 成为当前块,并在另外两个步骤后保持不变。在第 4 步之后 BP 移动到块 3,在步骤 7 之后移动到块 4,最后在第 10 步之后 BP 返回到块 1。
IP的状态顺序如图所示:箭头顺时针穿过,主箭头表示DP方向,一侧表示CP方向。