暂无测试数据。

夏天的风拂过小 C，这是他最喜欢的时候，初夏，没有过多的炎热，没有一丝丝寒冷，温暖而幸福。

不知过了多久，小 C 也拥有了神力，他可以马上计算出某个时刻有多少阵风，并且每阵风的风力是多少，他甚至可以操纵每阵风的方向，并且他发现，每阵风的相遇也满足向量的加减法则，形象的说，一阵向西的 $a$ 级风遇到一阵向东的 $b$ 级风，当 $a>b$ 时，就会合并成向西的 $a-b$ 级风，当 $a< b$ 时，就会合并成向东的 $b-a$ 级风，当 $a=b$ 时，这两阵风便全部静止了，而如果是同向风在一起，则风力会叠加起来。

已知有 $n$ 个时刻和 $m$ 阵风，第 $i$ 阵风在时刻 $a_i$ 出现，在时刻 $b_i$ 消失，大小为 $c_i$ 级，小 C 想知道，通过安排每一阵风的方向，使得合并出来的风的风力与定值 $L$ 差值尽量小，我们认为风的方向只有正东和正西。

输出每一时刻合并出来的风和定值的差值。

输入格式

第一行，三个数，$n,m,L$。

接下来 $m$ 行，每行三个数 $a_i,b_i,c_i$。

输出格式

$n$ 行，每行一个数，表示时刻 $i$ 合并出来的风力与 $L$ 的差值。

数据规模与约定

对于 $30\%$ 的数据，$1 \leq n,m \leq 15,1\leq L,c_i \leq 1000$；

对于 $100\%$ 的数据，$1 \leq n,m \leq 30,1\leq L,c_i \leq 10^5$。

2 2 3
1 2 2
1 1 1

0
1