F. Рельсотроны
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тёма играет в одну очень интересную компьютерную игру.

Во время прохождения очередной миссии, персонаж Тёмы оказался на незнакомой планете. В отличие от Земли эта планета плоская и представима в виде прямоугольника $$$n \times m$$$.

Персонаж Тёмы находится в точке с координатами $$$(0, 0)$$$, чтобы успешно завершить миссию ему необходимо живым добраться до точки с координатами $$$(n, m)$$$.

Пусть персонаж компьютерной игры находится в координате $$$(i, j)$$$. Каждую секунду, начиная с первой, Тёма может:

  • либо воспользоваться технологией гиперпрыжка по вертикали, после чего его персонаж попадёт в координату $$$(i + 1, j)$$$ в конце секунды,
  • либо воспользоваться технологией гиперпрыжка по горизонтали, после чего его персонаж попадёт в координату $$$(i, j + 1)$$$ в конце секунды,
  • либо Тёма может не совершать гиперпрыжок, тогда его персонаж не будет перемещаться в течение этой секунды.

Пришельцы, что обитают на этой планете очень опасны и настроены враждебно. Поэтому они будут стрелять из своих рельсотронов $$$r$$$ раз.

Каждый выстрел полностью простреливает одну координату по вертикали или горизонтали. Если в момент выстрела (в конце секунды) персонаж находится в зоне его поражения, то он умирает.

Так как Тёма посмотрел исходный код игры, он знает полную информацию о каждом выстреле — время, простреливаемую координату, а также направление выстрела.

За какое минимальное время персонаж может добраться до нужной точки? Если он обречён на смерть и не сможет добраться до точки с координатами $$$(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$$$ при $$$d = 1$$$, $$$0 \le coord \le m$$$ при $$$d = 2$$$).

Cумма произведений $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

Выходные данные

Для каждого набора входных данных выведите единственное число — минимальное время, за которое персонаж сможет добраться до координаты $$$(n, m)$$$, либо же $$$-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
Выходные данные
5
-1
3
6
10
Примечание

В первом наборе входных данных персонаж может перемещаться следующим образом: $$$(0, 0) \rightarrow (0, 1) \rightarrow (0, 2) \rightarrow (0, 3) \rightarrow (0, 3) \rightarrow (1, 3)$$$.

Во втором примере входных данных персонаж не сможет выйти за пределы прямоугольника, который будет полностью простреливаться выстрелами на $$$2$$$ секунде.