题目描述

给定一个 $H\times W$ 的矩形，有 $n$ 个格子里面有 $a_i$ 根香蕉。你是一只猴子，每一步可以从当前格子移动到当前行或当前列，比当前格子的香蕉数多的格子。

现在这 $n$ 个有香蕉的格子里面都有一只猴子，求每只猴子最多可以移动多少步。

输入格式

第一行输入三个整数分别为 $h,w,n$

接下来 $n$ 行每行三个整数，代表 $r_i,c_i,a_i$ 意思为第 $r_i$ 行 $c_i$ 列有 $a_i$ 根香蕉。

输出格式

打印 $N$ 行。对于每一个 $𝑖=1,2,…,𝑁$， 第 $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

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\ \leq\ H,\ W\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ N\ \leq\ \min(2\ \times\ 10^5,\ HW)$
• $1\ \leq\ r_i\ \leq\ H$
• $1\ \leq\ c_i\ \leq\ W$
• $1\ \leq\ a_i\ \leq\ 10^9$
• $ i\ \neq\ j\ \Rightarrow\ (r_i,\ c_i)\ \neq\ (r_j,\ c_j) $
• 所有的值均为整数

Sample Explanation 1

• 当 $(R,C)=(r_1,c_1)=(1,1)$ 时，可以移动一次棋子，移动方式为 $(1,1)\to (1,2)$。
• 当 $(R,C)=(r_2,c_2)=(1,2)$ 时，无法移动棋子。
• 当 $(R,C)=(r_3,c_3)=(2,1)$ 时，可以移动两次棋子，移动方式为 $(2,1)\to (1,1)\to (1, 2)$。
• 当 $(R,C)=(r_4,c_4)=(2,3)$ 时，无法移动棋子。
• 当 $(R,C)=(r_5,c_5)=(3,1)$ 时，可以移动三次棋子，移动方式为 $(3,1)\to (2,1)\to (1, 1)\to (1, 2)$。
• 当 $(R,C)=(r_6,c_6)=(3,2)$ 时，可以移动一次棋子，移动方式为 $(3,2)\to (1,2)$。
• 当 $(R,C)=(r_7,c_7)=(3,3)$ 时，无法移动棋子。