Caen \(n\) cuadrados, uno tras otro, sobre una línea horizontal. El \(i\)-ésimo tiene lado \(s_i\) y su borde izquierdo en \(x_i\), así que ocupa el intervalo \([x_i, x_i + s_i)\). Cae verticalmente hasta apoyarse en el suelo o en el techo de un cuadrado ya caído que se solape con él con largo positivo (tocarse solo en un borde no cuenta) y queda ahí.

Después de cada caída, informa la altura de la pila más alta.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 5 \cdot 10^4)\). Cada una de las siguientes \(n\) líneas tiene \(x_i\) \((1 \le x_i \le 10^8)\) y \(s_i\) \((1 \le s_i \le 10^6)\).

Salida

Las \(n\) alturas máximas, separadas por espacios.

Ejemplo 1

Entrada

3
1 2
2 3
6 1

Salida

2 5 5

Ejemplo 2

Entrada

2
100 100
200 100

Salida

100 100

Ejemplo 3

Entrada

3
1 5
2 2
3 1

Salida

5 7 8