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)$가 부여되어 있습니다.

경로란 모든 $1 \le i < \ell$에 대해 $e_i$의 끝점이 $e_{i+1}$의 시작점과 같은 간선들의 수열 $(e_1, e_2, \dots, e_\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$개의 줄 각각에는 가중치가 $w(e) = z$인 방향 간선 $e = (x, y)$를 나타내는 세 정수 $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$)가 주어집니다. 주어지는 간선 집합에는 중복 간선이 포함될 수 있습니다.

출력

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