Amin and Emil play game
Амин с Эмилем в Москве играют карточную игру . Амин должен разминировать старое - минное поле времен Второй мировой войны.Игровое поле состоит из 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», если такой клетки нет .