Tema 正在玩一个非常有趣的电脑游戏。
在下一次任务中,特马的角色发现自己身处一个陌生的星球。与地球不同,这颗行星是平坦的,可以表示为 $$$n \times m$$$ 矩形。
Tema 的角色位于坐标为 $$$(0, 0)$$$ 的点。为了成功完成任务,他需要活着到达坐标$$$(n, m)$$$的地点。
令电脑游戏的角色位于坐标$$$(i,j)$$$处。从第一秒开始,Tema 可以:
- 要么使用垂直超级跳跃技术,之后他的角色将在第二秒结束时到达坐标$$$(i + 1, j)$$$;
- 或使用水平超级跳跃技术,之后他的角色将在第二秒结束时到达坐标$$$(i, j + 1)$$$;
- 或者特马可以选择不进行超级跳跃,在这种情况下他的角色在这一秒内不会移动;
居住在这个星球上的外星人非常危险且充满敌意。因此,他们会用轨道炮射击 $$$r$$$ 次。
每次射击垂直或水平完全穿透一个坐标。如果角色在射击时(在第二秒结束时)位于其撞击线上,他就会死亡。
由于 Tema 查看了游戏的源代码,他知道每次射击的完整信息 - 时间、穿透坐标和射击方向。
角色到达所需点的最短时间是多少?如果他注定要死并且无法到达坐标$$$(n, m)$$$的点,则输出$$$-1$$$。
输入
输入的第一行包含一个整数 $$$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$$$ 是穿透坐标的大小($$$0 \le coord \le n$$$ for $$$d = 1$$$,$$$0 \le coord \le m$$$ for $$$d = 2$$$)。
所有测试用例的乘积 $$$n \cdot m$$$ 之和不超过 $$$10^4$$$。
输出
对于每个测试用例,输出一个数字 - 角色到达坐标 $$$(n, m)$$$ 的最短时间,如果他注定要死,则输出 $$$-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
注意
在第一个测试用例中,角色可以按如下方式移动:$$$(0, 0) \rightarrow (0, 1) \rightarrow (0, 2) \rightarrow (0, 3) \rightarrow (0, 3) \rightarrow (1, 3)$$$。
在第二个测试用例中,角色将无法离开在第二个 $$$2$$$ 处被射击完全穿透的矩形。