Yana, Mino, White et Huzz sont meilleurs amis.

Un jour, l'entraîneur a demandé à White, Mino et Huzz de préparer un concours blanc. Huzz a conçu un magnifique problème de recherche dont la complexité est exponentielle en $k$. Il a soigneusement vérifié tout l'énoncé, à l'exception d'un détail : il a accidentellement écrit $k \le 5 \times 10^5$ au lieu de $k \le 10$. Plus tard, ce problème est apparu lors d'un concours blanc. La participante furieuse, Yana, est venue voir Huzz pour lui demander comment le problème était censé être résolu. Mais il semblait avoir oublié quelque chose, et l'énoncé qu'il a fourni avait l'air légèrement différent —

On vous donne un graphe orienté à $n$ sommets et $m$ arêtes, où chaque arête $e$ est munie d'un poids entier $w(e)$ compris entre $1$ et $8$.

Un chemin est une suite d'arêtes $(e_1, e_2, \dots, e_\ell)$ telle que l'extrémité finale de $e_i$ soit l'extrémité initiale de $e_{i+1}$ pour tout $1 \le i < \ell$. La longueur du chemin est $\ell$, le nombre d'arêtes qu'il contient. Notez qu'un chemin peut contenir la même arête plusieurs fois.

La suite de poids du chemin est la suite des poids des arêtes $[w(e_1), w(e_2), \dots, w(e_\ell)]$. Les chemins sont comparés selon l'ordre lexicographique de leurs suites de poids.

Deux chemins sont considérés comme distincts dès lors qu'ils utilisent des arêtes différentes, même s'ils partagent la même suite de sommets et la même suite de poids. Par exemple, si les deux chemins $(e_1, e_2)$ et $(e_3, e_4)$ ont tous deux la suite de poids [1,2] et parcourent tous deux les sommets $1 \to 2 \to 3$, ils restent distincts tant que $e_1 \neq e_3$ ou $e_2 \neq e_4$.

White souhaite trouver les $k$ plus petits chemins selon l'ordre lexicographique. Comme la sortie totale pourrait être trop volumineuse, vous devez uniquement afficher la longueur de chaque chemin.

Entrée

La première ligne de l'entrée contient trois entiers $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$), représentant le nombre de sommets, le nombre d'arêtes et le nombre de chemins demandés.

Chacune des $m$ lignes suivantes contient trois entiers $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), représentant une arête orientée $e = (x, y)$ de poids $w(e) = z$. L'ensemble d'arêtes donné peut contenir des arêtes multiples.

Sortie

Affichez $k$ lignes. La $i$-ème ligne doit contenir un seul entier : la longueur du chemin dont la suite de poids est la $i$-ème plus petite dans l'ordre lexicographique. S'il y a moins de $i$ chemins, affichez $-1$ à la place.

Exemples

Entrée

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

Sortie

1
1
1
2
3
4
5
6

Entrée

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

Sortie

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

Entrée

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

Sortie

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

Note

Par simplicité, notons $e_j$ la $j$-ème arête de l'entrée.

Pour le premier cas de test, les $8$ plus petits chemins selon l'ordre lexicographique sont :

• Chemin $(e_1)$, suite de poids [1].
• Chemin $(e_3)$, suite de poids [1].
• Chemin $(e_5)$, suite de poids [1].
• Chemin $(e_5, e_1)$, suite de poids [1,1].
• Chemin $(e_5, e_1, e_4)$, suite de poids [1,1,2].
• Chemin $(e_5, e_1, e_4, e_5)$, suite de poids [1,1,2,1].
• Chemin $(e_5, e_1, e_4, e_5, e_1)$, suite de poids [1,1,2,1,1].
• Chemin $(e_5, e_1, e_4, e_5, e_1, e_4)$, suite de poids [1,1,2,1,1,2].