Центральна кав'ярня#2285

Центральна кав'ярня

15 секунд

256 мегабайтів

Легка

Це просто примха чи новий тренд? Ви не впевнені, але кількість кав'ярень, що постійно зростає у вашому рідному місті, безперечно привертає увагу. Схоже, що люди настільки підсіли на каву, що квартири неподалік від багатьох кав'ярень здаються за вищу орендну плату.

Це привернуло увагу місцевої ріелторської компанії. Вони зацікавлені у визначенні найвигідніших розташувань у місті з точки зору близькості до багатьох кав'ярень. Вам надана карта міста з нанесеними на неї всіма кав'ярнями. Припускаючи, що пересічна людина готова пройти лише певну фіксовану кількість кварталів за ранковою кавою, потрібно знайти таке місце, з якого можна дістатися до максимальної кількості кав'ярень.

Як ви, мабуть, знаєте, ваше рідне місто побудоване на прямокутній сітці з кварталами, вирівняними по осях північ-південь та схід-захід. Оскільки дозволено ходити лише вулицями, відстань між перехрестями $(a, b)$ та $(c, d)$ дорівнює $∣ a - c ∣ + ∣ b - d ∣$ |a - c| + |b - d|.

Вхідні дані

Вхід містить кілька тестових випадків. Кожен тестовий випадок описує місто. У першому рядку кожного тесту чотири цілі числа $d x$ , $d y$ , $n$ та $q$ . Вони задають розміри сітки $d x \times d y$ dx \times dy ( $1 \leq d x, d y \leq 1000$ 1 \le dx, dy \le 1000), кількість кав'ярень $n$ ( $0 \leq n \leq 5 \cdot 1 0^{5}$ 0 \le n \le 5 \cdot 10^5) та кількість запитів $q$ ( $1 \leq q \leq 20$ 1 \le q \le 20). Кожен з наступних $n$ рядків містить два цілі числа $x_{i}$ x_i та $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), що задають координати $i$ -ї кав'ярні. На кожному перехресті може бути не більше однієї кав'ярні. Далі у кожному з наступних $q$ рядків задано одне ціле число $m$ ( $0 \leq m \leq 1 0^{6}$ 0 \le m \le 10^6) — максимальна відстань, на яку людина готова йти за кавою.

Останній тестовий випадок завершено рядком, що містить чотири нулі.

Вихідні дані

Для кожного тесту виведіть його номер. Для кожного запиту виведіть рядок із максимальною кількістю кав'ярень, до яких можна дістатися на відстані не більше $m$ , та координатами оптимального розташування. Наприклад, у зразку $3$ кав'ярні знаходяться в межах відстані $1$ від оптимального розташування $(3, 4)$ , $4$ кав'ярні — в межах відстані $2$ від оптимального розташування $(2, 2)$ , а $5$ кав'ярень — в межах відстані $4$ від оптимального розташування $(3, 1)$ . Якщо існує кілька оптимальних точок, вибирайте найпівденнішу (з найменшою додатною $y$ -координатою). Якщо все ще буде нічия, вибирайте найдальшу на захід (з найменшою додатною $x$ -координатою).

Дотримуйтесь формату зразку виводу.

Приклади

Приклад 1