Yana, Mino, White och Huzz är bästa vänner.

En dag bad tränaren White, Mino och Huzz att förbereda en övningstävling. Huzz konstruerade ett vackert sökproblem vars komplexitet är exponentiell med avseende på $k$. Han kontrollerade noggrant hela problemformuleringen, förutom en detalj: han råkade skriva $k \le 5 \times 10^5$ istället för $k \le 10$. Senare dök detta problem upp i en övningstävling. Den rasande tävlanden Yana kom till Huzz och frågade hur det var tänkt att problemet skulle lösas. Men han verkade ha glömt något, och problemformuleringen han visade såg lite annorlunda ut —

Du får en riktad graf med $n$ hörn och $m$ kanter, där varje kant $e$ tilldelas en heltalsvikt $w(e)$ mellan $1$ och $8$.

En väg är en följd av kanter $(e_1, e_2, \dots, e_\ell)$ sådan att slutpunkten för $e_i$ är startpunkten för $e_{i+1}$ för alla $1 \le i < \ell$. Längden på vägen är $\ell$, antalet kanter den innehåller. Observera att en väg kan innehålla samma kant flera gånger.

Vägens viktföljd är följden av kantvikter $[w(e_1), w(e_2), \dots, w(e_\ell)]$. Vägar jämförs enligt lexikografisk ordning av deras viktföljder.

Två vägar betraktas som skilda så länge de använder olika kanter, även om de delar samma hörnföljd och viktföljd. Om till exempel både vägen $(e_1, e_2)$ och $(e_3, e_4)$ har viktföljden [1,2] och båda går genom hörnen $1 \to 2 \to 3$, är de ändå skilda så länge $e_1 \neq e_3$ eller $e_2 \neq e_4$.

White vill hitta de lexikografiskt minsta $k$ vägarna. Eftersom den totala utdatan kan bli för stor behöver du bara skriva ut längden på varje väg.

Indata

Den första raden i indatan innehåller tre heltal $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 representerar antalet hörn, antalet kanter och det begärda antalet vägar.

Var och en av de följande $m$ raderna innehåller tre heltal $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), som representerar en riktad kant $e = (x, y)$ med vikt $w(e) = z$. Den givna kantmängden kan innehålla multipla kanter.

Utdata

Skriv ut $k$ rader. Den $i$-te raden ska innehålla ett enda heltal, längden på den väg vars vikt är den $i$-te minsta i lexikografisk ordning. Om det finns färre än $i$ vägar, skriv ut $-1$ istället.

Exempel

Indata

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

Indata

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

Indata

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

Förklaring

För enkelhets skull, låt $e_j$ beteckna den $j$-te kanten i indatan.

För det första testfallet är de lexikografiskt minsta $8$ vägarna:

• Väg $(e_1)$, viktföljd [1].
• Väg $(e_3)$, viktföljd [1].
• Väg $(e_5)$, viktföljd [1].
• Väg $(e_5, e_1)$, viktföljd [1,1].
• Väg $(e_5, e_1, e_4)$, viktföljd [1,1,2].
• Väg $(e_5, e_1, e_4, e_5)$, viktföljd [1,1,2,1].
• Väg $(e_5, e_1, e_4, e_5, e_1)$, viktföljd [1,1,2,1,1].
• Väg $(e_5, e_1, e_4, e_5, e_1, e_4)$, viktföljd [1,1,2,1,1,2].