[SGU509] Chameleons All Around

题目描述

一个周长为 $L$ 的圆环上有 $n$ 只变色龙。第 $i$ 只变色龙初始位于坐标 $p_i$，颜色编号为 $c_i$，并以速度 $1$ 沿圆环运动。

方向 $d_i$ 只有两种：

• $d_i=1$：顺时针运动；
• $d_i=-1$：逆时针运动。

当两只变色龙相遇时，会立即发生以下变化：

1. 原本逆时针运动的变色龙把自己的颜色变成原本顺时针运动的变色龙的颜色；
2. 两只变色龙同时掉头，即各自的运动方向反转。

坐标沿顺时针方向增加，并按模 $L$ 循环，合法坐标范围为 $[0,L)$。

给定整数时刻 $T$，请你求出此时每一只变色龙的位置、颜色和运动方向。答案必须按照变色龙在输入中的顺序输出。

保证在时刻 $T$ 恰好不会有两只变色龙相遇。

由于所有初始位置和 $T$ 都是整数，且速度恒为 $1$，因此整数时刻所有变色龙的位置也一定是整数。本题要求直接输出整数坐标。

输入格式

第一行一个整数 $n$。

第二行一个整数 $L$，表示圆环周长。

接下来 $n$ 行，每行三个整数 $p_i,c_i,d_i$，依次表示第 $i$ 只变色龙的初始位置、颜色和方向。

最后一行一个整数 $T$。

输出格式

输出 $n$ 行。

第 $i$ 行输出三个整数 $x_i,c'_i,d'_i$，表示时刻 $T$ 第 $i$ 只变色龙的位置、颜色和方向。

其中 $0\le x_i<L$。

数据范围

• $1\le n\le 10^5$；
• $1\le L\le 10^9$；
• $0\le p_i<L$，且所有 $p_i$ 两两不同；
• $1\le c_i\le 10^9$；
• $d_i\in\{-1,1\}$；
• $0\le T\le 10^{18}$；
• 保证时刻 $T$ 没有两只变色龙恰好相遇。

样例

样例输入

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

样例输出

2 2 1
12 1 1
9 3 1
3 3 -1