Ваш дачный участок представляет собой прямоугольное пространство огороженное забором по периметру. Дачный участок разбит на квадратные зоны размера 1 × 1 в n горизонтальных и $$$m$$$ вертикальных рядов.
В центре некоторых квадратных зон растет 4 одинаковых стебля малины длиной $$$l_{ij}$$$. Вы хотите подвязать как можно больше стеблей, вырвав остальные. Чтобы подвязать стебель, вы можете протянуть его вдоль земли до забора и привязать к нему. Стеблю должно хватать длины. Протягивать можно только параллельно сторонам забора.
Каждый протянутый стебель занимает все зоны на пути от себя до забора и четверть своей зоны как показано на рисунке (занятое пространство каждым стеблем указано отдельным цветом):
Никакие два стебля не могут занимать одно и то же пространство. То есть для каждой зоны со стеблями вы потенциально можете подвязать любое количество стеблей от 0 до 4, но никакие два из них не могут идти в одном направлении.
Ниже указано три примера, где пространства, занятые стеблями, пересекаются. Такие подвязывания некорректны.
Подвяжите как можно больше стеблей и выведите какие именно из них и как надо привязать.
Первая строка входных данных содержит единственное целое число $$$t$$$ $$$(1 \le t \le 10^3)$$$ — количество наборов входных данных. Описание наборов входных данных следует ниже.
Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$s$$$ $$$(1 \le n, m \le 10^6, 1 \le s \le min(10^5, n \cdot m))$$$ — размер участка и количество зон со стеблями.
Следующие s строк содержат по 3 целых числа $$$r_i$$$, $$$c_i$$$, $$$l_i$$$ $$$(1 \le r_i \le n, 1 \le c_i \le m, 1 \le l_i \le 10^6)$$$ — строку, столбец и длину $$$i$$$-го набора стеблей. Гарантируется, что каждая пара $$$(r_i, c_i)$$$ встречается в наборе входных данных не более раза.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$10^6$$$, сумма $$$s$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных первая строка должна содержать ответ $$$t$$$ — максимальное количество подвязанных стеблей. Следующие $$$t$$$ строк должны содержать описание подвязанных стеблей в следующем формате:
В строке должно содержаться два целых числа $$$r_j$$$, $$$c_j$$$ — координаты зоны стебля — и литера $$$d_j \in \{«$$$u$$$», «$$$r$$$», «$$$d$$$», «$$$l$$$»\}$$$, обозначающая направление подвязывания (в соответствии с пояснением на рисунке в условии выше).
Если решений несколько, выведите любое.
В этой задаче каждый тест оценивается независимо. Все тесты можно разделить на следующие группы:
| Группа | Макс. балл | Доп. ограничения | Комментарий |
| $$$n, m$$$ | |||
| $$$0$$$ | $$$0$$$ | — | Тесты из условия |
| $$$1$$$ | $$$5$$$ | $$$n \le 1$$$ | |
| $$$2$$$ | $$$10$$$ | $$$n \le 2$$$ | |
| $$$3$$$ | $$$10$$$ | $$$n \le 3$$$ | |
| $$$4$$$ | $$$10$$$ | $$$n \cdot m \le 40$$$ | |
| $$$5$$$ | $$$5$$$ | — | Комментарий$$$^1$$$ |
| $$$6$$$ | $$$20$$$ | $$$n \cdot m \le 1$$$ $$$000$$$ | |
| $$$7$$$ | $$$40$$$ | — |
Баллы начисляются за прохождение каждого теста.
Комментарий$$$^1$$$: Для каждой зоны со стеблями гарантируется, что до забора можно дотянуться не более чем в одном из 4 направлений.
2 4 5 1 2 4 9 8 8 6 2 5 5 2 7 7 2 8 1 3 5 4 4 6 5 5 3 1
4 2 4 u 2 4 d 2 4 r 2 4 l 7 2 5 u 2 7 u 4 6 d 2 8 r 2 5 l 4 6 u 2 7 d
Первый тестовый случай изображен в условии.
Решение для второго тестового случая изображено ниже.
Обратите внимание, что полностью удаленные стебли не мешают протягиванию стеблей через их зону. Так, например, стебель 2 8 r можно заменить на 2 7 r, и решение останется корректным. Существуют также другие варианты решения этого тестового случая.
