Yana, Mino, White og Huzz er bestevenner.

En dag ba treneren White, Mino og Huzz om å forberede en treningskonkurranse. Huzz lagde et vakkert søkeproblem hvis kompleksitet er eksponentiell med hensyn på $k$. Han sjekket nøye hele oppgaveteksten, bortsett fra én detalj: han skrev ved et uhell $k \le 5 \times 10^5$ i stedet for $k \le 10$. Senere dukket denne oppgaven opp i en treningskonkurranse. Den rasende deltakeren Yana kom til Huzz og spurte hvordan oppgaven egentlig skulle løses. Men han så ut til å ha glemt noe, og oppgaveteksten han ga så litt annerledes ut —

Du får gitt en rettet graf med $n$ noder og $m$ kanter, der hver kant $e$ er tildelt en heltallsvekt $w(e)$ mellom $1$ og $8$.

En sti er en følge av kanter $(e_1, e_2, \dots, e_\ell)$ slik at sluttpunktet til $e_i$ er startpunktet til $e_{i+1}$ for alle $1 \le i < \ell$. Lengden på stien er $\ell$, antallet kanter den inneholder. Merk at en sti kan inneholde samme kant flere ganger.

Vektfølgen til stien er følgen av kantvekter $[w(e_1), w(e_2), \dots, w(e_\ell)]$. Stier sammenlignes etter leksikografisk rekkefølge av vektfølgene deres.

To stier regnes som forskjellige så lenge de bruker forskjellige kanter, selv om de deler samme nodefølge og vektfølge. Hvis for eksempel begge stiene $(e_1, e_2)$ og $(e_3, e_4)$ har vektfølge [1,2], og begge går gjennom nodene $1 \to 2 \to 3$, er de likevel forskjellige så lenge $e_1 \neq e_3$ eller $e_2 \neq e_4$.

White ønsker å finne de $k$ leksikografisk minste stiene. Siden den totale utdataen kan bli for stor, trenger du bare å skrive ut lengden på hver sti.

Inndata

Den første linjen i inndataene inneholder tre heltall $n, m, k$ ($2 \le n \le 5 \times 10^5, 1 \le m \le 5 \times 10^5, 1 \le k \le 5 \times 10^5$), som representerer antall noder, antall kanter og det ønskede antallet stier.

Hver av de neste $m$ linjene inneholder tre heltall $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), som representerer en rettet kant $e = (x, y)$ med vekt $w(e) = z$. Den gitte kantmengden kan inneholde multiple kanter.

Utdata

Skriv ut $k$ linjer. Den $i$-te linjen skal inneholde ett enkelt heltall, lengden på stien hvis vekt er den $i$-te minste i leksikografisk rekkefølge. Hvis det finnes færre enn $i$ stier, skriv ut $-1$ i stedet.

Eksempler

Inndata

5 5 8
2 1 1
3 1 2
4 1 1
1 5 2
5 2 1

Utdata

1
1
1
2
3
4
5
6

Inndata

3 4 10
1 2 1
1 2 1
2 3 2
2 3 3

Utdata

1
1
2
2
2
2
1
1
-1
-1

Inndata

6 5 15
1 2 3
2 3 5
3 4 2
3 5 1
5 6 4

Utdata

1
2
1
1
2
3
4
3
1
1
2
3
2
-1
-1

Forklaring

For enkelhets skyld lar vi $e_j$ betegne den $j$-te kanten i inndataene.

For det første testtilfellet er de $8$ leksikografisk minste stiene:

• Sti $(e_1)$, vektfølge [1].
• Sti $(e_3)$, vektfølge [1].
• Sti $(e_5)$, vektfølge [1].
• Sti $(e_5, e_1)$, vektfølge [1,1].
• Sti $(e_5, e_1, e_4)$, vektfølge [1,1,2].
• Sti $(e_5, e_1, e_4, e_5)$, vektfølge [1,1,2,1].
• Sti $(e_5, e_1, e_4, e_5, e_1)$, vektfølge [1,1,2,1,1].
• Sti $(e_5, e_1, e_4, e_5, e_1, e_4)$, vektfølge [1,1,2,1,1,2].