← 返回题目列表

Codeforces · 1575/J

J. 掉球的危险

中文机器翻译题面 查看原题

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$$$ 列上。一旦球离开网格,它就会停止下落。