圆圈上的变色龙

从前，森林中生活着许多变色龙，每只变色龙都有自己的初始颜色 $c_i$。

变色龙们会在一个长度为 $L$ 的圆环上进行游戏。第 $i$ 只变色龙的初始位置为 $p_i$，运动方向可能是顺时针，也可能是逆时针。所有变色龙的速度大小均为 $1$，其中顺时针方向的速度记为 $+1$，逆时针方向的速度记为 $-1$。圆环上的位置对 $L$ 取模，并表示为区间 $[0,L)$ 内的数。

当两只运动方向相反的变色龙相遇时，逆时针运动的变色龙会变成与顺时针运动的变色龙相同的颜色，而顺时针运动的变色龙颜色不变。随后，两只变色龙都会掉头，并沿相反方向继续运动。

请计算经过时间 $T$ 后，每只变色龙的颜色、位置和运动方向。

输入格式

第一行输入一个整数 $n$，表示变色龙的数量。

第二行输入一个整数 $L$，表示圆环的长度。

接下来 $n$ 行，第 $i$ 行输入三个整数 $p_i,c_i,d_i$，分别表示第 $i$ 只变色龙的初始位置、初始颜色和初始运动方向。其中，$d_i=+1$ 表示顺时针运动，$d_i=-1$ 表示逆时针运动。

最后一行输入一个整数 $T$，表示经过的时间。

输出格式

输出 $n$ 行，每行三个数，分别表示经过时间 $T$ 后，对应变色龙的位置 $p_i$、颜色 $c_i$ 和运动方向 $d_i$。

位置 $p_i$ 保留 $3$ 位小数。

样例输入

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 1000$；
• 对于 $100\%$ 的数据，$n\le 10^5$，$L\le 10^9$，$0\le p_i<L$，$1\le c_i\le 10^9$，$0\le T\le 10^{18}$；
• 保证任意两只变色龙的初始位置不同；
• 保证运动过程中不会出现 $3$ 只或更多变色龙同时位于同一位置，因此每次相遇恰有 $2$ 只反向运动的变色龙参与。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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