Yana, Mino, White e Huzz sono migliori amici.

Un giorno, l'allenatore chiese a White, Mino e Huzz di preparare una gara di simulazione. Huzz progettò un bellissimo problema di ricerca la cui complessità è esponenziale rispetto a $k$. Controllò attentamente l'intero testo del problema, tranne per un dettaglio: scrisse accidentalmente $k \le 5 \times 10^5$ invece di $k \le 10$. Più tardi, questo problema apparve in una gara di simulazione. La concorrente furiosa, Yana, andò da Huzz chiedendo come si dovesse risolvere il problema. Ma lui sembrava aver dimenticato qualcosa, e il testo del problema che fornì appariva leggermente diverso —

Ti viene dato un grafo orientato con $n$ vertici e $m$ archi, dove a ciascun arco $e$ è assegnato un peso intero $w(e)$ compreso tra $1$ e $8$.

Un cammino è una sequenza di archi $(e_1, e_2, \dots, e_\ell)$ tale che l'estremo finale di $e_i$ sia l'estremo iniziale di $e_{i+1}$ per ogni $1 \le i < \ell$. La lunghezza del cammino è $\ell$, il numero di archi che contiene. Nota che un cammino può contenere lo stesso arco più volte.

La sequenza dei pesi del cammino è la sequenza dei pesi degli archi $[w(e_1), w(e_2), \dots, w(e_\ell)]$. I cammini vengono confrontati secondo l'ordine lessicografico delle loro sequenze dei pesi.

Due cammini sono considerati distinti purché utilizzino archi diversi, anche se condividono la stessa sequenza di vertici e la stessa sequenza dei pesi. Ad esempio, se entrambi i cammini $(e_1, e_2)$ ed $(e_3, e_4)$ hanno sequenza dei pesi [1,2] ed entrambi attraversano i vertici $1 \to 2 \to 3$, sono comunque distinti fintanto che $e_1 \neq e_3$ oppure $e_2 \neq e_4$.

White vuole trovare i $k$ cammini lessicograficamente più piccoli. Poiché l'output totale potrebbe essere troppo grande, devi solamente stampare la lunghezza di ciascun cammino.

Input

La prima riga dell'input contiene tre interi $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$), che rappresentano il numero di vertici, il numero di archi e il numero richiesto di cammini.

Ciascuna delle successive $m$ righe contiene tre interi $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), che rappresentano un arco orientato $e = (x, y)$ con peso $w(e) = z$. L'insieme di archi fornito può contenere archi multipli.

Output

Stampa $k$ righe. La $i$-esima riga deve contenere un singolo intero, la lunghezza del cammino il cui peso è l'$i$-esimo più piccolo in ordine lessicografico. Se ci sono meno di $i$ cammini, stampa invece $-1$.

Esempi

Input

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

Output

1
1
1
2
3
4
5
6

Input

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

Output

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

Input

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

Output

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

Note

Per semplicità, sia $e_j$ il $j$-esimo arco in input.

Per il primo caso di test, gli $8$ cammini lessicograficamente più piccoli sono:

• Cammino $(e_1)$, sequenza dei pesi [1].
• Cammino $(e_3)$, sequenza dei pesi [1].
• Cammino $(e_5)$, sequenza dei pesi [1].
• Cammino $(e_5, e_1)$, sequenza dei pesi [1,1].
• Cammino $(e_5, e_1, e_4)$, sequenza dei pesi [1,1,2].
• Cammino $(e_5, e_1, e_4, e_5)$, sequenza dei pesi [1,1,2,1].
• Cammino $(e_5, e_1, e_4, e_5, e_1)$, sequenza dei pesi [1,1,2,1,1].
• Cammino $(e_5, e_1, e_4, e_5, e_1, e_4)$, sequenza dei pesi [1,1,2,1,1,2].