蚂蚁

题目描述

有许多蚂蚁在一根无限长的木棍上,每一只蚂蚁都有一个初始位置和初始朝向(任意两只蚂蚁的初始位置不同)。蚂蚁们以每秒一个单位的速度向前移动,当两只蚂蚁相遇时,它们会掉头(掉头时间忽略不计)。现给出每只蚂蚁的初始位置和初始朝向,请你计算出它们在t秒后的位置和朝向。

输入输出格式

输入格式


第一行,两个空格隔开的整数n,t(代表蚂蚁数n和时间t) 第2~n+1行每行两个整数,第i+1行代表第i只蚂蚁的初始位置ai(ai的绝对值在1000000以内)及初始朝向bi(bi=1时蚂蚁朝右,bi=-1时蚂蚁朝左)

输出格式


n行,每行两个整数,第i行代表t秒后第i只蚂蚁的位置及朝向(-1表示朝左,1表示朝右,0表示正在转向中)

输入输出样例

输入样例 #1

4 1
1 1
5 1
3 -1 
10 1

输出样例 #1

2 0
6 1
2 0
11 1

说明

【数据范围】 对于40%的数据,n<=100 对于80%的数据,n<=10000,t<=1000 对于100%的数据,n<=100000,t<=100000