1991 - contest1 D 小球碰撞

通过次数

0

提交次数

1

Time Limit : 2 秒
Memory Limit : 256 MB

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

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

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

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

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

Input

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

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

1 \leq n \leq 3 \times 10^5

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

Output

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

Examples

Input

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

Output

6 7
1 3
13 14

Hint

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