时空限制

1S/512M

题目描述

一家繁忙的银行开设了两个服务窗口（编号为 1 和 2）和一个用于排队的等候区。

现在有 $n$ 位客户，每位客户在特定的时刻 $T_i$ 到达银行，并且需要 $a_i$ 的服务时间。银行的运作规则如下：

1. 当一位客户到达时，他会首先查看是否有空闲的服务窗口。
   • 如果至少有一个窗口是空闲的，他会立即上前办理业务。如果两个窗口都空闲，他会选择 $1$ 号窗口。
   • 如果两个窗口都在忙，他会进入等候区的队伍末尾排队。
2. 当一个窗口完成当前客户的业务后，它会立即变为空闲状态。在它变为空闲的那一刻，如果等候区的队伍里有人，队首的客户会立即离开队伍，到这个刚空闲的窗口开始办理业务。
3. 如果两位客户在同一时刻到达，输入顺序靠前的客户优先进行判断和选择。
4. 如果两个窗口在同一时刻变为空闲，并且队伍中有至少一位客户，队首的客户会选择去 $1$ 号窗口。

注意：由于银行的记录系统有些混乱，给出的 $n$ 位客户信息并不保证是按到达时刻排序的。

请你为每位客户计算出他们完成业务并离开银行的确切时刻。

格式

输入格式

第一行包含一个整数 $n$，表示客户的数量。

接下来 $n$ 行，每行包含两个整数 $T_i, a_i$，分别表示第 $i$ 位客户的到达时刻和服务所需时间。

输出格式

输出 $n$ 行，每行一个整数。第 $i$ 行的整数表示第 $i$ 位客户离开银行的时刻。

样例

样例输入 #1

3
4 4
5 1
6 2

样例输出 #1

8
6
8

数据规模

对于 $20\%$ 的数据，$1 \le n \le 10^5$，$1 \le T_i , a_i \le 1000$。

对于 $50\%$ 的数据，$1 \le n \le 10^5$，$1 \le T_i , a_i \le 10^9$。且保证输入按 $T_i$ 非递减顺序给出。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le T_i , a_i \le 10^9$。