CF730G.Car Repair Shop

Polycarp starts his own business. Tomorrow will be the first working day of his car repair shop. For now the car repair shop is very small and only one car can be repaired at a given time.

Polycarp is good at marketing, so he has already collected n requests from clients. The requests are numbered from 1 to n in order they came.

The i-th request is characterized by two values: s__i — the day when a client wants to start the repair of his car, d__i — duration (in days) to repair the car. The days are enumerated from 1, the first day is tomorrow, the second day is the day after tomorrow and so on.

Polycarp is making schedule by processing requests in the order from the first to the n-th request. He schedules the i-th request as follows:

• If the car repair shop is idle for d__i days starting from s__i (s__i, s__i + 1, ..., s__i + d__i - 1), then these days are used to repair a car of the i-th client.
• Otherwise, Polycarp finds the first day x (from 1 and further) that there are d__i subsequent days when no repair is scheduled starting from x. In other words he chooses the smallest positive x that all days x, x + 1, ..., x + d__i - 1 are not scheduled for repair of any car. So, the car of the i-th client will be repaired in the range [x, x + d__i - 1]. It is possible that the day x when repair is scheduled to start will be less than s__i.

Given n requests, you are asked to help Polycarp schedule all of them according to the rules above.

波利卡普创办了自己的企业。明天将是他的汽车修理店首个营业日。目前，这家汽车修理店规模很小，同一时间只能修理一辆汽车。

波利卡普擅长市场营销，因此他已经收到了来自客户的 $n$ 个请求。这些请求按到达顺序编号为 $1$ 到 $n$。

第 $i$ 个请求由两个值刻画：$s_i$ —— 客户希望开始修车的日期；$d_i$ —— 修车所需天数（以天为单位）。日期从 $1$ 开始编号，第 $1$ 天是明天，第 $2$ 天是后天，依此类推。

波利卡普按照从第 $1$ 个到第 $n$ 个请求的顺序处理请求，并据此制定日程安排。他安排第 $i$ 个请求的方式如下：

• 若汽车修理店在从第 $s_i$ 天起连续 $d_i$ 天（即第 $s_i,\ s_i+1,\ \dots,\ s_i+d_i-1$ 天）均空闲，则将这 $d_i$ 天用于修理第 $i$ 位客户的汽车；
• 否则，波利卡普寻找第一个满足条件的日期 $x$（从 $1$ 开始向后查找），使得从第 $x$ 天起连续 $d_i$ 天均未被安排任何修车任务。换言之，他选择最小的正整数 $x$，使得第 $x,\ x+1,\ \dots,\ x+d_i-1$ 天均未被占用。于是，第 $i$ 位客户的汽车将在区间 $[x,\ x+d_i-1]$ 内完成修理。注意，实际安排的起始日 $x$ 可能小于客户期望的起始日 $s_i$。

给定 $n$ 个请求，请你帮助波利卡普依据上述规则为所有请求制定日程安排。

The first line contains integer n (1 ≤ n ≤ 200) — the number of requests from clients.

The following n lines contain requests, one request per line. The i-th request is given as the pair of integers s__i, d__i (1 ≤ s__i ≤ 109, 1 ≤ d__i ≤ 5·106), where s__i is the preferred time to start repairing the i-th car, d__i is the number of days to repair the i-th car.

The requests should be processed in the order they are given in the input.

第一行包含一个整数 $n$（$1 \leq n \leq 200$）——表示客户请求的数量。

接下来的 $n$ 行每行包含一个请求。第 $i$ 个请求以一对整数 $s_i,\,d_i$（$1 \leq s_i \leq 10^9$，$1 \leq d_i \leq 5 \cdot 10^6$）给出，其中 $s_i$ 表示第 $i$ 辆汽车维修的首选开始时间，$d_i$ 表示维修第 $i$ 辆汽车所需的天数。

请求应按照输入中给出的顺序依次处理。

Print n lines. The i-th line should contain two integers — the start day to repair the i-th car and the finish day to repair the i-th car.

输出 n 行。第 i 行应包含两个整数——第 i 辆车开始维修的日期和完成维修的日期。