Description

澄星是一颗被划分为 $n\times m$ 个网格的行星。网格 $(x,y)$ 表示第 $x$ 行、第 $y$ 列，其中 $1\le x\le n$，$1\le y\le m$。

行星上存在 $k$ 个离子干扰核心。第 $i$ 个干扰核心的中心位于 $(x_i,y_i)$，干扰半径为 $d_i$。

对于行星内的一个网格 $(x,y)$，当且仅当 $|x-x_i|\le d_i$且$|y-y_i|\le d_i$ 时，该网格会受到第 $i$ 个干扰核心影响。

换言之，每个干扰核心会覆盖一个以其中心为中心、按切比雪夫距离计算的正方形区域。超出行星边界的部分会被忽略。

现在需要在行星上建造一座极光信标。信标的中心必须位于行星内的某个网格 $(x_{\mathrm{ans}},y_{\mathrm{ans}})$，并选择一个非负整数信号半径 $d_{\mathrm{ans}}$。

行星内的网格 $(x,y)$ 会被信标覆盖，当且仅当 $|x-x_{\mathrm{ans}}|+|y-y_{\mathrm{ans}}|\le d_{\mathrm{ans}}$。

信标覆盖的所有行星内网格都不能受到任何干扰核心影响。信标覆盖区域超出行星边界的部分同样会被忽略。

请计算信标信号半径 $d_{\mathrm{ans}}$ 的最大可能值。

如果行星上的每一个网格都受到干扰，因而不存在任何可以作为信标中心的位置，输出 $-1$。

Format

Input

第一行包含三个整数 $n,m,k(1\le n,m\le 500,1\le k\le \min(500,nm))$，分别表示行星的行数、列数和干扰核心数量。

接下来 $k$ 行，第 $i$ 行包含三个整数 $x_i,y_i,d_i(1\le x_i\le n,1\le y_i\le m,0\le d_i\le 500)$，表示第 $i$ 个干扰核心的中心坐标和干扰半径。

所有干扰核心的中心坐标两两不同。

Output

输出一个整数，表示满足条件的最大信号半径。

如果不存在任何可以建造信标的位置，输出 $-1$。

Samples

5 6 2
2 2 2
5 6 1

1

5 5 1
3 3 2

-1

Note

在第一个样例中，第一个干扰核心覆盖第 $1$ 行至第 $4$ 行、第 $1$ 列至第 $4$ 列；第二个干扰核心覆盖第 $4$ 行至第 $5$ 行、第 $5$ 列至第 $6$ 列。

可以将信标中心放在 $(1,6)$ 或 $(2,6)$，并令信号半径为 $1$。此时信标覆盖的所有行星内网格均未受到干扰。

不存在信号半径至少为 $2$ 的合法方案，因此答案为 $1$。

在第二个样例中，唯一的干扰核心覆盖了整个 $5\times5$ 行星，因此没有任何网格可以作为信标中心，答案为 $-1$。