You finally trapped Lavutz and his $K - 1$ friends in a room (in total there are $K$ people). The room is very interesting, as it is split in $n$ rows and $m$ columns, and for each row $i$ and column $j$ ($1 \leq i \leq n$ and $1 \leq j \leq m$) there is a cell which is at $a_{i,j}$ units of height (distance in units from the ground). A person can move from cell ($i$, $j$) to one of the cells ($i-1$, $j$), ($i+1$, $j$), ($i$, $j-1$), ($i$, $j+1$) (if that doesn't go out of the boundaries of the room) in exactly $1$ second, or they can just stay in cell ($i$, $j$).

You have a device which can raise the level of the lava, which is initially raised at level $0$, but you don't want to hurt Lavutz or his friends. A person is hurt if the lava is raised at a level greater than the height of the cell where the person is at that moment.

Task

Now, you want to find for each $L$ from $1$ to $n \cdot m$ what is the minimum time you need to wait such that you can raise the lava to level $L$ and nobody gets hurt, or $-1$ if for any amount of time you will wait, you can't raise the lava to level $L$ without hurting anybody.

Input data

On the first line there are $3$ integers: $n$, $m$ ($1 \leq n, m \leq 700$)- the number of rows and columns and $K$ ($1 \leq K \leq 10 \ 000$) - the number of people in the room.

On the next $n$ lines, there will be $a_{i, j}$ ($1 \leq a_{i, j} \leq n \cdot m$) the height of cell ($i$, $j$). ($1 \leq i \leq n$ and $1 \leq j \leq m$).

For each of the next $K$ lines there will be two integers $x$, $y$ ($1 \leq x \leq n$ and $1 \leq y \leq m$) - the starting position of the $K$ people.

Output data

You will print $n \cdot m$ integers. The $i$-th integer is the answer for level $i$.

Constraints and clarifications

• Multiple people can move at the same time.
• Multiple people can be in the same cell at the same time.
• You can raise the lava to level $1$ without hurting anybody (each person is at a height of at least $1$).

Example

stdin

6 5 6
30 14 11 22 16
7 5 6 3 23
20 1 5 2 17
21 1 4 2 6
17 7 3 24 3
26 25 13 14 10
2 2
3 2
4 4
5 5
2 4
4 3

stdout

0 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 4 5 8 8 8 8 

Explanation

If you want to raise the lava to level $2$, you need to wait $1$ second for the person in cell ($3$, $2$).
If you want to raise the lava to level $6$, you need to wait $2$ seconds for the persons in cell ($4$, $3$).