Амін та Еміль грають у гру
Амін та Еміль у Москві грають у карткову гру. Амін має розмінувати старе мінне поле часів Другої світової війни. Ігрове поле складається з 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», якщо такої клітини немає.