1991 - contest1 D 小球碰撞
Time Limit : 2 秒
Memory Limit : 256 MB
小 i 最近在物理课上学了一些关于碰撞的知识,所以他打算应用并试验之。
小 i 在一根数轴上摆放了若干质量相同且宽度相同的长方体刚体,每个长方体都会在数轴上占用一定的空间,具体地,对于第 i 个长方体,将会占据数轴上 (l_i, r_i) 的这一段区间,每一个长方体还有一个初始速度 v,v > 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,尽量避免使用。