There are n dominoes lined straight up on a coordinate axis at positions x_i. Each domino has a height l_i. On pushing any particular domino, dominoes in the coordinates range [x_i + 1, x_i + l_i] (both inclusive) fall down and these dominoes may cascade further and push other dominoes. Calculate for each domino (independently), the maximum coordinate that can be reached by pushing it. (By independently, we mean that the process of pushing a domino is supposed to be carried out separately for each domino.)
Constraints :
1 <= n <= 10^5, 1 <= l_i, x_i <= 10^18
Input format:
There is a single test case. First line contains integer n. Each of the next n lines has x_i and l_i respectively, separated by a space.
The x_is are given in increasing order.
Output format:
Output n lines, each line containing the answer to the corresponding domino in the order in which they appear in the input.
Pushing any of the first three dominoes topples the third and stops the chain reaction making the maximum coordinate reached = 10. But the 5th domino on pushing topples no other domino, and only reaches up to 15.
