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:

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:

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:

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.

/*
  DRZAVNO TAKMICENJE 2007
  ZADATAK: plivanje
  AUTOR: Aleksandar Ilic, Nis

  Svaki takmicar je oznacen rednim brojem od 1 do n. Na pocetku ucitamo sve rezultate trka i u matrici a [n][4] pamtimo
  koliko puta je svaki takmicar bio prvi, drugi i treci. Ideja je da prodjemo po svim mogucim brojem poena za
  prvo i drugo mesto (dva ciklusa od 1 do p), a zatim da odredimo interval u kome mora da se nadje broj bodova
  za trece mesto - tako da takmicar sa rednim brojem 1 ima najvise poena. Na pocetku je taj interval [1, second - 1].
  Za svako 2 <= i <= n mora da vazi
  first * a [i][1] + second * a [i][2] + third * a [i][3] <= first * a [1][1] + second * a [1][2] + third * a [1][3] 

  Za ovakvu nejednakost po nepoznatoj third dobijamo gornje ili donje ogranicenje. Na kraju proverimo da li se
  u intervalu [minThird, maxThird] nalazi neki prirodan broj. Ukoliko je odgovor pozitivan prekidamo i stampamo rezultat, 
  a ukoliko takav broj ne postoji nastavljamo pretragu dalje.

  Vremenska slozenost algoritma je O (m + p^2 * n), dok je memorijska slozenost O (n).
  n - broj takmicara
  m - broj trka
  p - maksimalan broj bodova
  first, second, third - brojevi bodova za prvo, drugo i trece mesto
  sol - da li postoji resenje
*/

#include <iostream>
#include <fstream>
using namespace std;

int n, m, p, first, second, third;
int a [1001][4];
bool sol;
double minThird, maxThird;

int main ()
{
  /* Ucitavanje podataka */
  ifstream in ("plivanje.in");
  in >> n >> m >> p;
  for (int i = 1; i <= n; i++)
      for (int j = 1; j <= 3; j++)
          a [i][j] = 0;
  for (int i = 0; i < m; i++)
  {
        in >> first >> second >> third;
        a [first][1]++;
        a [second][2]++;
        a [third][3]++;
    }
  in.close();

    /* Fiksiranje brojeva first i second i nalazenje intervala za third */
  sol = false;
    for (first = p; first >= 3; first--)
  {
        for (second = first - 1; second >= 2; second--)
        {
            minThird = 1.0;
            maxThird = second - 1;
            for (int i = 2; i <= n; i++)
            {
                double x = first * (a [i][1] - a [1][1]) + second * (a [i][2] - a [1][2]);
                double y = a [1][3] - a [i][3];
        if ((y == 0) && (x > 0))
        {
          minThird = p;
          break;
        }
                if ((y > 0) && (minThird < x / y))
          minThird = x / y;
                if ((y < 0) && (maxThird > x / y))
          maxThird = x / y;
            }
            third = (int)maxThird;
            if (third >= minThird)
            {
                sol = true;
                break;
            }
        }
    if (sol == true)
      break;
  }

  /* Stampa rezultata */
  ofstream out ("plivanje.out");
  if (sol == false)
       out << "-1" << endl;
    else
         out << first << " " << second << " " << third << endl;
   out.close();
    return 0;
}