Car Repair Shop

题意翻译

### 题目描述 Polycarp 开始创业了，明天他将开始汽车修理。目前，汽车修理厂非常小，不能同时修理多辆汽车。 Polycarp 已经从客户那里收集了 $n$ 个请求。请求编号从 $1$ 到 $n$。 第 $i$ 个请求包含两个值：$s_i$ 为客户希望开始维修其汽车的日期，$d_i$ 为维修汽车所需天数。天数从 $1$ 开始计算，第一天是明天，第二天是后天，依此类推。 Polycarp 从 $1$ 到 $n$ 依次考虑每个请求，对于第 $i$ 个请求： - 如果 $\left[s_i,s_i+d_i-1\right]$ 这些天修理厂是闲置的，那么 $\left[s_i,s_i+d_i-1\right]$ 这些天就用来修理第 $i$ 个客户的车子 - 否则就找到最小的一个 $x$，满足 $\left[x,x+d_i-1\right]$ 这些天工厂是闲置的，然后把 $\left[x,x+d_i-1\right]$ 这些天用来修理第 $i$ 个客户的车子 给出 $n$ 个请求，请求出每个客户的车子是在那些天被修理的。 ### 输入格式 第一行一个整数 $n$。 接下来 $n$ 行，每行两个正整数，即 $s_i$ 和 $d_i$。 你应该按输入的顺序依次处理每一组询问。 ### 输出格式 输出 $n$ 行，每行两个正整数，分别表示第 $i$ 个客户的汽车开始修理的日期和结束修理的日期。

题目描述

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.

输入输出格式

输入格式

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}<=10^{9} $ , $ 1<=d_{i}<=5·10^{6} $ ), 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.

输出格式

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.

输入输出样例

输入样例 #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