Strażnicy

Limit pamięci: 128 MB

Bajtazar przyłączył się do ruchu oporu sprzeciwiającego się złemu Imperatorowi okupującemu Bajtocję. Jako że jest drobny i zwinny, został wybrany do wykonania misji polegającej na wykradzeniu z Pałacu Imperialnego tajnych planów Imperatora. Długo przemyśliwał, jak można się dostać do wnętrza Pałacu, i uznał, że najprościej będzie przejść przez kanały burzowe i ściekowe.

Niestety, po zebraniu informacji odkrył, że system kanałów miejskich jest odgrodzony mocnymi kratami od kanałów biegnących pod Pałacem. Postanowił więc, że przemknie się pod pierwszą linią straży kanałami miejskimi, wyjdzie na powierzchnię przez studzienkę na Placu Imperialnym (olbrzymim dziedzińcu samego Pałacu) i następnie przez inną studzienkę na Placu zejdzie z powrotem do kanałów, ale tym razem już po dobrej stronie kraty.

Plac Imperialny patrolowany jest przez strażników. Każdy strażnik patroluje odcinek łączący dwa punkty. Ruchem jednostajnym podąża z punktu do punktu , tam wykonuje zwrot w tył (natychmiastowo, czyli bez rozglądania się dookoła), a następnie idzie z punktu do punktu , wykonuje zwrot w tył, po czym czynność powtarza. Imperator, by osiągnąć wrażenie sprawnej i wydajnej (choć niekoniecznie sensownej) musztry, nakazał, by wszyscy strażnicy wykonywali zwroty w tych samych momentach, co minutę (co oznacza, że każdy strażnik porusza się z prędkością na minutę, gdzie to długość odcinka, który patroluje).

Bajtazar zna odcinki patrolowane przez wszystkich strażników. Sam skrada się w tempie bajtockich stóp na minutę. Na misję wyrusza w specjalnym czarnym płaszczu, który powoduje, że gdy stoi w miejscu, to strażnicy nie mają szans go dostrzec. Niestety, gdy spróbuje się poruszyć, będąc w polu widzenia jakiegokolwiek strażnika, zostanie spostrzeżony, a wkrótce potem złapany. W szczególności, Bajtazar nie może wyjść ze studzienki, ani wejść do studzienki, jeśli ta znajduje się w polu widzenia jakiegoś strażnika. Strażnicy mają nieskończony zasięg wzroku, natomiast nie mają oczu z tyłu głowy, w wyniku czego widzą wyłącznie to, co znajduje się w domkniętym kącie znajdującym się przed nimi. Można założyć, że Plac Imperialny jest nieskończenie wielki.

Bajtazar nie jest całkiem pewien, czy niektóre studzienki nie zostały ostatnimi czasy zamurowane. Dlatego, dla zwiększenia szans powodzenia misji, chciałby dla każdej studzienki, przez którą może wyjść z kanałów miejskich, policzyć, do ilu różnych studzienek prowadzących do kanałów pałacowych jest w stanie z niej dojść. Sam niestety nie daje sobie z tym rady z powodu olbrzymiej liczby studzienek, więc prosi Cię o pomoc.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , oraz (), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio liczby strażników, studzienek prowadzących do kanałów miejskich i studzienek prowadzących do kanałów pałacowych.

W następnych wierszach opisane są odcinki patrolowane przez poszczególnych strażników. W pojedynczym wierszu znajdują się cztery liczby całkowite , pooddzielane pojedynczymi odstępami: , oznaczające, że strażnik patroluje odcinek od do . Początkowo strażnik znajduje się w i patrzy w kierunku . Układ współrzędnych dobrany jest tak, że od punktu do punktu jest jedna stopa bajtocka.

W kolejnych wierszach są opisane położenia studzienek. W każdym z tych wierszy znajdują się dwie liczby całkowite i , oddzielone pojedynczym odstępem: , oznaczające, że studzienka znajduje się w punkcie . Pierwsze wierszy określa położenia studzienek łączących się z kanałami miejskimi, następne wierszy - położenia studzienek łączących się z kanałami pałacowymi.

Można założyć, że testy są skonstruowane tak, że odpowiedź nie zmieniłaby się, gdyby każdą studzienkę przesunąć o nie więcej niż stopy bajtockiej.

Wyjście

Na standardowe wyjście należy wypisać wierszy. W -tym z nich powinna znajdować się jedna liczba całkowita, określająca do ilu studzienek łączących się z kanałami pałacowymi da się dojść ze studzienki, która na wejściu była podana jako -ta.

Przykład

Dla danych wejściowych:

3 2 2
-3 4 7 -6
6 4 5 4
6 4 6 5
4 0
5 6
5 8
7 4

poprawną odpowiedzią jest:

0
2

Wyjaśnienie do przykładu: Pierwsza studzienka jest, niefortunnie, cały czas w zasięgu wzroku któregoś ze strażników - gdy tylko trzeci strażnik odwróci się do niej tyłem, to drugi właśnie zaczyna na nią patrzeć.

Z drugiej studzienki da się dojść do obydwu studzienek prowadzących do pałacu. Aby dojść do pierwszej z nich, wystarczy poczekać minutę i 42 sekundy, aż pierwszy strażnik przestanie widzieć studzienkę (strażnicy drugi i trzeci stracą ją z oczu wcześniej), i spokojnie w 18 sekund przebiec do studzienki .

Aby dotrzeć do studzienki , trzeba napracować się ciut bardziej. Ponownie wychodzimy ze studzienki po 102 sekundach i te 18 sekund, które mamy, zanim strażnicy obrócą się i nas zobaczą, wykorzystujemy na przemknięcie do punktu . Tam przyczajamy się na 30 sekund, a potem możemy swobodnie przebiec do studzienki .

Autor zadania: Jakub Onufry Wojtaszczyk.