Yana, Mino, White и Huzz — лучшие друзья.

Однажды тренер попросил White, Mino и Huzz подготовить тренировочный контест. Huzz придумал красивую задачу на перебор, сложность которой экспоненциальна по $k$. Он внимательно проверил всё условие задачи, кроме одной детали: он случайно написал $k \le 5 \times 10^5$ вместо $k \le 10$. Позже эта задача появилась в тренировочном контесте. Разъярённая участница Yana пришла к Huzz, спрашивая, как вообще предполагалось решать эту задачу. Но он, кажется, что-то забыл, и условие задачи, которое он показал, выглядело немного иначе —

Вам дан ориентированный граф с $n$ вершинами и $m$ рёбрами, где каждому ребру $e$ приписан целочисленный вес $w(e)$ от $1$ до $8$.

Путём называется последовательность рёбер $(e_1, e_2, \dots, e_\ell)$ такая, что конец ребра $e_i$ совпадает с началом ребра $e_{i+1}$ для всех $1 \le i < \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$ строк содержит три целых числа $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].