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).
Output
Output \(k\) integers — the \(i\)-th integer denoting the column where the \(i\)-th ball will end.
Note
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
|
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
|
2 2 1
|
|
2
|
1 2 2
1 3
1 2
|
1 2
|