Їдальня
У відомій компанії працюють два типи працівників: екстраверти та інтроверти. Ці типи людей відрізняються багатьма аспектами, і в цій задачі ми зосередимося на їх поведінці під час обіду.
Їдальню компанії можна уявити як прямокутну сітку розміром N×M. Це означає, що кожна точка з цілими координатами x, y (0 ≤ x ≤ N, 0 ≤ y ≤ M) представляє стіл. Кожен стіл розрахований на одну особу.
Відстань між точками з координатами (x_1, y_1) та (x_2, y_2) визначається як Евклідова відстань.
Коли інтроверт приходить до їдальні, він обирає вільний стіл так, щоб мінімальна відстань до найближчого зайнятого столу була максимальною. Якщо є кілька столів з однаковою найбільшою мінімальною відстанню, він обирає той, у якого найменша координата x. Якщо таких столів кілька, він обирає той, у якого найменша координата y.
Коли екстраверт приходить до їдальні, він обирає вільний стіл так, щоб максимальна відстань до найдальшого зайнятого столу була мінімальною. Якщо є кілька столів з однаковою найменшою максимальною відстанню, він обирає той, у якого найменша координата x. Якщо таких столів кілька, він обирає той, у якого найменша координата y.
Вам надано розмір їдальні та опис Q подій. Кожна подія - це або прибуття, або відбуття однієї особи. Для кожного прибуття ви повинні визначити стіл, який вона займе.
Вхідні дані
Перша строка містить три цілі числа N, M, Q, розділені пробілами (1 ≤ N, M ≤ 5000, 0 ≤ Q ≤ 100). Наступні Q рядків описують події. Якщо i-та подія - це прибуття екстраверта, i-й рядок містить слово "ext"; якщо подія - це прибуття інтроверта, рядок містить слово "int"; якщо подія - це відбуття, рядок містить 1-базовий індекс (серед усіх подій) події, що описує прибуття цієї особи.
Гарантується, що вхідні дані коректні: для кожної прибуваючої особи є принаймні один вільний стіл у їдальні на момент її прибуття, і для кожної події відбуття індекс, зазначений у рядку, відповідає події прибуття, і особа, яка прибула в цій події, все ще знаходиться в їдальні.
Вихідні дані
Для кожного прибуття виведіть рядок з двома цілими числами, розділеними пробілом, - координати столу, який займається.