AlgoLiga 2018

Północno-zachodnie rejony Bajtocji są wciąż zamieszkiwane przez rdzenną ludność indiańską. Najpotężniejsze plemię Bajtohikanów przejawia ostatnio wrogie zamiary względem równie walecznego plemienia Bitrokezów. W związku z tym naczelny wódz Bitrokezów - Rączy Gigabit nakazał opracowanie szybkiego systemu przekazu informacji pomiędzy wioskami plemienia, na wypadek ataku ze strony Bajtohikanów.

Najmędrsi z plemiennej starszyzny opracowali system, który zapewnia, że wiadomość o zagrożeniu dotrze do wszystkich wiosek. Ustalono, że do przekazu informacji wykorzystana zostanie sprawdzona metoda znaków dymnych. W każdej wiosce przy gotowym do podpalenia stosie stale czuwać będą strażnicy. Jeśli osada stanie w obliczu zagrożenia, strażnicy rozpalą ogień i znakami dymnymi przekażą informację do innych wiosek znajdujących się w pobliżu. Mieszkańcy tych wiosek w taki sam sposób przekażą wiadomość dalej. Strażnicy w poszczególnych wioskach mogą różnić się sprawnością w rozpalaniu ogniska i nadawaniu znaków, dlatego czas potrzebny na przekazanie informacji oraz jej zasięg są wielkościami charakterystycznymi dla każdej osady.

System przewiduje również, że do przekazywania informacji można wykorzystywać posłańców. Jest to metoda, z której należy korzystać tylko wtedy, jeśli dzięki temu informacja szybciej dotrze do jakiejś osady niż za pomocą znaków dymnych. W pewnych sytuacjach może to też być jedyny sposób poinformowania wioski, jeśli ta nie leży w zasięgu znaków dymnych żadnej z pozostałych osad. Posłaniec porusza się na galopującym koniu i na przekazanie wiadomości potrzebuje tyle sekund, ile wynosi odległość pomiędzy wioskami wyrażona w sekundach końskiego galopu (skg), zaokrąglona w dół do liczby całkowitej. Jeśli miałaby zajść sytuacja, że kilku posłańców dociera jednocześnie do tej samej wioski, to jest to bezcelowe - należy wysłać tylko jednego posłańca.

Ponieważ do działania systemu ważne jest też dokładne określenie położenia wszystkich wiosek, starszyzna zadecydowała, aby wykorzystać do tego Pradawną Skałę Bogini Nieba i Ziemi Ataensic, znajdującą się na terenie zamieszkiwanym przez Bitrokezów. Dla każdej wioski obliczono dwie wartości: odległość jaka dzieli ją od Skały (wyrażoną w skg) oraz kierunek w jakim trzeba wyruszyć z osady, aby dojść do Skały. Kierunki oznaczono liczbami od 0 do 359 zaczynając od północy i zgodnie z ruchem Słońca na niebie (0 - północ, 90 - wschód, 180 - południe, 270 - zachód). Każda wioska leży w innym miejscu.

Na podstawie danych dotyczących wiosek oraz wiedząc, która z nich jest zagrożona (czyli rozpoczyna nadawanie informacji) można odpowiedzieć na pytania dotyczące czasu, po jakim wszystkie wioski plemienia zostaną powiadomione oraz ilu posłańców trzeba będzie wykorzystać.

Wejście

W pierwszej linii liczba wiosek Bitrokezów n (2 ≤ n ≤ 1111).
W n kolejnych liniach po cztery liczby całkowite charakteryzujące wioskę: d - odległość wioski od Skały wyrażona w skg (0 < d ≤ 10⁹), k - kierunek z wioski do Skały (0 ≤ k < 360), t - czas (w sekundach) jaki strażnicy potrzebują na nadanie znaków dymnych (0 < t ≤ 10⁶), r - zasięg znaków dymnych wyrażony w skg (0 < r ≤ 10⁹)

Następnie liczba zapytań q (1 ≤ q ≤ 100).
W każdej z kolejnych q linii jedna liczba całkowita w (1 ≤ w ≤ n) oznaczająca numer zagrożonej wioski.

Wyjście

Dla każdego zapytania w osobnej linii dwie liczby całkowite: liczba sekund potrzebnych, aby informacja o zagrożeniu dotarła do wszystkich wiosek oraz liczba posłańców wykorzystanych do przekazania informacji.

Przykład

Wejście:
9
180 180 30 300
300 120 151 240
240 270 130 180
480 210 55 120
360 255 180 240
540 270 20 120
420 135 160 180
600 135 40 60
225 180 100 75
1
1

Wyjście:
341 2

Uwaga: W zadaniu obowiązują dość restrykcyjne limity czasowe.