Falling Dominos

# D. Falling Dominos

#### Problem Statement

Tiger is bored in Health class so he is playing with $$n$$ dominos arranged in a straight line — the $$i$$-th domino has position $$x_i$$ and height $$h_i$$. Tiger is clumsy (unless he is only pretending to be) so he wondered, for each $$i$$ $$(1 \leq i \leq n)$$, how many dominos would fall if he were to knock over the $$i$$-th domino?

Note that Tiger is knocking over the dominos to the right, and if the $$i$$-th domino has been knocked over, it will knock over the $$j$$-th domino if $$x_i < x_j$$ and $$x_i + h_i \geq x_j$$ (and the $$j$$-th domino will fall to the same side as the $$i$$-th domino).

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 256mb

#### Constraints

$$1 \leq n \leq 2 \cdot 10^5$$
$$1 \leq x_i, h_i \leq 10^9$$
$$x_i < x_{i + 1}$$ for all $$1 \leq i < n$$

#### Input Format

The first line has one integer $$n$$
The next $$n$$ lines have two integers $$x_i$$ and $$h_i$$
It is guaranteed that the positions of the dominos are distinct.

#### Output Format

Output $$n$$ integers. For each $$i$$ $$(1 \leq i \leq n)$$ output the number of dominos that would fall if Tiger knocked over the $$i$$-th domino.

5
1 3
2 2
3 2
5 1
7 3

4 3 2 1 1

#### Sample Explanation

If you knock over the second domino, it reaches the third domino at $$x = 3$$, which then knocks over the fourth domino at $$x = 5$$. Thus the total number is $$3$$

Credit: Eggag