eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Amin and Emil play game

Amin and Emil play game

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

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

####Входные данныеВ первой строке даны три целых числа n,m и q — размеры поля и количество запросов (1 <= n,m <= 2000;1 <= q <= 10^6 ). В следующих строках даны запросы. Каждый запрос начинается с символа, а затем идут два целых числа x[i] и y[i] (1 <= x[i]<= n, 1 <= y[i] <= m). Если символ равен «c», это означает, что Амин выкопал бомбу в клетке (x[i],y[i]). Гарантируется, что он выкапывает бомбу в каждой клетке не более одного раза. Иначе, Амин просит Эмиля найти ближайшую к клетке (x[i] , y[i] ) клетку, в которой еще есть бомба, в выбранном направлении . Если символ равен «u», то направление — вверх, если символ — «d», направление — вниз, если символ — «l», направление — влево, и если символ — «r», направление — вправо.

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

Пример

Входные данные #1
3 4 6
u 2 3
c 2 4
r 2 4
c 2 3
l 2 4
d 1 3
Выходные данные #1
1 3
-1
2 2
3 3
Источник 2 февраля 2019 года. Личная олимпиада. Условия по фильму «Аквамен» , CoronaVirus GrandPrix 2020 Round 2