题目描述

从前在一个森林中，有好多好多只变色龙，每只变色龙有自己的初始颜色 $c_i$，变色龙们没事的时候，喜欢玩一个游戏，所有变色龙站在一个长度为 $L$ 的圆环上，每只变色龙的初始位置位置 $p_i$，他们有的按照顺时针方向走，有的按照逆时针方向走。

当方向不同的两只变色龙相遇的时候，逆时针的变色龙的颜色变成和顺时针的变色龙颜色一样，顺时针的变色龙颜色不变，并且两只变色龙掉头向反方向继续走。

请你计算一下，$T$ 时间后，每只变色龙的颜色和位置以及他们的方向。

输入格式

第一行是一个数 $n$ ，表示有 $n$ 只变色龙，第二行是一个数 $L$，表示圆环的长度。

接下来有 $n$ 行，每行三个数 $p_i,c_i,d_i$，$p_i$ 表示每只变色龙位置，$c_i$ 表示每只变色龙的颜色，$d_i$ 表示每只变色龙的方向，+1 表示顺时针，-1 表示逆时针。

最后一行一个整数 $T$ 表示时间。

（修者注：数据保证了每条变色龙初始与结束位置是不同的）

输出格式

$n$ 行数，每行三个数，分别表示 $T$ 时间后每只变色龙的 $p_i,c_i,d_i$，$p_i$ 保留三位小数。

样例输入

4
13
2 1 1
0 2 -1
12 3 1
5 2 1
23

样例输出

2.000 2 1
12.000 1 1
9.000 3 1
3.000 3 -1

数据规模与约定

对于 $40\%$ 的数据，$n\le 100$。

对于 $60\%$ 的数据，$n\le 10^3$。

对于 $100\%$ 的数据，$n\le 10^5$，$L\le 10^9$，$0\le p_i<L$，$1\le c_i\le 10^9$，$T\le 10^{18}$。