human
PYTHON3 solution for "Mr. Chanek has a new game called Dropping Balls. Initially, Mr. Chanek has a grid a of size n × 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, ..., c_k-th (1 ≤ c_i ≤ m) columns.

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

Input

The first line contains three integers n, m, and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 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},…,a_{i,m} (1 ≤ a_{i,j} ≤ 3). It will satisfy a_{i, 1} ≠ 3 and a_{i, m} ≠ 1.

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

Output

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

Examples

Input

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

Output

2 2 1 

Input

1 2 2
1 3
1 2

Output

1 2 

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, ..., c_k-th columns respectively. A ball will stop dropping once it leaves the grid.":
assistant
#Here is Python code to determine in which column each ball will end up in (position of the ball after leaving the grid).
 import sys
sys.setrecursionlimit(100000)

def _r(): return sys.stdin.buffer.readline()
def rs(): return _r().decode('ascii').strip()
def rn(): return int(_r())
def rnt(): return map(int, _r().split())
def rnl(): return list(rnt())

def solve(n, m, k, mat, q):
    sol, cache = [], [0]*m
    for c in q:
        cc = c-1
        if cache[cc] == 0:
            r, c, alldown = 0, c-1, True
            while r < n:
                if mat[r][c] == 2:
                    r += 1
                else:
                    alldown = False
                    mat[r][c], c = 2, c + 2 - mat[r][c]
            if alldown:
                cache[cc] = c+1
            sol.append(c+1)
        else:
            sol.append(cache[cc])
    return sol

n, m, k = rnt()
mat = []
for _ in range(n):
    mat.append(rnl())
q = rnl()
print(' '.join(map(str, solve(n, m, k, mat, q))))

# def solve(n, m, mat):
#     def _try(r, c, dr, dc):
#         sol = 0
#         for i in range(c+1, c+dc):
#             sol += 1 - int(mat[r][i])
#             sol += 1 - int(mat[r+dr][i])
#         for i in range(r+1, r+dr):
#             sol += 1 - int(mat[i][c])
#             sol += 1 - int(mat[i][c+dc])
#         for i in range(r+1, r+dr):
#             for j in range(c+1, c+dc):
#                 sol += int(mat[i][j])
#         return sol
#     sol = float('inf')
#     sols = [[0]*m for _ in range(n)]
#     for r in range(n-4):
#         for c in range(m-3):
#             dr = 4
#             while r+dr < n:
#                 dc = 3
#                 while c+dc < m:
#                     sols[r+dr][c+dc] = _try(r, c, dr, dc)
#                     sol = min(sol, _try(r, c, dr, dc))
#                     dc += 1
#                 dr += 1
#     for row in sols:
#         print(row)
#     return sol

# for _ in range(rn()):
#     n, m = rnt()
#     mat = []
#     for _ in range(n):
#         mat.append(rs())
#     print(solve(n, m, mat))