The wealthy Mr. JOI, who owned all the railways in the country of IOI, has passed away. The railways are to be divided and inherited according to his will.

The country of IOI has $N$ cities and $M$ railways connecting them. The cities are numbered from $1$ to $N$, and the railways are numbered from $1$ to $M$. Railway $i$ connects city $A_i$ and city $B_i$ bidirectionally and generates an annual profit of $C_i$ yen. Since the number of passengers and fares vary, all $C_1, \dots, C_M$ are distinct. There may be multiple railways connecting the same two cities.

The will specifies the method of dividing the railways as follows:

• The railways are to be inherited by Mr. JOI's $K$ children. The children are numbered from $1$ to $K$ in descending order of age.
• Each child inherits some number of the $M$ railways (it is possible for a child to inherit zero railways).
• First, child $1$ chooses some railways from the $M$ available railways to be their inheritance. Next, child $2$ chooses their inheritance from the remaining railways. This continues, with the $K$ children choosing their inheritance in order.
• No child can inherit a railway that has already been assigned to someone else. That is, if railway $i$ is included in the inheritance of child $j$, then any younger child $k$ ($k > j$) cannot include railway $i$ in their own inheritance.
• When choosing their inheritance, no child is allowed to select a set of railways that contains a cycle. That is, if it is possible to start from a city and return to the same city by using each of the railways $i_1, i_2, \dots, i_m$ ($i_1, i_2, \dots, i_m$ are distinct) exactly once, then no child can inherit all of the railways $i_1, i_2, \dots, i_m$ at once.
• Any railways remaining after everyone has made their choices are donated to the country of IOI.

Since all the children are as greedy as their father, each child chooses their inheritance such that the total annual profit of the inherited railways is as large as possible. It can be proven that for every child, there is a unique way to choose their inheritance that maximizes the total annual profit. Determine who inherits each railway.

Input

Read the following from standard input:

• The first line contains three space-separated integers $N, M, K$. This indicates that the country of IOI has $N$ cities and $M$ railways, and Mr. JOI has $K$ children.
• The $i$-th line of the following $M$ lines ($1 \le i \le M$) contains space-separated integers $A_i, B_i, C_i$. This indicates that railway $i$ connects city $A_i$ and city $B_i$ bidirectionally and generates an annual profit of $C_i$ yen.

Output

The output should consist of $M$ lines. The $i$-th line ($1 \le i \le M$) should contain the number of the child who inherits railway $i$. If the railway is donated to the country of IOI, output $0$.

Constraints

All input data satisfies the following conditions:

• $2 \le N \le 1\,000$.
• $1 \le M \le 300\,000$.
• $1 \le K \le 10\,000$.
• $1 \le A_i \le N, 1 \le B_i \le N$ ($1 \le i \le M$).
• $A_i \neq B_i$ ($1 \le i \le M$).
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le M$).
• $C_i \neq C_j$ ($1 \le i < j \le M$).

Subtasks

Subtask 1 [15 points]

• $K \le 10$ is satisfied.

Subtask 2 [85 points]

• No additional constraints.

Examples

Input 1

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

Output 1

1
0
2
1
2

Note

• Child $1$ chooses railways $1$ and $4$ from railways $1, 2, 3, 4, 5$. The total annual profit of the inherited railways is $3 + 6 = 9$ yen, which is the maximum.
• Child $2$ chooses railways $3$ and $5$ from the remaining railways $2, 3, 5$. The total annual profit of the inherited railways is $4 + 2 = 6$ yen, which is the maximum.
• The remaining railway $2$ is donated to the country of IOI.

Input 2

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

Output 2

4
3
2
1
2
1

The number of railways inherited may differ among children. There may be children who do not inherit any railways.