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$)，表示一条从 $x$ 到 $y$ 的有向边 $e = (x, y)$，其边权为 $w(e) = z$. 给定的边集中可能包含重边。

输出格式

输出 $k$ 行。第 $i$ 行应包含一个整数，表示权值序列字典序第 $i$ 小的路径的长度。如果路径总数少于 $i$ 条，则输出 $-1$。

样例

输入样例 1

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

输出样例 1

1
1
1
2
3
4
5
6

输入样例 2

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

输出样例 2

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

输入样例 3

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

输出样例 3

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