Codah ClubВежбај. Испрати. Напредувај.
Најави се
Македонски
#0006AF

Ostrva - Izborno

Kapetan Mika ima zadatak da napravi mapu arhipelaga koji se sastoji od n ostrva. Na raspolaganju ima mali brod i hrabru posadu. On se odlučio za sledeću taktiku: za svaka dva različita ostrva A i B , on će se pravolinijski uputiti od ostrva A do ostrva B, izbrojaće koliko se ostalih ostrva nalazi sa desne strane putanje broda i pribeležiće to. Ostrvo se nalazi sa desne strane putanje ako pripada desnoj poluravni (polumoru) određenoj pravom AB. Smer je, naravno, bitan - ako je neko ostrvo sa desne strane putanje od A do B, onda je ono sa leve strane putanje od B do A.


Napomenimo da ne postoje tri kolinearna ostrva, tj. pri pomenutim pravolinijskim putanjama između dva ostrva brod nikad neće naleteti na neko treće ostrvo. Takođe napomenimo da nije poznato kako kapetanove beleške pomažu pri pravljenju mape.


Posle svih putovanja, kapetan Mika se zagledao u svoje beleške i pokušao na osnovu njih da odgovori na k pitanja tipa: "kada sam putovao od ostrva A do ostrva B, da li mi je ostrvo C bilo sa desne strane?", ali nije uspeo. Možete li mu pomoći?


InputU prvom redu standardnog ulaza nalazi se jedan prirodan broj n - broj ostrva u arhipelagu. Zatim se u narednih n redova (3 ≤ n ≤ 200) nalaze po n celih brojeva - opis matrice a koja predstavlja Mikine beleške. aij označava broj ostrva sa desne strane pri putovanju od ostrva i do ostrva j (ostrva su numerisana brojevima od 1 do n). Elementi na glavnoj dijagonali matrice a će uvek biti 0. U narednom redu standardnog ulaza nalazi se broj k - broj Mikinih upita (1 ≤ k ≤ 10^5). Najzad, u sledećih k redova se nalaze po 3 cela broja A, B i [] (1 ≤ A, B, C ≤ n, A ≠ B ≠ C ≠ A) koji predstavljaju pitanje: da li je ostrvo C sa desne strane putanje od ostrva A do ostrva B?

OutputZa svaki od k upita je potrebno odgovoriti sa ’DA’ ili ’NE’ (bez navodnika), zavisno od toga da li je odgovarajuće ostrvo sa prave strane. Na pitanja odgovarati u datom redosledu, pri čemu svaki odgovor treba biti ispisan u posebnom redu standardnog izlaza.

Ulaz:
[c]3
0 1 0
0 0 1
1 0 0
2
1 2 3
1 3 2
Izlaz:
DA
NE
Objašnjenje: Kako se sa desne strane puta od ostrva 1 do ostrva 2 nalazi jedno ostrvo (a12 = 1) i kako imamo samo 3 ostrva, to ostrvo mora biti ostrvo 3, pa je odgovor na prvo pitanje potvrdan. Slično, ostrvo 2 se ne može nalaziti sa desne strane puta od ostrva 1 do ostrva 3.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.