Yana, Mino, White và Huzz là những người bạn thân nhất của nhau.

Một ngày nọ, huấn luyện viên yêu cầu White, Mino và Huzz chuẩn bị một kỳ thi thử. Huzz đã thiết kế một bài toán tìm kiếm tuyệt đẹp có độ phức tạp hàm mũ theo $k$. Cậu đã kiểm tra kỹ lưỡng toàn bộ đề bài, ngoại trừ một chi tiết: cậu vô tình viết $k \le 5 \times 10^5$ thay vì $k \le 10$. Sau đó, bài toán này xuất hiện trong kỳ thi thử. Thí sinh giận dữ Yana đã tìm đến Huzz, hỏi xem bài toán này phải giải như thế nào. Nhưng Huzz dường như đã quên mất điều gì đó, và đề bài mà cậu đưa ra trông hơi khác một chút —

Bạn được cho một đồ thị có hướng gồm $n$ đỉnh và $m$ cạnh, trong đó mỗi cạnh $e$ được gán một trọng số nguyên $w(e)$ từ $1$ đến $8$.

Một đường đi là một dãy các cạnh $(e_1, e_2, \dots, e_\ell)$ sao cho điểm cuối của $e_i$ là điểm đầu của $e_{i+1}$ với mọi $1 \le i < \ell$. Độ dài của đường đi là $\ell$, tức số lượng cạnh mà nó chứa. Lưu ý rằng một đường đi có thể chứa cùng một cạnh nhiều lần.

Dãy trọng số của đường đi là dãy trọng số các cạnh $[w(e_1), w(e_2), \dots, w(e_\ell)]$. Các đường đi được so sánh theo thứ tự từ điển của dãy trọng số của chúng.

Hai đường đi được coi là phân biệt miễn là chúng sử dụng các cạnh khác nhau, ngay cả khi chúng có cùng dãy đỉnh và dãy trọng số. Ví dụ, nếu cả hai đường đi $(e_1, e_2)$ và $(e_3, e_4)$ đều có dãy trọng số [1,2], và đều đi qua các đỉnh $1 \to 2 \to 3$, chúng vẫn phân biệt miễn là $e_1 \neq e_3$ hoặc $e_2 \neq e_4$.

White muốn tìm $k$ đường đi có thứ tự từ điển nhỏ nhất. Vì tổng dữ liệu ra có thể quá lớn, bạn chỉ cần in ra độ dài của mỗi đường đi.

Dữ liệu

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $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$), lần lượt biểu thị số đỉnh, số cạnh và số lượng đường đi cần tìm.

Mỗi dòng trong $m$ dòng tiếp theo chứa ba số nguyên $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), biểu thị một cạnh có hướng $e = (x, y)$ với trọng số $w(e) = z$. Tập cạnh đã cho có thể chứa đa cạnh.

Kết quả

In ra $k$ dòng. Dòng thứ $i$ chứa một số nguyên duy nhất là độ dài của đường đi có dãy trọng số nhỏ thứ $i$ theo thứ tự từ điển. Nếu có ít hơn $i$ đường đi, hãy in ra $-1$ để thay thế.

Ví dụ

Dữ liệu

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

Kết quả

1
1
1
2
3
4
5
6

Dữ liệu

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

Kết quả

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

Dữ liệu

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

Kết quả

1
2
1
1
2
3
4
3
1
1
2
3
2
-1
-1

Giải thích

Để đơn giản, gọi $e_j$ là cạnh thứ $j$ trong dữ liệu vào.

Ở bộ test đầu tiên, $8$ đường đi có thứ tự từ điển nhỏ nhất là:

• Đường đi $(e_1)$, dãy trọng số [1].
• Đường đi $(e_3)$, dãy trọng số [1].
• Đường đi $(e_5)$, dãy trọng số [1].
• Đường đi $(e_5, e_1)$, dãy trọng số [1,1].
• Đường đi $(e_5, e_1, e_4)$, dãy trọng số [1,1,2].
• Đường đi $(e_5, e_1, e_4, e_5)$, dãy trọng số [1,1,2,1].
• Đường đi $(e_5, e_1, e_4, e_5, e_1)$, dãy trọng số [1,1,2,1,1].
• Đường đi $(e_5, e_1, e_4, e_5, e_1, e_4)$, dãy trọng số [1,1,2,1,1,2].