C. Минное поле
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня Аквамен решил заняться разминированием старого минного поля времен Второй мировой войны. Поле состоит из $$$n$$$ строк и $$$m$$$ столбцов квадратных клеток, в каждой из которых изначально закопана мина. Будем обозначать клетку на пересечении $$$x$$$-й строки и $$$y$$$-го столбца как $$$(x, y)$$$. Так как работа по извлечению мин довольно утомительна, Аквамен будет иногда задавать вам вопросы следующего вида. Артур говорит вам клетку $$$(x, y)$$$ и одно из четырех направлений (вверх, вниз, влево, вправо) и просит найти ближайшую к $$$(x, y)$$$ клетку в выбранном направлении, в которой еще есть мина, либо сказать, что такой клетки нет.

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

В первой строке даны три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ — размеры поля и количество запросов ($$$1 \le n, m \le 2\,000$$$; $$$1 \le q \le 10^6$$$). В следующих строках даны запросы. Каждый запрос начинается с символа, а затем идут два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$). Если символ равен «c», это означает, что Артур выкопал мину в клетке $$$(x_i, y_i)$$$. Гарантируется, что он выкапывает мину в каждой клетке не более одного раза. Иначе, Аквамен просит вас найти ближайшую к клетке $$$(x_i, y_i)$$$ клетку, в которой еще есть мина, в выбранном направлении. Если символ равен «u», то направление — вверх, если символ — «d», направление — вниз, если символ — «l», направление — влево, и если символ — «r», направление — вправо.

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

На каждый вопрос выведите искомую клетку, или «-1», если такой клетки нет.

Система оценки

Эта задача состоит из трехподзадач. Для некоторых подзадач выполняются дополнительные ограничения, указанные в таблице ниже. Для получения баллов за подзадачу необходимо пройти все тесты данной подзадачи, а также все тесты всех необходимых подзадач. Необходимые подзадачи также указаны в таблице.

|c|}

Подзадача

БаллыОграничения Необходимые подзадачи
159$$$n, m \le 100$$$; $$$q \le 10^4$$$
219Все запросы на выкапывание бомб идут до всех запросов на нахождение клетки
322Без дополнительных ограничений1,2
Пример
Входные данные
3 4 6
u 2 3
c 2 4
r 2 4
c 2 3
l 2 4
d 1 3
Выходные данные
1 3
-1
2 2
3 3