F. 棋局

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

「苍天如圆盖,陆地似棋局。世人黑白分,往来争荣辱。荣者自安安,辱者定碌碌。」
——罗贯中《三国演义·第三十七回》

Pac 善观万物往复,而小小棋盘有如世间缩影,尤为她所喜爱。今天闲来无事,她又发明了一种新的棋。

给出一个有 个格子水平排列的棋盘,从左到右标号为 到 ,游戏的开始时有 个棋子,标号为 ,标号为 的棋子在格子 上。

棋子可以重叠,我们默认标号小的格子位于标号大的格子上面。

现有 张行动卡片,行动卡片上指定了移动棋子的标号 和位移 ,使用卡片会使得标号 的棋子向右移动 格(注意位移可能为负值)。

当棋子移动到一个已经存在其他棋子的格子上时,移动的棋子会叠在目标位置所有棋子的上方,一个棋子移动时会使得其上方的所有棋子一起移动。

现在按照给出卡片的顺序依次进行操作,请输出操作结束后所有棋子所在的格子的位置。

输入格式

第 行三个整数 , 表示棋盘的大小,棋子的数量和行动卡片的数量。

第 行 个整数 表示棋子的初始位置。

第 行到第 行,每行两个整数 , 描述一张行动卡片,分别表示移动的棋子标号和位移。

保证对于所有用例,每次行动不会超出棋盘的范围。

输出格式

共一行 个整数,用空格隔开,第 个整数表示标号为 的棋子的最终位置。

样例

输入样例 1

9 3 12
2 3 4
1 1
1 1
1 2
2 1
2 1
1 -1
3 1
2 2
3 -1
2 -1
3 1
3 2

输出样例1

9 9 9

数据范围与提示

对于所有测试点,满足 。

对于20%的数据,。