IOI 国的铁路所有者、大富豪 JOI 先生去世了。根据遗嘱，铁路将进行分割继承。
IOI 国有 $N$ 个城市和 $M$ 条连接这些城市的铁路。城市编号为 $1$ 到 $N$，铁路编号为 $1$ 到 $M$。铁路 $i$ 双向连接城市 $A_i$ 和城市 $B_i$，每年产生 $C_i$ 日元的收益。由于铁路的客流量和票价各不相同，因此 $C_1, \dots, C_M$ 各不相同。连接同一对城市的铁路可能有多条。
遗嘱中记载了如下的铁路分割继承方法：
- 铁路将由 JOI 先生的 $K$ 个孩子继承。孩子们按年龄从大到小编号为 $1$ 到 $K$。
- 每个孩子继承 $M$ 条铁路中的若干条（也可以是 $0$ 条）。
- 首先，孩子 $1$ 从 $M$ 条铁路中选择若干条作为自己的继承份额。接着，孩子 $2$ 从剩下的铁路中决定自己的继承份额。以此类推， $K$ 个孩子按顺序决定自己的继承份额。
- 任何孩子都不能继承已经被他人继承的铁路。也就是说，如果铁路 $i$ 包含在孩子 $j$ 的继承份额中，那么年龄较小的孩子 $k$ ($k > j$) 就不能将铁路 $i$ 包含在自己的继承份额中。
- 任何孩子在决定自己的继承份额时，必须确保继承的铁路不包含环。也就是说，如果通过利用铁路 $i_1, i_2, \dots, i_m$（$i_1, i_2, \dots, i_m$ 互不相同）各一次，可以从某个城市出发并回到同一个城市，那么任何孩子都不能独自继承所有这些铁路 $i_1, i_2, \dots, i_m$。
- 无人继承的剩余铁路将捐赠给 IOI 国。
由于每个孩子都像父亲一样贪婪，他们会选择自己的继承份额，使得所继承铁路的年收益总额尽可能大。可以证明，对于每个孩子，使年收益总额最大的继承方案是唯一的。请确定每条铁路分别由谁继承。
题目描述
给定 IOI 国的铁路信息和 JOI 先生的孩子人数，请编写一个程序，确定每条铁路分别由谁继承。
输入格式
从标准输入读取以下内容：
- 第 $1$ 行包含 $3$ 个整数 $N, M, K$，以空格分隔。这表示 IOI 国有 $N$ 个城市和 $M$ 条铁路，JOI 先生有 $K$ 个孩子。
- 接下来的 $M$ 行中，第 $i$ 行 ($1 \le i \le M$) 包含整数 $A_i, B_i, C_i$，以空格分隔。这表示铁路 $i$ 双向连接城市 $A_i$ 和城市 $B_i$，年收益为 $C_i$ 日元。
输出格式
输出包含 $M$ 行。第 $i$ 行 ($1 \le i \le M$) 输出继承铁路 $i$ 的孩子的编号。如果铁路被捐赠给 IOI 国，则输出 $0$。
数据范围
所有输入数据满足以下条件：
- $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$)
子任务
子任务 1 [15 分]
- 满足 $K \le 10$。
子任务 2 [85 分]
- 没有额外限制。
样例
样例 1
输入：
3 5 2 1 2 3 1 2 1 2 3 4 2 3 6 1 3 2
输出：
1 0 2 1 2
说明： 孩子 $1$ 从铁路 $1, 2, 3, 4, 5$ 中选择铁路 $1, 4$ 继承。此时继承铁路的年收益总额为 $3 + 6 = 9$ 日元，这是最大值。 孩子 $2$ 从剩下的铁路 $2, 3, 5$ 中选择铁路 $3, 5$ 继承。此时继承铁路的年收益总额为 $4 + 2 = 6$ 日元，这是最大值。 * 剩下的铁路 $2$ 被捐赠给 IOI 国。
样例 2
输入：
3 6 5 1 2 1 1 2 2 2 3 3 2 3 4 3 1 5 3 1 6
输出：
4 3 2 1 2 1
说明： 每个孩子继承的铁路数量可能不同。也可能存在没有继承任何铁路的孩子。