Perica je sasvim slučajno primetio da je jedna banka napravila sledeći previd: za jedan uloženi euro je davala 1.2 dolara, za jedan uloženi dolar je plaćala 0.6 funti, a za jednu uloženu funtu građanin je dobijao 1.45 eura. Perica je proračunao da će, ako promeni 1 euro u dolare, zatim dobijene dolare pretvori u funte, a onda sve dobijene funte u eure dobiti 1.044 eura. To je Perica i iskoristio, uložio 1000 eura i dobio 1044, tj. zaradio dragocenih 44 eura. Međutim, verovatno su i bankari primetili da im nešto ne štima pa su već narednog dana popravili kursnu listu i ova jednostavna konverzija euro-dolar-funta-euro nije donosila dobit. Međutim, kursna lista sadrži i druge valute te nije isključeno da negde ne postoji dobitni lanac. Pomozite Perici da ga nađe.

Ulaz:

Ulazni podaci se nalaze u datoteci kurs.in. U prvom redu je broj kursnih listi i to je ceo broj nl koji nije veći od 5. U sledećim redovima se nalaze opisi tih listi. U prvom redu svakog opisa je broj različitih valuta koji obrazuju tu listu i to je ceo pozitivan broj nv koji nije veći od 100. Valute su numerisane brojevima od 1 do nv. U narednih nv redova je opis jedne valute. Opis jedne valute (recimo da je to valuta broj i) se sastoji od nv mešovitih brojeva, tako da j-ti broj označava koliko se dobija j-te valute ako se uloži jedna jedinica i-te valute.

Izlaz:

U izlaznoj datoteci kurs.out treba ispisati nl redova, a u svakom redu po jedan ceo broj (0 ili 1). U i-tom redu treba upisati ceo broj 1 ako za i-tu kursnu listu postoji dobitni lanac zamena takav da se može ostvariti zarada, a broj 0, ako u i-toj kursnoj listi nema dobitnog lanca. Vodite računa da ne treba štampati dobitni niz konverzija.

Primer:

2
3
1.000 1.200 0.780
0.800 1.000 0.650
1.450 1.520 1.000
3
1.000 1.200 0.680
0.800 1.000 0.650
1.250 1.520 1.000

1
0