Yana, Mino, White i Huzz są najlepszymi przyjaciółmi.

Pewnego dnia trener poprosił White, Mino i Huzza o przygotowanie próbnego konkursu. Huzz zaprojektował piękne zadanie przeszukiwania, którego złożoność jest wykładnicza względem $k$. Dokładnie sprawdził całą treść zadania, z wyjątkiem jednego szczegółu: przypadkowo napisał $k \le 5 \times 10^5$ zamiast $k \le 10$. Później zadanie to pojawiło się na próbnym konkursie. Wściekła uczestniczka, Yana, przyszła do Huzza z pytaniem, jak to zadanie miało zostać rozwiązane. Wyglądało jednak na to, że o czymś zapomniał, a przedstawiona przez niego treść zadania wyglądała nieco inaczej —

Dany jest skierowany graf o $n$ wierzchołkach i $m$ krawędziach, w którym każdej krawędzi $e$ przypisano całkowitą wagę $w(e)$ z przedziału od $1$ do $8$.

Ścieżką nazywamy ciąg krawędzi $(e_1, e_2, \dots, e_\ell)$ taki, że koniec krawędzi $e_i$ jest początkiem krawędzi $e_{i+1}$ dla wszystkich $1 \le i < \ell$. Długością ścieżki jest $\ell$, czyli liczba krawędzi, które zawiera. Zauważ, że ścieżka może zawierać tę samą krawędź wielokrotnie.

Ciągiem wag ścieżki jest ciąg wag jej krawędzi $[w(e_1), w(e_2), \dots, w(e_\ell)]$. Ścieżki są porównywane według porządku leksykograficznego ich ciągów wag.

Dwie ścieżki uważa się za różne, o ile używają różnych krawędzi, nawet jeśli mają ten sam ciąg wierzchołków i ciąg wag. Na przykład, jeśli obie ścieżki $(e_1, e_2)$ oraz $(e_3, e_4)$ mają ciąg wag [1,2] i obie przechodzą przez wierzchołki $1 \to 2 \to 3$, to nadal są różne, o ile $e_1 \neq e_3$ lub $e_2 \neq e_4$.

White chce znaleźć $k$ leksykograficznie najmniejszych ścieżek. Ponieważ pełne wyjście może być zbyt duże, wystarczy wypisać długość każdej ścieżki.

Wejście

Pierwszy wiersz wejścia zawiera trzy liczby całkowite $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$), oznaczające liczbę wierzchołków, liczbę krawędzi oraz wymaganą liczbę ścieżek.

Każdy z kolejnych $m$ wierszy zawiera trzy liczby całkowite $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), reprezentujące skierowaną krawędź $e = (x, y)$ o wadze $w(e) = z$. Podany zbiór krawędzi może zawierać krawędzie wielokrotne.

Wyjście

Wypisz $k$ wierszy. $i$-ty wiersz powinien zawierać jedną liczbę całkowitą – długość ścieżki, której ciąg wag jest $i$-ty najmniejszy w porządku leksykograficznym. Jeśli istnieje mniej niż $i$ ścieżek, wypisz zamiast tego $-1$.

Przykłady

Wejście

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

Wyjście

1
1
1
2
3
4
5
6

Wejście

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

Wyjście

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

Wejście

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

Wyjście

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

Uwaga

Dla uproszczenia niech $e_j$ oznacza $j$-tą krawędź z wejścia.

Dla pierwszego przypadku testowego $8$ leksykograficznie najmniejszych ścieżek to:

• Ścieżka $(e_1)$, ciąg wag [1].
• Ścieżka $(e_3)$, ciąg wag [1].
• Ścieżka $(e_5)$, ciąg wag [1].
• Ścieżka $(e_5, e_1)$, ciąg wag [1,1].
• Ścieżka $(e_5, e_1, e_4)$, ciąg wag [1,1,2].
• Ścieżka $(e_5, e_1, e_4, e_5)$, ciąg wag [1,1,2,1].
• Ścieżka $(e_5, e_1, e_4, e_5, e_1)$, ciąg wag [1,1,2,1,1].
• Ścieżka $(e_5, e_1, e_4, e_5, e_1, e_4)$, ciąg wag [1,1,2,1,1,2].