Uolevi on ohjelmoinut algoritmin, joka laskee taulukosta suurimman epätyhjän välin summan. Kuitenkin aina kun Uolevi on juuri saanut suoritettua algoritminsa, Kaaleppi käy vaihtamassa taulukosta yhden arvon, ja suoritus on taas aloitettava täysin alusta.

Tehtäväsi on laskea suurin yhtenäisen välin summa taulukossa aina jokaisen muutoksen jälkeen.

Syöte

Ensimmäisellä rivillä on luvut n ja k. n on taulukon pituus ja k on muutoksien lukumäärä.

Seuraavalla rivillä on n lukua a_1, a_2, \ldots, a_n, taulukon alkuarvot.

Seuraavat k riviä sisältävät muutokset. Jokainen muutos on kaksi välein eroteltua lukua i ja x, mikä tarkoittaa, että kohtaan i asetetaan arvo x.

Tuloste

Tulosta jokaista muutosta kohti yksi rivi, jolla lukee taulukon suurin epätyhjän välin summa muutoksen jälkeen.

Rajat

• 1\leq n\leq 10^5
• 1\leq k\leq 10^5
• -10^9\leq a_i\leq 10^9
• 1\leq i\leq n
• -10^9\leq x\leq 10^9

Esimerkki

Syöte:

5 3
1 2 -1 2 2
3 -5
1 4
3 -1

Tuloste:

4
6
9

Selitys:
Aluksi taulukko on [1 2 -1 2 2]
Muutos 3: -5, uusi taulukko [1 2 -5 2 2]
Suurin summa on välillä 4\ldots 5: 2 + 2 = 4
Muutos 1: 4, uusi taulukko [4 2 -5 2 2]
Suurin summa on välillä 1\ldots 2: 4+2=6
Muutos 3: -1, uusi taulukko [4 2 -1 2 2]
Suurin summa on välillä 1\ldots 5: 4+2-1+2+2=9