题目描述

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

4 1
1 1
5 1
3 -1 
10 1

2 0
6 1
2 0
11 1

提示

数据范围及约定

• 对于 $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 10^6$。