Recientemente Byteland abrió un restaurante japonés, y las cosas no funcionan muy bien. A veces, los clientes obtienen mucha comida esperando, y ahora cree que comprende por qué sucede esto.

El restaurante no tiene comidas, sino una barra muy larga con una escalera mecánica que transporta alimentos de la cocina al cliente. El bar cuenta con ~500.000.000~ sillas numeradas en ese orden.

La silla ~1~ es la más cercana a la cocina. A veces los clientes hacen nuevos pedidos. Un comando (pedido) realizado en ~T~ segundos por el cliente en el asiento ~P~ llegará instantáneamente a la cocina.

La preparación de la comida tomará ~D~ segundos y luego la comida se colocará en la cinta mecánica y tomará exactamente ~P~ segundos para llegar al cliente. Mientras tanto, la comida pasará por los asientos ~1, 2, ... P-1~.

Si, por alguna razón, el cliente no levanta sus alimentos en la cinta, seguirá moviéndose. De lo contrario, el cliente en cuestión espera que la comida llegue a su asiento en ~T + D + P~ segundos.

Por el momento, el restaurante sirve un plato único: papitas fritas. Por lo tanto, los pedidos de los clientes son fácilmente intercambiables, y están muy abiertos a aprovechar este hecho.

Se conocen los siguientes:

▪ Un cliente puede tener cero o más pedidos pendientes.

▪ Un cliente con cero comandos en cola está completamente inactivo.

▪ El número de órdenes pendientes de un cliente que hace un paquete por ~T~ segundos aumentará en una unidad por ~T~ segundo.

▪ Un cliente que tiene al menos una orden recogerá la primera parte del plato de papas fritas que se encuentra frente a él, ya sea que esté destinado o no. Si lo hace a la hora ~T~, su número de pedido pendiente se reducirá en una unidad exactamente a la hora ~T~.

Por ejemplo, analizamos lo siguiente con dos comandos:

La duración de la preparación del plato de papas fritas es ~D = 2~ segundos. Este valor es una constante y se aplica lo mismo a cada comando.

En el segundo ~T1 = 10~, la persona en el asiento con el número ~P1 = 8~ (para llamarlo ~A~) ordena un plato de papas fritas. En el segundo ~T1 + D = 12~, su pedido se coloca en la cinta.

En el segundo ~T2 = 16~, la persona en el asiento con el número ~P2 = 6~ (llámelo ~B~) ordena un plato de papas fritas. En el segundo ~T2 + D = 18~, su pedido se coloca en la cinta.

A los ~18~ segundos, el pedido del cliente ~A~ pasa por delante de la silla ~6~, y el cliente ~B~, estando él mismo esperando el pedido, lo tomará y lo comerá. Comerá en el ~18~ y luego ignorará su propio comando, que pasará por él.

En el segundo ~26~, el pedido para el cliente ~B~ llegará al cliente ~A~, y él la tomará y la comerá. Por lo tanto, comerá a los ~26~ segundos.

Se observa que, en general, a pesar de los retrasos creados, cada cliente consumirá exactamente cuántas porciones ha pedido.

Tarea

Para evaluar el impacto de esta costumbre en el tiempo de espera, se obtuvieron datos sobre todos los comandos dados en el día actual. Usted propone averiguar para cada pedido el siguiente valor: si ese pedido es realizado por ese cliente, ¿cuál es el segundo al que el cliente en cuestión comerá a NO?

Entrada

La entrada contendrá en la primera línea el número de comandos ~N~, respectivamente y el tiempo ~D~ de preparación de un plato. Las siguientes ~N~ líneas contendrán un par de números: ~T[i]~, el segundo al que se le manda respectivamente y ~P[i]~, el número del asiento desde el que se le ordenó. Se garantiza que los tiempos de control son distintos y se reproducen en el orden de sus lecturas.

Salida

La salida contendrá ~N~ líneas, cada una con un solo valor entero: el ~i-esimo~ valor representará la respuesta requerida para ordenarlo en el orden de lectura.

Restricciones y aclaraciones.

~1 \le N \le 100 000~

~0 \le D, T[i] \le 500 000 000~, para todo ~1 \le i \le N~

~1 \le P[i] \le 500 000 000~, para todo ~1 \le i \le N~

Se garantiza que ~T[i] < T[i+1]~, para todo ~1 \le i \le N~

Para las pruebas que totalizan ~22~ puntos, se garantiza, además que restricciones generales, para ~N \le 2000~ si ~D, T[i], P[i] \le 5000~

Para otras pruebas que suman ~25~ puntos, se garantiza además de las restricciones generales que ~N \le 2000~

Ejemplo de Entrada #1

 2 2
 10 8
 16 6

Ejemlo de Salida #1

26
18

Explicación: El ejemplo descrito en la declaración.

Ejemplo de Entrada #2

3 2
5 4
6 4
7 3

Ejemlo de Salida #2

12
13
10

Explicación: Tenga en cuenta que en este ejemplo el cliente en el asiento con el número 4 hace dos órdenes. La respuesta a la primera orden, es la segunda vez que el cliente come por primera vez, y La respuesta a la segunda orden es la segunda donde el cliente está comiendo por segunda vez.

Ejemplo de Entrada #3

3 0
0 6
3 3
4 5

Ejemlo de Salida #3

10
3
8

Explicación: Tenga en cuenta que en este ejemplo el cliente en el asiento con el número 3 hace un comando de pedido al segundo 3. Exactamente al mismo tiempo que aparece un plato de papas fritas al frente, e inmediatamente lo consume.