#216993. [ICPC 2025 Shanghai R] Yet another mailbox problem

Yana, Mino, White, and Huzz are best friends.

One day, the coach asked White, Mino, and Huzz to prepare a mock contest. Huzz designed a beautifully search problem whose complexity is exponential with respect to . He carefully checked the entire problem statement, except for one detail: he accidentally wrote instead of . Later, this problem appeared in a mock contest. The furious contestant, Yana, came to Huzz, asking how the problem was supposed to be solved. But he seemed to have forgotten something, and the problem statement he provided looked slightly different —

You are given a directed graph with vertices and edges, where each edge is assigned an integer weight between and .

A path is a sequence of edges such that the endpoint of is the startpoint of for all . The length of the path is , the number of edges it contains. Note that a path may contain the same edge multiple times.

The weight sequence of the path is the sequence of edge weights . Paths are compared by lexicographical order of their weight sequences.

Two paths are considered distinct as long as they use different edges, even if they share the same vertex sequence and weight sequence. For example, if both paths and have weight sequence , and both traverse vertices , they are still distinct as long as or .

White wants to find the lexicographically smallest paths. Since the total output may be too large, you only need to output the length of each path.

The st line of the input contains integers (, , ), representing the number of vertices, the number of edges, and the required number of paths.

Each of the next lines contains integers (, , ), representing a directed edge with weight . The given edge set may contain multiple edges.

Print lines. The -th line should contain a single integer, the length of the path whose weight is the -th smallest in lexicographical order. If there are fewer than paths, output instead.

样例输入 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

For simplicity, let denote the -th input edge.

For the first testcase, the lexicographically smallest paths are:

• Path , weight sequence .
• Path , weight sequence .
• Path , weight sequence .
• Path , weight sequence .
• Path , weight sequence .
• Path , weight sequence .
• Path , weight sequence .
• Path , weight sequence .