CF1575J.Jeopardy of Dropped Balls

Mr. Chanek has a new game called Dropping Balls. Initially, Mr. Chanek has a grid $a$ of size $n \times m$

Each cell $(x,y)$ contains an integer $a_{x,y}$ denoting the direction of how the ball will move.

• $a_{x,y}=1$ — the ball will move to the right (the next cell is $(x, y + 1)$);
• $a_{x,y}=2$ — the ball will move to the bottom (the next cell is $(x + 1, y)$);
• $a_{x,y}=3$ — the ball will move to the left (the next cell is $(x, y - 1)$).

Every time a ball leaves a cell $(x,y)$, the integer $a_{x,y}$ will change to $2$. Mr. Chanek will drop $k$ balls sequentially, each starting from the first row, and on the $c_1, c_2, \dots, c_k$-th ($1 \leq c_i \leq m$) columns.

Determine in which column each ball will end up in (position of the ball after leaving the grid).

Chanek 先生有一个新游戏，名为“掉落小球”。初始时，Chanek 先生有一个大小为 $n \times m$ 的网格 $a$。

每个格子 $(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$ 个小球，每个小球均从第一行开始下落，且第 $i$ 个小球的起始列号为 $c_i$（即第 $i$ 个小球从位置 $(1, c_i)$ 开始下落），其中 $1 \leq c_i \leq m$。

请确定每个小球最终从哪一列离开网格（即小球离开网格时所在的列号）。

The first line contains three integers $n$, $m$, and $k$ ($1 \leq n, m \leq 1000$, $1 \leq k \leq 10^5$) — the size of the grid and the number of balls dropped by Mr. Chanek.

The $i$-th of the next $n$ lines contains $m$ integers $a_{i,1},a_{i,2},\ldots,a_{i,m}$ ($1 \leq a_{i,j} \leq 3$). It will satisfy $a_{i, 1} \ne 3$ and $a_{i, m} \ne 1$.

The next line contains $k$ integers $c_1, c_2, \ldots, c_k$ ($1 \leq c_i \leq m$) — the balls' column positions dropped by Mr. Chanek sequentially.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 1000$，$1 \leq k \leq 10^5$）—— 分别表示网格的尺寸以及 Mr. 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$）—— 表示 Mr. Chanek 依次投下小球所在的列位置。

Output $k$ integers — the $i$-th integer denoting the column where the $i$-th ball will end.

输出 $k$ 个整数——第 $i$ 个整数表示第 $i$ 个球最终所在的列。

In the first example, the first ball will drop as follows. Note that the cell $(1, 1)$ will change direction to the bottom direction.

The second and third balls will drop as follows.

All balls will be dropped from the first row and on the $c_1, c_2, \dots, c_k$-th columns respectively. A ball will stop dropping once it leaves the grid.

在第一个示例中，第一个小球的下落路径如下所示。注意，单元格 $(1, 1)$ 的方向将变为向下。

第二个和第三个球的下落路径如下所示。

所有小球均从第一行分别在第 $c_1, c_2, \dots, c_k$ 列处释放。一个小球一旦离开网格，即停止下落。