### 问题描述 一如既往，小辫子酱坐的列车又延误了。这一次，她选择观察每节车厢的乘客来消磨时间。 这辆列车上有 $n$ 个车厢，编号分别为 $1,2,\dots,n$。每个车厢要么是空的，要么坐满了乘客。坐满乘客的车厢会产生一个乘客的情绪值，第 $i$ 节车厢的情绪值为 $v_i$。特别地，空的车厢情绪值为 $0$。初始所有车厢都是空的。这辆列车的价值为**非空**连续车厢情绪值总和的最大值。例如，假设当前列车的情绪值为 $[1,1,0,4,0,5,1,0,4]$，那么非空的连续车厢一共有 $[1,1]$， $[4]$， $[5,1]$， $[4]$ 这四段，其中最大值为 $5+1 = 6$，因而当前列车的价值为 $6$。 小辫子酱观察了 $q$ 次乘客上下车，第 $i$ 次观察中，编号 $x_i$ 车厢的情绪值变为了 $v_i$。如果 $v_i = 0$ 说明该车厢变为空。在每次观察中，小辫子酱想知道当前列车的价值为多少。请你帮帮她。 ### 输入格式 第一行两个整数 $n,q \space (1 \leq n,q \leq 5 \times 10^4)$，代表列车的长度和观察次数。 接下来 $q$ 行，第 $i$ 行两个整数 $x_i,v_i \space (1 \leq x_i \leq n,0 \leq v_i \leq 10^6)$，代表编号 $x_i$ 车厢的情绪值变为了 $v_i$。 ### 输出格式 输出 $q$ 行，每行一个整数，代表每次车厢情绪值变动后，列车的情绪值。 ### 样例输入 ``` 9 12 1 1 2 9 3 1 4 9 5 8 6 1 7 0 8 7 9 6 3 0 5 1 4 0 ``` ### 样例输出 ``` 1 10 11 20 28 29 29 29 29 18 13 13 ```