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].