蚂蚁

题目描述

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

输入

第一行，两个空格隔开的整数 n,t（代表蚂蚁数 n 和时间 t）。

第 2\sim n+1 行每行两个整数，第 i+1 行代表第 i 只蚂蚁的初始位置 a_i 及初始朝向 b_i（b_i=1 时蚂蚁朝右，b_i=-1 时蚂蚁朝左）。

输出

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

样例

提示

• 对于 40\% 的数据，1\le n\le 100；
• 对于 80\% 的数据，1\le n\le 10^4，0\le t\le 1000；
• 对于 100\% 的数据，n\le 10^5，0\le t\le 10^5，|a_i|\le 2\times 10^6。