In a strange country, there are $N$ cities numbered $1$ to $N$, and $M$ roads numbered $1$ to $M$. The government would like to connect as many cities together as possible for the minimum cost. Every day, they will activate the current minimum spanning tree/forest.

Two cities are considered connected if they can be reached directly or indirectly from one another. A bidirectional road connects two cities and has a cost to activate.

It is worth noting that all costs are distinct, which means there is always only one way to form the minimum spanning tree/forest. However, after every day, the people of the country tend to destroy roads, and a road that was activated for the day will not be usable for the rest of eternity. Thus, the government will activate a new set of roads the day after according to the same rule. The government wants to know for each road which day in the following $K$ days it was activated or output that the road is never activated in the $K$ following days.

Constraints

For all subtasks:

$1\le N\le 5\times {10}^3$

$1\le K\le {10}^4$

$0\le M\le 3\times {10}^5$

$1\le u_i,v_i\le N$

$1\le w_i\le {10}^9$

All edges are bidirectional.

There will be no self-loops, but there can be multiple edges running through the same pair of nodes.

Subtask 1 [30%]

$0\le M\le 1000$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains three integers $N$, $M$, and $K$.

The following $M$ lines contain three integers $u_i$, $v_i$, $w_i$, meaning there is a road connecting $u_i$ and $v_i$ with a cost of $w_i$ to activate.

Output Specification

Output $M$ lines, the $i$th line contains an integer representing which day the $i$th road in the order of input is activated, or $-1$ if the road is never activated in the $K$ days.

Sample Input

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

Sample Output

2
1
2
-1
1

Sample Explanation

On the first day, roads $2$ and $5$ are activated. On the second day, roads $1$ and $3$ are activated. Note that road $4$ is never activated.