I — Biztonsági őrök

Az utóbbi hetekben a Bináris Kaszinót egy helyi bűnözési hullám sújtotta, amely elsősorban a környék kaszinóit érintette. Bár a Bináris Kaszinóban több térfigyelő kamera is működik, a tolvajok általában elég könnyen meg tudnak lépni, mivel szinte senki sem járőrözik a kaszinóban.

Miután a teljes pénteki bevételt ellopták, a Bináris Kaszinó vezetője elvesztve a türelmét úgy döntött, hogy megerősíti a kaszinó biztonságát azzal, hogy felbérel sok-sok biztonsági őrt. Sajnos azonban a kaszinóban senki sem tudta megtervezni, hogy hogyan is kellene az őröket szétosztani a kaszinó teljes területén a maximális biztonság elérése érdekében. A biztonsági őröket így minden rendszer nélkül szórták szét a kaszinóban. Szerencsére a helyzetük megadható a kétdimenziós sík egész koordinátáival.

A biztonsági őrök egyenetlen eloszlása miatt a biztonsági felügyelők nagyon nehezen tudják csak megállapítani egy bűneset bejelentésekor, hogy melyik őr van legközelebb az incidens helyszínéhez. A feladatot a korlátozott mozgástér is nehezíti, hiszen a kaszinó tele van zsúfolva pénznyerő automaták végeláthatatlan soraival. Ez a korlátozás arra kárhoztatja az őröket, hogy az egyik helyszínről a másikra csak kis lépések sorozatán keresztül tudnak eljutni: minden lépésben csak 1-gyel, 0-val vagy –1-gyel tudják változtatni az egyik vagy mindkét koordinátájukat. Két helyszín közötti távolságnak azt a minimális lépésszámot tekintjük, amennyivel egy őr el tud jutni az egyik helyszínről a másikra.

A feladatod, hogy az őrök pozícióinak és néhány biztonsági incidens helyszínének az ismeretében kiszámítsd, hogy mekkora az egyes incidensek helyszínei és az őrök közötti minimális távolság. Ez lehetővé teszi, hogy a biztonsági felügyelők a megfelelő őröket riasszák, és ezáltal jelentősen erősödjön a kaszinó biztonsága.

A bemenet specifikációja

A bemenet első sorában két egész szám, N és Q szerepel (1 ≤ N, Q ≤ 3 · 10⁵). N az őrök számát, Q pedig a biztonsági incidensek számát adja meg. Ezután N sor következik, mindegyikben két egész számmal, X-szel és Y-nal (0 ≤ X, Y ≤ 5000), amelyek egy-egy őr két koordinátáját írják le a kétdimenziós síkban. A következő Q sor mindegyikében szintén két egész szám, A és B szerepel (0 ≤ A, B ≤ 5000), amelyek pedig egy-egy biztonsági incidens koordinátáit adják meg.

A kimenet specifikációja

A Q biztonsági incidens mindegyikére egy sort kell a kimenetre írni, amely az incidens helyszíne és a biztonsági őrök közötti minimális távolságot tartalmazza lépésszámban megadva.