国王收到了一些投诉，称他王国中的某些地区在经济上被忽视了。很长一段时间以来，市民们都没有看到有商人在连接村庄的某些道路上往来。为了解决这个问题，恢复王国的财富与繁荣，国王任命了他的皇家数学家来制定一份可行的商人路线计划。

该计划将包含每条道路上往来的正整数数量的商人，且必须沿其中一个方向行进。进入一个村庄的商人数量应等于离开该村庄的商人数量。为了确保商人在王国各处分布相对均匀，国王要求每条道路上的商人数量至少为 1 且小于 $M$。

皇家数学家已被国王召见以提交他的发现。由于他未能解决这个问题，他的未来充满不确定性。不过，他确实取得了一些进展。他找到了一个每条道路上商人数量有效的计划。唯一的问题是，村庄中进入和离开的商人数量并不完全相等（至少不完全相等）。虽然对于每个村庄，其差值可能不为零，但该差值模 $M$ 等于零。如果你能编写一个程序来找到一个有效的计划或报告其不存在，他愿意与你分享他的发现。

输入格式

第一行包含 $N$（村庄数量）、$R$（道路数量）和 $M$。

接下来的 $R$ 行描述了道路，每行包含 $A_i$、$B_i$ 和 $C_i$，表示连接村庄 $A_i$ 和 $B_i$ 的一条道路，其中有 $C_i$ 名商人从 $A_i$ 往 $B_i$ 行进。村庄编号从 $1$ 到 $N$。每对村庄之间最多只有一条道路，且没有道路连接村庄自身。每个村庄进入和离开的商人数量之差模 $M$ 等于 $0$。

数据范围

• $1 \le N \le 1000$
• $0 \le R \le 10\,000$
• $2 \le M \le 1000$
• $1 \le A_i, B_i \le N$
• $0 < C_i < M$

输出格式

输出每条道路上往来的商人数量。请按照输入中给出的顺序，在单独的行中打印它们。如果商人行进的方向与输入中定义道路的城市顺序相反，请用负值表示（例如，如果有 $X$ 名商人从 $B_i$ 往 $A_i$ 行进，则在第 $i$ 行输出中用 $-X$ 表示）。

如果存在多个解，你可以输出其中任意一个。如果不存在解，则单行输出单词 "IMPOSSIBLE"。

样例

输入 1

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

输出 1

2
3
2
-1
3