你需要维护两个初值为 $0$ 的序列 $a_1,\dots,a_n$ 和 $b_1,\dots,b_n$ ；

共 $m$ 次操作，每次操作给出 $x,y$ ，将 $a_x$ 修改为 $y$ ，然后对 $i=1,\dots,n$ 将 $b_i$ 加上 $\max\limits_{j=1}^i a_j$ ，然后查询 $\sum\limits_{i=1}^x b_i$。

输入格式

第一行两个整数 $n,m$；

接下来 $m$ 行，每行两个整数 $x,y$ 表示一次操作。

输出格式

共 $m$ 行，每行一个整数表示答案。

样例数据

样例输入

5 6
3 4
1 2
2 4
1 4
3 5
1 2

样例输出

4
2
10
8
47
14

子任务

Idea：nzhtl1477，Solution：nzhtl1477，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$1\le x,y\le n$。