坡旅甲开始了自己的事业。明天就是他的汽车修理店的第一个工作日。目前修车店规模很小,一次只能修一辆车。
Polycarp擅长营销,因此他已经收集了n个客户的请求。请求按照到达的顺序从 1 到 n 进行编号。
第 i 个请求有两个值:si — 客户想要开始维修汽车的日期,di — 维修汽车的持续时间(以天为单位)。天数从1开始计数,第一天是明天,第二天是后天,以此类推。
Polycarp 正在按照从第一个请求到第 n 个请求的顺序处理请求来制定计划。他将第 i 个请求安排如下:
- 如果汽车修理店从 si (si, si + 1, ..., si + di - 1) 开始闲置了 di 天,则这些天用于修理第 i 个客户的汽车。
- 否则,Polycarp 会发现第一天 x(从 1 开始),从 x 开始,有 di 个后续天没有安排修复。换句话说,他选择所有 x, x + 1, ..., x + di - 1 天内不安排修理任何汽车的最小正 x。因此,第 i 个客户的汽车将在 [x, x + di - 1] 范围内进行维修。计划开始修复的日期 x 可能会小于 si。
给定 n 个请求,您需要帮助 Polycarp 根据上述规则安排所有请求。
输入
第一行包含整数 n (1 ≤ n ≤ 200) — 来自客户端的请求数。
以下 n 行包含请求,每行一个请求。第 i 个请求以整数对 si、di (1 ≤ si ≤ 109, 1 ≤ di ≤ 5·106) 的形式给出,其中 si 是开始维修第 i 辆车的首选时间,di 是维修第 i 辆车的天数。
请求应按照输入中给出的顺序进行处理。
输出
打印 n 行。第 i 行应包含两个整数 - 修理第 i 辆车的开始日期和修理第 i 辆车的结束日期。
示例
输入 #1
3 9 2 7 3 2 4
输出 #1
9 10 1 3 4 7
输入 #2
4 1000000000 1000000 1000000000 1000000 100000000 1000000 1000000000 1000000
输出 #2
1000000000 1000999999 1 1000000 100000000 100999999 1000001 2000000