CF1840F.Railguns

Tema is playing a very interesting computer game.

During the next mission, Tema's character found himself on an unfamiliar planet. Unlike Earth, this planet is flat and can be represented as an $n \times m$ rectangle.

Tema's character is located at the point with coordinates $(0, 0)$. In order to successfully complete the mission, he needs to reach the point with coordinates $(n, m)$ alive.

Let the character of the computer game be located at the coordinate $(i, j)$. Every second, starting from the first, Tema can:

• either use vertical hyperjump technology, after which his character will end up at coordinate $(i + 1, j)$ at the end of the second;
• or use horizontal hyperjump technology, after which his character will end up at coordinate $(i, j + 1)$ at the end of the second;
• or Tema can choose not to make a hyperjump, in which case his character will not move during this second;

The aliens that inhabit this planet are very dangerous and hostile. Therefore, they will shoot from their railguns $r$ times.

Each shot completely penetrates one coordinate vertically or horizontally. If the character is in the line of its impact at the time of the shot (at the end of the second), he dies.

Since Tema looked at the game's source code, he knows complete information about each shot — the time, the penetrated coordinate, and the direction of the shot.

What is the minimum time for the character to reach the desired point? If he is doomed to die and cannot reach the point with coordinates $(n, m)$, output $-1$.

特玛正在玩一款非常有趣的电脑游戏。

在接下来的任务中，特玛的角色发现自己身处一颗陌生的星球上。与地球不同，这颗星球是平坦的，可被建模为一个 $n \times m$ 的矩形。

特玛的角色起始于坐标 $(0, 0)$ 处。为了成功完成任务，他必须活着抵达坐标 $(n, m)$ 处。

设电脑游戏中角色当前位于坐标 $(i, j)$。从第 $1$ 秒开始，每秒内特玛可以执行以下操作之一：

• 使用垂直超跃技术，使得角色在该秒结束时移动至坐标 $(i + 1, j)$；
• 使用水平超跃技术，使得角色在该秒结束时移动至坐标 $(i, j + 1)$；
• 或者选择不进行超跃，此时角色在该秒内保持静止；

这颗星球上的外星人极其危险且充满敌意，因此他们将使用轨道炮总共射击 $r$ 次。

每次射击会完全贯穿某一行或某一列（即沿垂直或水平方向穿透整条直线）。若角色在射击发生的时刻（即该秒结束时）恰好位于该射击路径上，则角色死亡。

由于特玛查阅了游戏源代码，他已完全掌握每次射击的全部信息——包括射击发生的时刻、被贯穿的坐标（即行号或列号），以及射击方向（垂直或水平）。

问：角色抵达目标点 $(n, m)$ 所需的最短时间是多少？若角色注定死亡、无法抵达 $(n, m)$，则输出 $-1$。

The first line of the input contains a single integer $T$ ($1 \le T \le 10^4$) — the number of test cases.

Then follow the descriptions of the test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \cdot m \le 10^4$) — the size of the planet, its height and width.

The second line of each test case contains a single integer $r$ ($1 \le r \le 100$) — the number of shots.

Then follow $r$ lines, each describing one shot.

A shot is described by three integers $t$, $d$, $coord$. Where $t$ is the second at which the shot will be fired ($1 \le t \le 10^9$). $d$ is the direction of the shot ($d = 1$ denotes a horizontal shot, $d = 2$ denotes a vertical shot). $coord$ is the size of the penetrated coordinate ($0 \le coord \le n$ for $d = 1$, $0 \le coord \le m$ for $d = 2$).

The sum of the products $n \cdot m$ over all test cases does not exceed $10^4$.

输入的第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。

随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \cdot m \le 10^4$），分别表示星球的尺寸（高度和宽度）。

每个测试用例的第二行包含一个整数 $r$（$1 \le r \le 100$），表示射击次数。

接下来是 $r$ 行，每行描述一次射击。

一次射击由三个整数 $t$、$d$、$coord$ 描述：其中 $t$ 表示该次射击发生的时刻（秒）（$1 \le t \le 10^9$）；$d$ 表示射击方向（$d = 1$ 表示水平射击，$d = 2$ 表示垂直射击）；$coord$ 表示被穿透坐标的数值（当 $d = 1$ 时，$0 \le coord \le n$；当 $d = 2$ 时，$0 \le coord \le m$）。

所有测试用例中 $n \cdot m$ 的总和不超过 $10^4$。

For each test case, output a single number — the minimum time for the character to reach the coordinate $(n, m)$, or $-1$ if he is doomed to die.

对于每个测试用例，输出一个数字——角色到达坐标 $(n, m)$ 所需的最短时间；若角色注定死亡，则输出 $-1$。

In the first test case, the character can move as follows: $(0, 0) \rightarrow (0, 1) \rightarrow (0, 2) \rightarrow (0, 3) \rightarrow (0, 3) \rightarrow (1, 3)$.

In the second test case, the character will not be able to leave the rectangle that will be completely penetrated by shots at the second $2$.

在第一个测试用例中，角色可以按如下方式移动：$(0, 0) \rightarrow (0, 1) \rightarrow (0, 2) \rightarrow (0, 3) \rightarrow (0, 3) \rightarrow (1, 3)$。

在第二个测试用例中，角色将无法离开该矩形区域，因为该矩形将在第 $2$ 秒时被子弹完全贯穿。