题目描述

有许多蚂蚁在一根无限长的木棍上，每一只蚂蚁都有一个初始位置和初始朝向（任意两只蚂蚁的初始位置不同）。蚂蚁们以每秒一个单位的速度向前移动，当两只蚂蚁相遇时，它们会掉头（掉头时间忽略不计）。现给出每只蚂蚁的初始位置和初始朝向，请你计算出它们在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