Chanek 先生有一款新游戏,名为 Dropping Balls。最初,Chanek 先生有一个网格 $$$a$$$,大小为 $$$n \times m$$$
每个单元格 $$$(x,y)$$$ 包含一个整数 $$$a_{x,y}$$$ 表示球移动的方向。
- $$$a_{x,y}=1$$$ — 球将向右移动(下一个单元格是 $$$(x, y + 1)$$$);
- $$$a_{x,y}=2$$$ — 球将移动到底部(下一个单元格是 $$$(x + 1, y)$$$);
- $$$a_{x,y}=3$$$ — 球将向左移动(下一个单元格是 $$$(x, y - 1)$$$)。
每次球离开单元格 $$$(x,y)$$$ 时,整数 $$$a_{x,y}$$$ 将更改为 $$$2$$$。 Chanek 先生将从第一行开始按顺序掉落 $$$k$$$ 球,并在 $$$c_1、c_2、\dots、c_k$$$ 列($$$1 \leq c_i \leq m$$$)列上。
确定每个球最终会进入哪一列(离开网格后球的位置)。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n, m \leq 1000$$$, $$$1 \leq k \leq 10^5$$$) — 网格的大小和 Chanek 先生扔下的球的数量。
接下来的 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$m$$$ 整数 $$$a_{i,1},a_{i,2},\ldots,a_{i,m}$$$ ($$$1 \leq a_{i,j} \leq 3$$$)。它将满足 $$$a_{i, 1} \ne 3$$$ 和 $$$a_{i, m} \ne 1$$$。
下一行包含 $$$k$$$ 整数 $$$c_1, c_2, \ldots, c_k$$$ ($$$1 \leq c_i \leq m$$$) — Chanek 先生依次掉落的球的列位置。
输出
输出 $$$k$$$ 整数 — 第 $$$i$$$ 个整数,表示第 $$$i$$$ 个球将结束的列。
示例
输入 #1
5 5 3 1 2 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 1
输出 #1
2 2 1
输入 #2
1 2 2 1 3 1 2
输出 #2
1 2
注意
在第一个示例中,第一个球将按如下方式掉落。请注意,单元格 $$$(1, 1)$$$ 会将方向更改为底部方向。
第二个和第三个球将按如下方式掉落。
所有球将从第一行分别掉落在 $$$c_1、c_2、\dots、c_k$$$ 列上。一旦球离开网格,它就会停止下落。