Yana, Mino, White y Huzz son mejores amigos.

Un día, el entrenador pidió a White, Mino y Huzz que prepararan un concurso de prueba. Huzz diseñó un hermoso problema de búsqueda cuya complejidad es exponencial con respecto a $k$. Revisó cuidadosamente todo el enunciado, salvo por un detalle: escribió accidentalmente $k \le 5 \times 10^5$ en lugar de $k \le 10$. Más tarde, este problema apareció en un concurso de prueba. La furiosa concursante, Yana, acudió a Huzz preguntando cómo se suponía que debía resolverse el problema. Pero él parecía haber olvidado algo, y el enunciado que proporcionó se veía ligeramente diferente —

Se te da un grafo dirigido con $n$ vértices y $m$ aristas, donde a cada arista $e$ se le asigna un peso entero $w(e)$ entre $1$ y $8$.

Un camino es una secuencia de aristas $(e_1, e_2, \dots, e_\ell)$ tal que el extremo final de $e_i$ es el extremo inicial de $e_{i+1}$ para todo $1 \le i < \ell$. La longitud del camino es $\ell$, el número de aristas que contiene. Ten en cuenta que un camino puede contener la misma arista múltiples veces.

La secuencia de pesos del camino es la secuencia de pesos de las aristas $[w(e_1), w(e_2), \dots, w(e_\ell)]$. Los caminos se comparan por el orden lexicográfico de sus secuencias de pesos.

Dos caminos se consideran distintos siempre que utilicen aristas diferentes, incluso si comparten la misma secuencia de vértices y la misma secuencia de pesos. Por ejemplo, si ambos caminos $(e_1, e_2)$ y $(e_3, e_4)$ tienen la secuencia de pesos [1,2] y ambos recorren los vértices $1 \to 2 \to 3$, siguen siendo distintos mientras $e_1 \neq e_3$ o $e_2 \neq e_4$.

White quiere encontrar los $k$ caminos lexicográficamente más pequeños. Como la salida total puede ser demasiado grande, solo necesitas imprimir la longitud de cada camino.

Entrada

La primera línea de la entrada contiene tres enteros $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$), que representan el número de vértices, el número de aristas y el número requerido de caminos.

Cada una de las siguientes $m$ líneas contiene tres enteros $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), que representan una arista dirigida $e = (x, y)$ con peso $w(e) = z$. El conjunto de aristas dado puede contener aristas múltiples.

Salida

Imprime $k$ líneas. La $i$-ésima línea debe contener un solo entero: la longitud del camino cuyo peso es el $i$-ésimo más pequeño en orden lexicográfico. Si hay menos de $i$ caminos, imprime $-1$ en su lugar.

Ejemplos

Entrada

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

Salida

1
1
1
2
3
4
5
6

Entrada

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

Salida

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

Entrada

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

Salida

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

Nota

Por simplicidad, sea $e_j$ la $j$-ésima arista de la entrada.

Para el primer caso de prueba, los $8$ caminos lexicográficamente más pequeños son:

• Camino $(e_1)$, secuencia de pesos [1].
• Camino $(e_3)$, secuencia de pesos [1].
• Camino $(e_5)$, secuencia de pesos [1].
• Camino $(e_5, e_1)$, secuencia de pesos [1,1].
• Camino $(e_5, e_1, e_4)$, secuencia de pesos [1,1,2].
• Camino $(e_5, e_1, e_4, e_5)$, secuencia de pesos [1,1,2,1].
• Camino $(e_5, e_1, e_4, e_5, e_1)$, secuencia de pesos [1,1,2,1,1].
• Camino $(e_5, e_1, e_4, e_5, e_1, e_4)$, secuencia de pesos [1,1,2,1,1,2].