Yemək Otağı#2573
Bir məşhur şirkətdə iki tip işçi var: ekstrovertlər və introvertlər. Bu iki insan tipi bir çox cəhətdən fərqlənir və bu məsələdə onların nahar zamanı davranış fərqini nəzərə alacağıq.
Bu şirkətin yeməkxanası N \times M ölçülü düzbucaqlı şəbəkə kimi göstərilib. Başqa sözlə, tam ədədi koordinatlarla olan hər bir nöqtəsində (0 \leq x \leq N, 0 \leq y \leq M) bir masa var. Hər masa bir nəfərlikdir.
(x_1, y_1) və (x_2, y_2) nöqtələri arasındakı (Evklid) məsafə belə hesablanır: \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}.
İntrovert yeməkxanaya daxil olduqda, ən yaxın tutulan masaya mümkün qədər böyük olan minimal məsafə ilə boş masa seçir. Əgər ən böyük minimal məsafəyə malik bir neçə masa varsa, koordinatı ən kiçik olanını seçir. Əgər yenə də bir neçə variant varsa, koordinatı ən kiçik olanı seçir.
Ekstrovert isə yeməkxanaya daxil olduqda, ən uzaq tutulan masaya olan maksimal məsafə mümkün qədər kiçik olan boş masa seçir. Əgər ən kiçik maksimal məsafəyə malik bir neçə masa varsa, koordinatı ən kiçik olanını seçir. Əgər yenə də bir neçə variant varsa, koordinatı ən kiçik olanını seçir.
Sizə yeməkxananın ölçüləri və hadisənin təsviri verilir. Hər hadisə ya bir şəxsin gəlməsi, ya da getməsidir. Hər gəliş üçün onların oturduqları masanın koordinatlarını tapmalısınız.
Birinci sətirdə aralarında boşluq olmaqla , , tam ədədləri verilir (1 \leq N, M \leq 5000, 0 \leq Q \leq 100). Növbəti sətirdə hadisələr təsvir olunur. Əgər -ci hadisə ekstrovertin gəlişidirsə, o sətirdə **ext** yazılır; əgər introvertin gəlişidirsə, **int** yazılır; əgər bu hadisə bir şəxsin çıxışıdırsa, həmin şəxsin gəlişini təsvir edən hadisənin -dən başlayan nömrəsi verilir.
Zəmanət verilir ki, giriş düzgündür: gələn hər bir şəxs üçün həmin an boş masa olur, və çıxış üçün indeks düzgün gəliş hadisəsinə istinad edir və həmin şəxs hələ də yeməkxanadadır.
Hər bir gəliş üçün bir sətirdə iki tam ədəd — tutulan masanın koordinatlarını boşluqla ayrılmış şəkildə çap edin.
Nümunə 1