You need to maintain two sequences $a_1, \dots, a_n$ and $b_1, \dots, b_n$, both initially set to $0$.

There are $m$ operations. Each operation provides $x$ and $y$, updates $a_x$ to $y$, then for each $i=1, \dots, n$, adds $\max\limits_{j=1}^i a_j$ to $b_i$, and finally queries $\sum\limits_{i=1}^x b_i$.

Input

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain two integers $x$ and $y$, representing an operation.

Output

Output $m$ lines, each containing an integer representing the answer.

Examples

Input 1

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

Output 1

4
2
10
8
47
14

Subtasks

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: ccz181078

For $100\%$ of the data, $1\le n, m\le 10^6$ and $1\le x, y\le n$.