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)$。

一條路徑是一個邊序列 $(e_1, e_2, \dots, e_\ell)$，滿足對於所有 $1 \le i < \ell$，$e_i$ 的終點是 $e_{i+1}$ 的起點。路徑的長度為 $\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$ 行，每行包含三個整數 $x, y, z$（$1 \le x, y \le n, 1 \le z \le 8, x \neq y$），表示一條有向邊 $e = (x, y)$，其邊權為 $w(e) = z$。給定的邊集中可能包含重邊。

輸出格式

輸出 $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].