题目描述

小 i 最近在物理课上学了一些关于碰撞的知识，所以他打算应用并试验之。

小 i 在一根数轴上摆放了若干质量相同且宽度相同的长方体刚体，每个长方体都会在数轴上占用一定的空间，具体地，对于第 $i$ 个长方体，将会占据数轴上 $(l_i, r_i)$ 的这一段区间，每一个长方体还有一个初始速度 $v$，$v > 0$ 则表示长方体接下来会朝着数轴正方向移动，$v < 0$ 则反之。

长方体在进行运动的时候会不可避免地与别的长方体产生弹性碰撞（即没有能量损失的碰撞，在质量相同的情况下，二者速度会发生交换）。现在，你需要求出在 $s$ 秒之后每一个长方体的位置。

保证初始情况中任意两个长方体不会发生重叠。

长方体的速度 $v$ 代表在 $1$ 秒内长方体会向相应方向运动 $|v|$ 个单位长度。

输入格式

第一行两个整数 $n, s$ 代表长方体的数量和运动的秒数。

接下来 $n$ 行第 $i$ 行包含三个整数 $l_i, r_i, v_i$ 表示第 $i$ 个长方体的位置和速度。

$1 \\leq n \\leq 3 \ imes 10^5$

$-10^9 \\leq v_i, l_i, r_i \\leq 10^9$

输出格式

输出包含 $n$ 行，每一行包含两个数 $l_i, r_i$ 代表第 $i$ 个长方体的位置，两个整数使用一个空格隔开。

样例

3 5 
2 3 2 
-1 1 1 
4 5 0

6 7 
1 3 
13 14

提示

cin 和 cout 可能会导致 TLE，尽量避免使用。