Yana, Mino, White und Huzz sind beste Freunde.

Eines Tages bat der Trainer White, Mino und Huzz, einen Trainingswettbewerb vorzubereiten. Huzz entwarf ein wunderbares Suchproblem, dessen Komplexität exponentiell in $k$ ist. Er überprüfte sorgfältig die gesamte Aufgabenstellung, bis auf ein Detail: Aus Versehen schrieb er $k \le 5 \times 10^5$ statt $k \le 10$. Später erschien diese Aufgabe in einem Trainingswettbewerb. Die wütende Teilnehmerin Yana kam zu Huzz und fragte, wie die Aufgabe denn gelöst werden sollte. Doch er schien etwas vergessen zu haben, und die Aufgabenstellung, die er vorlegte, sah leicht anders aus —

Gegeben ist ein gerichteter Graph mit $n$ Knoten und $m$ Kanten, wobei jeder Kante $e$ ein ganzzahliges Gewicht $w(e)$ zwischen $1$ und $8$ zugewiesen ist.

Ein Pfad ist eine Folge von Kanten $(e_1, e_2, \dots, e_\ell)$, sodass für alle $1 \le i < \ell$ der Endpunkt von $e_i$ der Startpunkt von $e_{i+1}$ ist. Die Länge des Pfades ist $\ell$, die Anzahl der darin enthaltenen Kanten. Beachte, dass ein Pfad dieselbe Kante mehrmals enthalten kann.

Die Gewichtsfolge des Pfades ist die Folge der Kantengewichte $[w(e_1), w(e_2), \dots, w(e_\ell)]$. Pfade werden anhand der lexikographischen Ordnung ihrer Gewichtsfolgen verglichen.

Zwei Pfade gelten als verschieden, solange sie unterschiedliche Kanten verwenden, selbst wenn sie dieselbe Knotenfolge und Gewichtsfolge besitzen. Wenn beispielsweise beide Pfade $(e_1, e_2)$ und $(e_3, e_4)$ die Gewichtsfolge [1,2] haben und beide die Knoten $1 \to 2 \to 3$ durchlaufen, sind sie dennoch verschieden, solange $e_1 \neq e_3$ oder $e_2 \neq e_4$ gilt.

White möchte die lexikographisch kleinsten $k$ Pfade finden. Da die Gesamtausgabe zu groß sein könnte, musst du nur die Länge jedes Pfades ausgeben.

Eingabe

Die erste Zeile der Eingabe enthält drei ganze Zahlen $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$), die die Anzahl der Knoten, die Anzahl der Kanten und die geforderte Anzahl an Pfaden darstellen.

Jede der nächsten $m$ Zeilen enthält drei ganze Zahlen $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), die eine gerichtete Kante $e = (x, y)$ mit Gewicht $w(e) = z$ darstellen. Die gegebene Kantenmenge kann Mehrfachkanten enthalten.

Ausgabe

Gib $k$ Zeilen aus. Die $i$-te Zeile soll eine einzige ganze Zahl enthalten, die Länge des Pfades, dessen Gewicht in lexikographischer Ordnung das $i$-tkleinste ist. Falls es weniger als $i$ Pfade gibt, gib stattdessen $-1$ aus.

Beispiele

Eingabe

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

Ausgabe

1
1
1
2
3
4
5
6

Eingabe

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

Ausgabe

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

Eingabe

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

Ausgabe

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

Hinweis

Der Einfachheit halber bezeichne $e_j$ die $j$-te Eingabekante.

Für den ersten Testfall sind die lexikographisch kleinsten $8$ Pfade:

• Pfad $(e_1)$, Gewichtsfolge [1].
• Pfad $(e_3)$, Gewichtsfolge [1].
• Pfad $(e_5)$, Gewichtsfolge [1].
• Pfad $(e_5, e_1)$, Gewichtsfolge [1,1].
• Pfad $(e_5, e_1, e_4)$, Gewichtsfolge [1,1,2].
• Pfad $(e_5, e_1, e_4, e_5)$, Gewichtsfolge [1,1,2,1].
• Pfad $(e_5, e_1, e_4, e_5, e_1)$, Gewichtsfolge [1,1,2,1,1].
• Pfad $(e_5, e_1, e_4, e_5, e_1, e_4)$, Gewichtsfolge [1,1,2,1,1,2].