问题文

高桥君住在一个 $H × W$ 的网格上。左下方的小方格是 $(1,1)$，右上方的小方格是 $(W,H)$。然而，这个网格有些棘手，偶尔会有光束飞过来。作为人类的高桥君，一旦被光束击中就会变得"非常糟糕"，所以他不想被光束击中。

光束通过 $(时间、方向、坐标)$ 这样的组合给出。时间表示光束到达的时间，方向表示是垂直还是水平。

具体来说，光束 $(t, 垂直, a)$ 在时间 $t$ 到达，对于满足 $1 ≤ i ≤ H$ 的所有 $i$，通过方格 $(a,i)$。光束 $(t, 水平, a)$ 在时间 $t$ 到达，对于满足 $1 ≤ i ≤ W$ 的所有 $i$，通过方格 $(i,a)$。其他的方格不会被光束击中。

幸运的是，高桥君知道光束什么时候以及以何种方式到来的全部信息。因此，他希望以最少的移动次数避开所有的光束。高桥君可以通过边与相邻的方格进行移动，一次可以移动1个方格。

由于高桥君经常进行训练，所以他可以在单位时间内进行任意次数的移动。此外，高桥君可以自由选择初始位置，并且在最后可以停留在任何一个方格上。注意，高桥君不能走出网格。

请计算高桥君的最小移动次数。如果高桥君无法避免被光束击中而移动，则输出 $-1$。

---

输入

输入通过标准输入按以下格式给出。

$W$ $H$ $Q$

$T_1$ $D_1$ $X_1$

...

$T_Q$ $D_Q$ $X_Q$

• 第一行有三个整数 $W, H, Q (1 ≤ W,H ≤ 10^5, 0 ≤ Q ≤ 10^5)$ 分别表示网格的宽度、高度和光束的数量。
• 接下来的 $Q$ 行描述了光束的信息。其中第 $i$ 行包括三个整数 $T_i, D_i, X_i (1 ≤ T_i ≤ 10^5, 0 ≤ D_i ≤ 1, 当 D_i=0 时，1 ≤ X_i ≤ W, 当 D_i=1 时，1 ≤ X_i ≤ H)$，表示光束在时刻 $T_i$ 以方向 $D_i$ 出现在位置 $X_i$。对于任意的 $i, j$，满足 $(T_i,D_i,X_i) ≠ (T_j,D_j,X_j)$。

---

部分得分

本问题设置了部分得分。

• 当满足 $1 ≤ W,H,Q ≤ 100, T_i ≤ 100 (1 ≤ i ≤ Q)$ 的数据集给出正确答案时，可以得到 30 分。

---

输出

如果存在一种移动方式使得光束不会击中高桥君，则输出高桥君的最小移动次数。否则，输出 $-1$。

输出的末尾必须包含一个换行符。(21:40修正)

---

示例输入1

3 2 8
1 0 2
3 0 2
4 1 2
2 1 2
4 0 3
2 0 3
1 1 1
2 0 1

示例输出1

3

高桥君可以通过以下移动方式避开所有的光束:

• 开始时，高桥君在 $(3,2)$ 的方格上。
• 在时间 $1.5$，高桥君移动到 $(2,2)$，然后移动到 $(2,1)$。
• 在时间 $2.5$，高桥君移动到 $(1,1)$。

---

示例输入2

2 4 10
3 1 1
2 1 3
3 0 1
2 1 4
1 1 3
2 1 2
3 1 2
1 0 1
3 1 4
2 0 2

示例输出2

4

---

示例输入3

3 3 5
1 0 3
1 0 2
1 1 3
1 1 2
1 0 1

示例输出3

-1