Амін та Еміль грають у гру#9778
Амін та Еміль у Бравотауні грають у карткову гру. Амін має розмінувати старе мінне поле часів Другої світової війни. Ігрове поле складається з рядків і стовпців квадратних клітин, у кожній з яких спочатку закопана міна. Позначимо клітину на перетині -го рядка і -го стовпця як (, ). Оскільки робота з вилучення мін досить втомлююча, Амін іноді ставить Емілю питання такого типу. Амін вказує Емілю клітину (, ) і один з чотирьох напрямків (вгору, вниз, вліво, вправо) та просить знайти найближчу до (, ) клітину у вибраному напрямку, в якій ще є міна, або повідомити, що такої клітини немає. Яку найближчу клітину вибере Еміль?
У першому рядку дано три цілі числа , і — розміри поля та кількість запитів (1 \le n, m \le 2000; 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», якщо такої клітини немає.
Приклад 1