Bomb Chain Reaction

You are given n bombs on a straight line. The i-th bomb is located at coordinate \(x_i\) and has an explosion radius \(r_i\). When a bomb explodes, any other bomb at position \(x_j\) will be triggered if

[ |x_j - x_i| \le r_i, ]

The explosion proceeds in a chain reaction; that is, when a bomb is triggered, it in turn may trigger additional bombs in its explosion range. For each bomb, if it is the first one to be detonated, compute the total number of bombs that will eventually explode (including the initial one). Since the answer can be large, output it modulo \(10^9+7\).

inputFormat

The first line contains a single integer \(n\) (the number of bombs). Each of the following \(n\) lines contains two integers \(x_i\) and \(r_i\), representing the coordinate and explosion radius of the \(i\)-th bomb.

It is guaranteed that the input values are such that a solution with an \(O(n^2)\) algorithm can pass the given test cases.

outputFormat

Output \(n\) integers separated by a space. The \(i\)-th integer represents the total number of bombs that will be triggered if the \(i\)-th bomb is detonated first, modulo \(10^9+7\).

sample

3
1 1
3 1
6 1

1 1 1