题目描述

Polycarp 是一个汽车修理人。明天是他的汽车修理店的第一个工作日。但是现在汽车修理店很小，一次只能修理一辆车。

现在他已经收集了客户的要求。顾客请求按顺序从1到 n 排列。

第 i 个请求有两个值：s i：客户想要开始修理他的汽车的日期，d i：修理汽车的时间(单位: 天)。天数从1开始计算。

Polycarp 通过按照从第一个到第 n 个请求的顺序处理请求来制定时间表。他将第 i 项请求安排如下：

• 如果汽车修理店从第s i 天开始持续修理d i 天，那么这些天被用来修理第 i 个客户的汽车。
• 有时，polycarp 会发现从第x天 (从x及以后开始)有 d i 天没有计划进行维修。换句话说，在 x,x + 1,..., x + d i-1这几天中没有计划修理任何汽车。因此，第二个客户的汽车将在[x，x + d i -1]范围内提前修复。修复计划开始的日期 x 可能小于 s i。

给出 n 个顾客的要求，请你帮助 polycarp 按照上面的规则安排所有顾客的要求。

输入格式

第一行为整数 n (1 < = n < = 200) 表示来自客户的请求数。

下面的 n 行包含请求，每行一个请求。第i个请求为整数s i，d i (1 < = s i < = 10 ^ 9,1 < = d i < = 5*10 ^ 6) ，其中 s i 是开始修理第i辆车的时间，d i 是修理第i辆车的天数。

顾客的请求应该按照输入中给定的顺序进行处理。

输出格式

输出n行。第i行应该包含两个整数，即修理第i节车厢的开始日和修理第i节车厢的结束日。