4717: 蚂蚁
[Creator : ]
Description
有许多蚂蚁在一根无限长的木棍上，每一只蚂蚁都有一个初始位置和初始朝向（任意两只蚂蚁的初始位置不同）。蚂蚁们以每秒一个单位的速度向前移动，当两只蚂蚁相遇时，它们会掉头（掉头时间忽略不计）。现给出每只蚂蚁的初始位置和初始朝向，请你计算出它们在 ttt 秒后的位置和朝向。
Input
第一行，两个空格隔开的整数 n,t (1≤n,t≤105)n,t\ (1\le n,t \le 10^5)n,t (1≤n,t≤105)，代表蚂蚁数和时间。
接下来 nnn 行，每行两个整数，分别为蚂蚁的初始位置 ai (−106≤ai≤106)a_i\ (-10^6\le a_i \le 10^6)ai (−106≤ai≤106) 及初始朝向 bib_ibi（bi=1b_i=1bi=1 时蚂蚁朝右，bi=−1b_i=-1bi=−1 时蚂蚁朝左）。
接下来 nnn 行，每行两个整数，分别为蚂蚁的初始位置 ai (−106≤ai≤106)a_i\ (-10^6\le a_i \le 10^6)ai (−106≤ai≤106) 及初始朝向 bib_ibi（bi=1b_i=1bi=1 时蚂蚁朝右，bi=−1b_i=-1bi=−1 时蚂蚁朝左）。
Output
n 行，每行两个整数，第 iii 行代表 ttt 秒后第 iii 只蚂蚁的位置及朝向（−1-1−1 表示朝左，111 表示朝右，000 表示正在转向中）。
Sample 1 Input
4 1
1 1
5 1
3 -1
10 1
Sample 1 Output
2 0
6 1
2 0
11 1