Yana、Mino、White、Huzz は親友です。

ある日、コーチは White、Mino、Huzz に模擬コンテストの準備を頼みました。Huzz は計算量が $k$ に関して指数時間となる美しい探索問題を作りました。彼は問題文全体を注意深く確認しましたが、一つだけ見落としがありました。誤って $k \le 10$ と書くべきところを $k \le 5 \times 10^5$ と書いてしまったのです。後にこの問題は模擬コンテストに出題されました。激怒した参加者の Yana は Huzz のもとへ行き、どうやって解くつもりだったのかと問い詰めました。しかし Huzz は何かを忘れてしまったようで、彼が提示した問題文は少し異なっていました——

$n$ 個の頂点と $m$ 本の辺からなる有向グラフが与えられます。各辺 $e$ には $1$ 以上 $8$ 以下の整数の重み $w(e)$ が割り当てられています。

パスとは、すべての $1 \le i < \ell$ について $e_i$ の終点が $e_{i+1}$ の始点と一致するような辺の列 $(e_1, e_2, \dots, e_\ell)$ のことです。パスの長さは $\ell$、すなわちパスに含まれる辺の本数です。パスは同じ辺を複数回含んでもよいことに注意してください。

パスの重み列とは、辺の重みの列 $[w(e_1), w(e_2), \dots, w(e_\ell)]$ のことです。パス同士は、その重み列の辞書順によって比較されます。

二つのパスは、頂点列や重み列が同じであっても、使用する辺の列が異なる限り異なるパスとみなされます。例えば、パス $(e_1, e_2)$ と $(e_3, e_4)$ がともに重み列 [1,2] を持ち、ともに頂点 $1 \to 2 \to 3$ を通る場合でも、$e_1 \neq e_3$ または $e_2 \neq e_4$ である限り、それらは異なるパスです。

White は辞書順で小さい方から $k$ 個のパスを求めたいと考えています。出力全体が大きくなりすぎる可能性があるため、各パスの長さのみを出力してください。

入力

入力の最初の行には、頂点数、辺数、および求めるパスの個数を表す三つの整数 $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$）が与えられます。

続く $m$ 行のそれぞれには、重み $w(e) = z$ の有向辺 $e = (x, y)$ を表す三つの整数 $x, y, z$（$1 \le x, y \le n, 1 \le z \le 8, x \neq y$）が与えられます。与えられる辺集合には多重辺が含まれる場合があります。

出力

$k$ 行出力してください。$i$ 行目には、重み列が辞書順で $i$ 番目に小さいパスの長さを表す一つの整数を出力してください。パスが $i$ 個未満しか存在しない場合は、代わりに $-1$ を出力してください。

入出力例

入力

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

出力

1
1
1
2
3
4
5
6

入力

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

出力

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

入力

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

出力

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

注記

簡単のため、$e_j$ で入力の $j$ 番目の辺を表します。

最初のテストケースにおいて、辞書順で小さい方から $8$ 個のパスは次の通りです：

• パス $(e_1)$, 重み列 [1].
• パス $(e_3)$, 重み列 [1].
• パス $(e_5)$, 重み列 [1].
• パス $(e_5, e_1)$, 重み列 [1,1].
• パス $(e_5, e_1, e_4)$, 重み列 [1,1,2].
• パス $(e_5, e_1, e_4, e_5)$, 重み列 [1,1,2,1].
• パス $(e_5, e_1, e_4, e_5, e_1)$, 重み列 [1,1,2,1,1].
• パス $(e_5, e_1, e_4, e_5, e_1, e_4)$, 重み列 [1,1,2,1,1,2].