Yemək Otağı
Məşhur bir şirkətdə iki növ 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ə biz onların nahar zamanı davranışlarındakı fərqləri nəzərdən keçiririk.
Bu şirkətin yeməkxanası düzbucaqlı bir şəbəkə N×M kimi təsvir edilə bilər. Başqa sözlə, tam ədədi koordinatları x, y (0 ≤ x ≤ N, 0 ≤ y ≤ M) olan hər bir nöqtədə bir masa var. Hər masa bir nəfərlikdir.
Koordinatları (x_1, y_1) və (x_2, y_2) olan nöqtələr arasındakı (Evklid) məsafə bərabərdir.
Bir introvert yeməkxanaya gəldikdə, o, ən yaxın dolu masaya olan minimal məsafənin mümkün qədər böyük olduğu boş masanı seçir. Əgər ən böyük minimal məsafəyə malik bir neçə masa varsa, o, x koordinatı ən kiçik olanı seçir. Əgər hələ də bir neçə masa varsa, o, y koordinatı ən kiçik olanı seçir.
Bir ekstrovert yeməkxanaya gəldikdə, o, ən uzaq dolu masaya olan maksimal məsafənin mümkün qədər kiçik olduğu boş masanı seçir. Əgər ən kiçik maksimal məsafəyə malik bir neçə masa varsa, o, x koordinatı ən kiçik olanı seçir. Əgər hələ də bir neçə masa varsa, o, y koordinatı ən kiçik olanı seçir.
Sizə yeməkxananın ölçüsü və Q hadisənin təsviri verilir. Hər bir hadisə ya bir şəxsin gəlişi, ya da gedişidir. Hər bir gəliş üçün onun oturduğu masanı tapmalısınız.
Giriş verilənləri
Girişin ilk sətri boşluqlarla ayrılmış N, M, Q tam ədədlərini ehtiva edir (1 ≤ N, M ≤ 5000, 0 ≤ Q ≤ 100). Növbəti Q sətir hadisələri təsvir edir. Əgər i-ci hadisə bir ekstrovertin gəlişidirsə, i-ci sətir tək bir "ext" sətirini ehtiva edir; əgər hadisə bir introvertin gəlişidirsə, sətir tək bir "int" sətirini ehtiva edir; əgər hadisə bir şəxsin gedişidirsə, sətir onun gəlişini təsvir edən hadisənin 1-dən başlayan indeksini ehtiva edir.
Giriş məlumatlarının düzgün olduğu təmin edilir, yəni hər gələn insan üçün onun gəlişi anında yeməkxanada ən azı bir boş masa var və hər gediş hadisəsi üçün sətirdə təsvir olunan indeks bir gəliş hadisəsinə uyğundur və bu hadisədə gələn şəxs hələ də yeməkxanadadır.
Çıxış verilənləri
Hər bir gəliş üçün bir sətirdə iki boşluqla ayrılmış tam ədəd yazın - tutulan masanın koordinatları.