#P1367. 蚂蚁

蚂蚁

题目描述

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

输入格式

第一行,两个空格隔开的整数 n,tn,t(代表蚂蚁数 nn 和时间 tt)。

2n+12\sim n+1 行每行两个整数,第 i+1i+1 行代表第 ii 只蚂蚁的初始位置 aia_i 及初始朝向 bib_ibi=1b_i=1 时蚂蚁朝右,bi=1b_i=-1 时蚂蚁朝左)。

输出格式

nn 行,每行两个整数,第 ii 行代表 tt 秒后第 ii 只蚂蚁的位置及朝向(1-1 表示朝左,11 表示朝右,00 表示正在转向中)。

4 1
1 1
5 1
3 -1 
10 1

2 0
6 1
2 0
11 1

提示

数据范围及约定

  • 对于 40%40\% 的数据,1n1001\le n\le 100
  • 对于 80%80\% 的数据,1n1041\le n\le 10^40t10000\le t\le 1000
  • 对于 100%100\% 的数据,n105n\le 10^50t1050\le t\le 10^5ai106|a_i|\le 10^6