轨道炮

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

角色从 $(0,0)$ 出发，要到达 $(n,m)$。每一秒结束时，他可以从 $(i,j)$ 移动到 $(i+1,j)$、移动到 $(i,j+1)$，或原地等待。

共有 $r$ 次射击。一次射击由 $t,d,coord$ 描述：在第 $t$ 秒结束时，若 $d=1$，横坐标为 coord 的整行被贯穿；若 $d=2$，纵坐标为 coord 的整列被贯穿。角色当时位于该行或该列就会死亡。

求安全到达终点的最短时间；若无法到达，输出 $-1$。

输入格式

第一行是测试组数 $T$。每组先输入 $n,m$，再输入射击数 $r$，随后 $r$ 行每行三个整数 $t,d,coord$。

输出格式

每组输出一个整数，表示最短时间或 $-1$。

样例输入 1

5
1 3
4
1 2 0
2 2 1
3 2 2
4 1 1
3 3
6
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2
2 1
3
7 1 2
2 1 1
7 2 1
2 2
5
9 1 2
3 2 0
5 1 2
4 2 2
7 1 0
4 6
7
6 1 2
12 1 3
4 1 0
17 2 3
1 2 6
16 2 6
3 2 4

样例输出 1

5
-1
3
6
10

数据范围

对于所有数据：$1\le T\le10^4$，$1\le n\cdot m\le10^4$，$1\le r\le100$，$1\le t\le10^9$；所有测试组的 $n\cdot m$ 之和不超过 $10^4$。