28834번 - Минное поле 다국어

Сегодня Аквамен решил заняться разминированием старого минного поля времен Второй мировой войны. Поле состоит из $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>>, если такой клетки нет.