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