Sinulla on taulukko, jossa on n lukua. Taulukon sisältöön tulee muutoksia, ja tehtäväsi on ilmoittaa joka muutoksen jälkeen suurin yhtenäisen välin summa taulukossa.

Syöte

Syötteen ensimmäinen rivi sisältää kokonaisluvut n ja m: taulukon koko ja muutosten määrä. Taulukon kohdat on numeroitu kokonaisluvuin 1,2,\ldots,n.

Seuraavalla rivillä on n kokonaislukua x_1,x_2,\ldots,x_n: taulukon sisältö.

Sitten syötteessä on m riviä, joista jokainen kuvaa yhden muutoksen. Rivillä on kaksi kokonaislukua k ja x: kohtaan k tulee luku x.

Tuloste

Ohjelmasi tulee tulostaa jokaisen muutoksen jälkeen suurin yhtenäisen välin summa taulukossa.

On sallittua, että väli on tyhjä, jolloin sen summa on 0.

Rajat

• 1 \le n, m \le 10^5
• -10^9 \le x_i \le 10^9
• 1 \le k \le n
• -10^9 \le x \le 10^9

Esimerkki

Syöte:

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

Tuloste:

9
13
6