Hay un arreglo que consiste en ~n~ enteros. Algunos valores en el arreglo se actualizarán, y después de cada actualización, su tarea es informar el subarreglo de suma máxima en el arreglo.

Entrada

La primera línea de entrada contiene los enteros ~N~ y ~M~: el tamaño del arreglo y el número de actualizaciones. El arreglo está indexada ~1,2, \ldots, n~. La siguiente línea tiene ~n~ enteros: ~x_1, x_2, \ldots, x_n~: el contenido inicial del arreglo. Luego hay ~m~ líneas que describen los cambios. Cada línea tiene dos enteros ~k~ y ~x~: el valor en la posición ~k~ se convierte en ~x~.

Salida

Después de cada actualización, imprima la suma máxima del subarreglo. Se permiten subarreglos vacíos (con suma 0).

Restricciones

• ~1 \leq n, m \leq 2 \cdot 10^5~
• ~-10^9 \leq x_i \leq 10^9~
• ~1 \leq k \leq n~
• ~-10^9 \leq x \leq 10^9~

Ejemplo de Entrada

5 3
1 2 -3 5-1
2 6
3 1
2 -2

Ejemplo de Salida

9
13
6