Mərkəzi kafe#2285

Mərkəzi kafe

15 saniyə

256 meqabayt

Asan

Bu sadəcə dəbdirmi, yoxsa qalıcıdır? Əmin deyilsiniz, lakin doğma şəhərinizdə açılan qəhvə dükanlarının sayının getdikcə artması həqiqətən də böyük maraq doğurur. Görünür, insanlar qəhvəyə o qədər aludə olublar ki, bir çox qəhvə dükanına yaxın olan mənzillər daha baha icarəyə verilir.

Bunu yerli daşınmaz əmlak şirkəti də nəzərə alıb. Onlar şəhərdə ən qiymətli yerləri, yəni ən çox qəhvə dükanına yaxın olan yerləri müəyyən etmək istəyirlər. Sizə qəhvə dükanlarının qeyd olunduğu şəhər xəritəsi verilib. Tutaq ki, orta hesabla bir insan səhər qəhvəsi üçün yalnız müəyyən sayda kvartal məsafə piyada gedə bilər; belə olduqda, siz elə bir nöqtə tapmalısınız ki, oradan ən çox sayda qəhvə dükanına çatmaq mümkün olsun.

Yəqin bilirsiniz, doğma şəhəriniz düzbucaqlı şəbəkə üzrə inşa olunub, kvartallar şimal-cənub və şərq-qərb oxları boyunca yerləşir. Piyada yalnız küçələr boyunca hərəkətə icazə verildiyindən, $(a, b)$ və $(c, d)$ kəsişmələri arasındakı məsafə $∣ a - c ∣ + ∣ b - d ∣$ |a - c| + |b - d| olur.

Giriş

Giriş bir neçə testdən ibarətdir. Hər bir test bir şəhəri təsvir edir. Hər bir testin ilk sətrində dörd tam ədəd $d x$ , $d y$ , $n$ və $q$ verilir. Bunlar, grid ölçülərini $d x \times d y$ dx \times dy ( $1 \leq d x, d y \leq 1000$ 1 \le dx, dy \le 1000), qəhvə dükanlarının sayını $n$ ( $0 \leq n \leq 5 \cdot 1 0^{5}$ 0 \le n \le 5 \cdot 10^5), sorğuların sayını isə $q$ ( $1 \leq q \leq 20$ 1 \le q \le 20) göstərir. Növbəti $n$ sətrin hər birində iki tam ədəd $x_{i}$ x_i və $y_{i}$ y_i ( $1 \leq x_{i} \leq d x$ 1 \le x_i \le dx, $1 \leq y_{i} \leq d y$ 1 \le y_i \le dy) verilir, hansı ki, $i$ -ci qəhvə dükanının koordinatlarını göstərir. Hər kəsişmədə maksimum bir qəhvə dükanı ola bilər. Sonra $q$ sətrin hər birində bir tam ədəd $m$ ( $0 \leq m \leq 1 0^{6}$ 0 \le m \le 10^6) verilir – insanın qəhvə üçün piyada getməsi üçün maksimum məsafə.

Son testdən sonra sətrin dördü sıfır olan bir sətir verilir.

Çıxış

Hər bir test üçün testin nömrəsini çap edin. Hər bir sorğu üçün, verilmiş $m$ məsafəsi daxilində çatmaq mümkün olan maksimal qəhvə dükanı sayını və optimal yerin koordinatlarını çap edin. Məsələn, nümunədə optimal $(3, 4)$ yerindən $1$ məsafədə $3$ qəhvə dükanı, $(2, 2)$ yerindən $2$ məsafədə $4$ qəhvə dükanı, $(3, 1)$ yerindən $4$ məsafədə isə $5$ qəhvə dükanı vardır. Əgər bir neçə optimal yer varsa, ən cənubdakı (ən kiçik $y$ -koordinatı olan) seçilməlidir. Əgər hələ də bərabərlik varsa, ən qərbdəki (ən kiçik $x$ -koordinatı olan) seçilməlidir.

Nümunə çıxışdakı formata riayət edin.

Nümunələr

Nümunə 1