U školi je organizovan turnir u plivanju. Mali Kosta se prijavio sa namerom da pobedi
u disciplini kraul. Turnir je bio organizovan u okviru nekoliko trka i posle svake trke
znamo ko je bio prvi, drugi i treći. Na kraju se samo ovi rezultati uzimaju u obzir pri
određivanju šampiona, tako što prvo mesto nosi A bodova, drugo mesto nosi B, dok treće
mesto nosi C bodova. Sumiraju se bodovi za svakog takmičara i takmičar koji ima najviše
bodova je šampion. Kako bodove sabira Kostin najbolji drugar iz klupe, on želi da odredi
takav način bodovanja - da Kosta bude šampion ove godine.
Na takmičenje se prijavilo n učenika, pri čemu Kosta nosi kapicu sa rednim brojem
jedan. Turnir se odvija u okviru m trka i za svaku od trka se znaju trojica prvoplasiranih.
Maksimalan broj bodova za prvo mesto je p, dok je minimalan broj bodova za treće mesto 1
(p ≥ A > B > C ≥ 1). Broj bodova za drugo mesto mora biti strogo manji od broja bodova
za prvo mesto i takođe broj bodova za treće mesto mora biti strogo manji od broja bodova
za drugo mesto. Ukoliko je moguće, odrediti prirodne brojeve A, B i C, tako da je broj
bodova koje je Kosta osvojio veći ili jednak broju bodova bilo kog drugog takmičara.
Ulaz:
(Ulazni podaci se nalaze u datoteci plivanje.in) U prvom redu ulazne datoteke se
nalaze tri prirodna broja: n, m i p. Broj n predstavlja broj takmičara (plivača), a m je
ukupan broj trka. Broj p je maksimalan broj bodova koje neki takmičar može da osvoji u
jednoj trci. U svakom od sledećih m redova data su tri različita prirodna broja između
1 i n, koji predstavljaju redne brojeva takmičara koji su trku završili na prvom, drugom
i trećem mestu.
Izlaz:
(Izlazne podatke upisati u datoteku vlada.out) U prvom i jedinom redu štampati
brojeve A, B i C, razdvojene razmakom. U slučaju da postoji više rešenja, štampati
bilo koje od njih. Ukoliko rešenje ne postoji, štampati -1.
Ograničenja:
- 3 ≤ n ≤ 1000
- 1 ≤ m ≤ 20000
- 1 ≤ p ≤ 50
- vremensko ograničenje za izvršavanje programa je 1 s.
Primer 1:
plivanje.in
|
|
plivanje.out
|
3 5 10
1 3 2
3 1 2
1 2 3
3 1 2
3 1 2
|
|
10 8 2
|
Objašnjenje:
Kosta je bio dva puta prvi i tri puta drugoplasirani na turniru. Ako se za
prvo mesto dobija 10 bodova, za drugo 8, a za treće 2 boda, tada će takmičari imati redom
20 + 24 + 0 = 44, 0 + 8 + 8 = 16 i 30 + 8 + 2 = 40 bodova, pa je šampion Kosta sa rednim brojem
jedan.
Primer 2:
plivanje.in
|
|
plivanje.out
|
5 7 5
1 4 2
2 3 4
5 3 2
3 2 1
4 1 2
1 3 2
2 1 4
|
|
5 4 1
|
Primer 3:
plivanje.in
|
|
plivanje.out
|
8 4 4
3 8 1
2 7 3
2 1 6
5 4 1
|
|
-1
|
Objašnjenje:
lj
Ako se za prvo mesto dobija 3 boda, za drugo mesto 2 i za treće 1 bod - onda
će takmičar broj 2 imati 6 bodova, a Kosta 4 boda. Ako se za prvo mesto dobija 4 boda,
tada će takmičar sa rednim brojem 2 imati 8 bodova, a Kosta najviše 3 + 4 = 7 bodova. Ni
u jednom slučaja Kosta ne može da pobedi.