Їдальня

У відомій компанії працюють співробітники двох типів: екстраверти та інтроверти. Ці дві категорії людей відрізняються у багатьох аспектах, і в цій задачі розглядається відмінність їхньої поведінки під час обіду.

Їдальня цієї компанії представлена у вигляді прямокутної сітки розміром N \times M. Іншими словами, у кожній точці з цілими координатами $x,y$ (0 \leq x \leq N, 0 \leq y \leq M) розташований стіл. Кожен стіл призначений для однієї людини.

(Евклідова) відстань між точками (x_1, y_1) та (x_2, y_2) обчислюється як \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}.

Коли інтроверт приходить у їдальню, він вибирає вільний стіл так, щоб мінімальна відстань до найближчого зайнятого столу була якомога більшою. Якщо є кілька столів з однаковою максимальною мінімальною відстанню, він обирає той, у якого координата $x$ найменша. Якщо таких ще кілька, обирає той, у якого координата $y$ найменша.

Коли екстраверт приходить у їдальню, він вибирає вільний стіл так, щоб максимальна відстань до найдальшого зайнятого столу була якомога меншою. Якщо є кілька столів з однаковою мінімальною максимальною відстанню, він обирає той, у якого координата $x$ найменша. Якщо таких ще кілька, обирає той, у якого координата $y$ найменша.

Вам задано розміри їдальні та опис $Q$ подій. Кожна подія — це або прихід, або вихід людини. Для кожного приходу потрібно визначити, який стіл вона займе.