B. The floor is lava!
time limit per test
3 seconds
memory limit per test
256 MB
input
standard input
output
standard output

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.

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

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.

Multiple people can move at the same time. Multiple people can be in the same cell at the same time.

Output

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

Example
Input
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
Output
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
Note

You can raise the lava to level $$$1$$$ without hurting anybody (each person is at a height of at least $$$1$$$).

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$$$).