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

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

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

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

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