CS2: Tutun bilan to'sish

De_mirage xaritasining "mid" hududida \(n\) ta dushman ko'rish chizig'i (sightline) bor — bular dushman sizni ko'ra oladigan to'g'ri chiziq segmentlari (masalan, "Palace" dan "Mid"gacha, yoki "Window" orqali).

Sizda oldindan tayyorlangan (lineup) \(m\) ta tutun granatasi otish nuqtasi bor — har biri aniq \((p_x, p_y)\) koordinataga tushadi va radiusi \(R\) bo'lgan doira hosil qiladi.

Bir sightline to'silgan hisoblanadi, agar tutun doirasi shu segment bilan kamida bitta umumiy nuqtaga ega bo'lsa (ya'ni, nuqtadan segmentgacha bo'lgan eng qisqa masofa \(\le R\)).

Sizga qaysi otish nuqtasini tanlash eng ko'p sightline'ni to'sishini aniqlash kerak.

CS2'da "mid" hududidagi tutun granatasi lineup nuqtasi

Kiruvchi ma'lumotlar

Birinchi qatorda uchta butun son \(n\), \(m\) va \(R\) (\(1 \le n, m \le 2000\); \(1 \le R \le 10000\)) — mos ravishda dushman ko'rish chiziqlari (sightlines) soni, tutun tashlash nuqtalari soni va tutun doirasining radiusi.

Keyingi \(n\) ta qatorning har birida to'rtta butun son \(x_1, y_1, x_2, y_2\) (\(-10^4 \le x_1, y_1, x_2, y_2 \le 10^4\)) — har bir dushman ko'rish chizig'i segmentining boshlang'ich va oxirgi nuqtalari koordinatalari beriladi.

Keyingi \(m\) ta qatorning har birida ikkita butun son \(p_x, p_y\) (\(-10^4 \le p_x, p_y \le 10^4\)) — har bir tutun granatasi tushadigan nuqtaning \((x, y)\) koordinatalari beriladi.

Chiquvchi ma'lumotlar

Eng ko'p sightline'ni to'suvchi otish nuqtasining raqamini (\(1-\)indeksli) va u to'sadigan sightline'lar sonini chiqaring (bo'sh joy bilan ajratib). Agar bir nechta nuqta bir xil sondagi sightline'ni to'ssa, eng kichik raqamlisini chiqaring.

Misollar

1

2 2 3
0 0 10 0
0 5 10 5
5 0
5 3

2 2

2

1 2 2
0 0 10 0
5 1
5 5

1 1