UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2912. [Poi1997]Jump

Statistics 下载数据

Description

在一个无限长的棋盘上玩一种跳棋游戏,其中棋盘被划分成许多区域,每一个区域中可以放置多个的棋子。规定某一个区域的编号为0,在它开始往左边连续的区域编号为-1-2-3,在它的右边连续区域编号为123,若区域P有棋子,那么棋子有两种跳法:

向左跳:则方格P-1P-2中应增加一枚棋子,方格P中应减少一枚棋子。

向右跳:则方格PP+1中应减少一枚棋子,方格P+2中应增加一枚棋子。

对于给定的初始棋局,经过若干步跳棋后,总可以找到一种目标,就是任意两个相邻的区域棋子数目不超过1

       你的任务是对给定的一种初始棋局,找到最终的目标棋局。

Input

第一行为一个正整数n, 1 <= n <= 10000, 表示棋盘中放置棋子的状态数,下面的n行描述了每个状态,由两个用空格分隔的整数组成,第一个整数表示区域的位置(不超过10000),第二个整数表示该区域放置的棋子数目(不超过100000000).

Output

写入最终的棋局,这一行包含若干个整数,其中每一个整数为有棋子的区域编号,所有的区域按从小到大排列。

Sample Input

2
0 5
3 3

Sample Output

-4 -1 1 3 5

Hint

Source