Elektrik Ehtiyacları#3749
Şəhərinizdə yeni bir zavod tikməyi planlaşdırırsınız. Elektrik ehtiyaclarınız böyük olduğundan, zavodun elektrik stansiyasına yaxın yerləşdirilməsi vacibdir. Mümkün yerlərin prioritetləşdirilmiş siyahısını qurmaq istəyirsiniz.
Zavodun yerləşdirilməsi lazım olan ərazi N sətir və M sütunlu hüceyrələrdən ibarət düzbucaqlı şəbəkə kimi təsvir edilə bilər. Bu hüceyrələrdən bəzilərində elektrik stansiyası var. Yeni zavod dəqiq bir hüceyrəni tutur və hər hansı boş hüceyrədə (yəni elektrik stansiyası olmayan hər hansı hüceyrədə) yerləşdirilə bilər.
Sətirləri 1-dən N-ə və sütunları 1-dən M-ə qədər nömrələyərək, hüceyrənin yeri iki tam ədədlə təsvir edilə bilər. Hüceyrə (i, j) i sətirində və j sütununda olan hüceyrədir. Hüceyrə (i_0, j_0) ilə hüceyrə (i_1, j_1) arasındakı məsafə max(|i_0 − i_1|, |j_0 − j_1|) olaraq hesablanır, burada |x| x-in mütləq dəyərini təmsil edir. Bir yerin elektrik prioriteti onun elektrik stansiyasına minimum məsafəsidir.
Bunu nəzərə alaraq, bütün mümkün yerləri ardıcıl olaraq 1-dən başlayaraq nömrələyəcəksiniz. Onları elektrik prioritetinin artan sırasına görə nömrələyəcəksiniz. Eyni elektrik prioritetinə malik yerlər arasında, onları sətir nömrələrinin artan sırasına görə nömrələyəcəksiniz. Eyni elektrik prioriteti və sətir nömrəsinə malik yerlər arasında, onları sütun nömrələrinin artan sırasına görə sıralayacaqsınız.
Aşağıdakı şəkildə 4×7 şəbəkəni görə bilərsiniz. Qara hüceyrələr elektrik stansiyası olan hüceyrələrdir. Tünd boz hüceyrələrin elektrik prioriteti 1, açıq boz hüceyrələrin elektrik prioriteti 2 və ağ hüceyrələrin elektrik prioriteti 3-dür. Hər bir hüceyrənin içindəki nömrə sizin tərəfindən yerə təyin edilmiş nömrədir.
Siz qurulmuş prioritetləşdirilmiş siyahı ilə bağlı bir neçə sorğu alacaqsınız. Hər bir sorğuda sizə prioritetləşdirilmiş siyahıdakı mövqeyi təmsil edən bir nömrə veriləcək və sizə həmin mövqeyə təyin edilmiş yerin hansı olduğunu hesablamaq tapşırılacaq.
Hər bir test halı bir neçə sətirdə verilir. Birinci sətir şəbəkənin sətir və sütunlarının sayını (1 ≤ N, M ≤ 10^9) və mövcud elektrik stansiyalarının sayını (1 ≤ P ≤ 20) təmsil edən üç tam ədəd N, M və P ehtiva edir. Növbəti P sətir hər biri elektrik stansiyasının yerini təmsil edən iki tam ədəd R və C ehtiva edir (1 ≤ R ≤ N və 1 ≤ C ≤ M). Hər bir test halında, bütün elektrik stansiyası yerləri fərqlidir. Növbəti sətir sorğuların sayını təmsil edən tək tam ədəd Q ehtiva edir (1 ≤ Q ≤ 50). Sonra Q tam ədəd p_1, ..., p_Q təmsil edən bir sətir gəlir, bunlar prioritetləşdirilmiş siyahıdakı mövqeləri təmsil edir (1 ≤ p_i ≤ N×M−P).
Son test halı üç sıfır ehtiva edən bir sətirlə tamamlanır.
Hər bir test halı üçün Q+1 sətir çıxış edin. İlk Q sətirin i-ci sətiri verilmiş p_i nömrəsinə təyin edilmiş yerin sətir və sütun nömrələrini təmsil edən iki tam ədəd ehtiva etməlidir. Hər bir test halı üçün son sətir tək '-' (tire) simvolunu ehtiva etməlidir.
Nümunə 1