网格上的整数

题目描述

有一个 $H$ 行 $W$ 列的网格。用 $(i, j)$ 表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子。

每个格子中写着一个整数。对每个 $i = 1, 2, \ldots, N$，格子 $(r_i, c_i)$ 中写着一个正整数 $a_i$。其余格子中写着 0。

初始时，有一个棋子放在格子 $(R, C)$ 上。 高桥可以把棋子任意多次地移动到当前所在格子以外的格子。 但是，移动棋子时必须同时满足以下两个条件。

棋子移动到的格子上的整数，严格大于棋子移动前所在格子上的整数。

棋子移动前和移动后所在的格子在同一行或同一列。

对每个 $i = 1, 2, \ldots, N$，输出当 $(R, C) = (r_i, c_i)$ 时，高桥最多能移动棋子的次数。

输入格式

输入按以下格式从标准输入给出：

$H$ $W$ $N$
$r_1$ $c_1$ $a_1$
$r_2$ $c_2$ $a_2$
$\vdots$
$r_N$ $c_N$ $a_N$

输出格式

输出 $N$ 行。 对每个 $i = 1, 2, \ldots, N$，第 $i$ 行输出当 $(R, C) = (r_i, c_i)$ 时，高桥最多能移动棋子的次数。

样例

3 3 7
1 1 4
1 2 7
2 1 3
2 3 5
3 1 2
3 2 5
3 3 5

1
0
2
0
3
1
0

网格中填入的整数如下。

4 7 0
3 0 5
2 5 5

当 $(R, C) = (r_1, c_1) = (1, 1)$ 时，可以按 $(1, 1) \rightarrow (1, 2)$ 移动，共移动 1 次。

当 $(R, C) = (r_2, c_2) = (1, 2)$ 时，一次也不能移动。

当 $(R, C) = (r_3, c_3) = (2, 1)$ 时，可以按 $(2, 1) \rightarrow (1, 1) \rightarrow (1, 2)$ 移动，共移动 2 次。

当 $(R, C) = (r_4, c_4) = (2, 3)$ 时，一次也不能移动。

当 $(R, C) = (r_5, c_5) = (3, 1)$ 时，可以按 $(3, 1) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2)$ 移动，共移动 3 次。

当 $(R, C) = (r_6, c_6) = (3, 2)$ 时，可以按 $(3, 2) \rightarrow (1, 2)$ 移动，共移动 1 次。

当 $(R, C) = (r_7, c_7) = (3, 3)$ 时，一次也不能移动。

5 7 20
2 7 8
2 6 4
4 1 9
1 5 4
2 2 7
5 5 2
1 7 2
4 6 6
1 4 1
2 1 10
5 6 9
5 3 3
3 7 9
3 6 3
4 3 4
3 3 10
4 2 1
3 5 4
1 2 6
4 7 9

2
4
1
5
3
6
6
2
7
0
0
4
1
5
3
0
5
2
4
0

数据范围

• 输入均为整数。
• $2 \le H, W \le 2 \times 10^5$
• $1 \le N \le \min(2 \times 10^5, HW)$
• $1 \le r_i \le H$
• $1 \le c_i \le W$
• $1 \le a_i \le 10^9$
• $i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)$