Sequence Update and Query

You are given two sequences \(a_1,\dots,a_n\) and \(b_1,\dots,b_n\) initialized to 0. There are \(m\) operations. In each operation, you are given two integers \(x\) and \(y\). You must perform the following steps:

• Set \(a_x = y\).
• For each \(i=1,\dots,n\), update \(b_i = b_i + \max\limits_{j=1}^{i} a_j\).
• Output the query \(\sum\limits_{i=1}^{x} b_i\).

Please note that the maximum in the update is taken over the current state of \(a\) (after the update in this operation). The answer for each operation must be printed on a new line.

inputFormat

The first line contains two integers (n) and (m) representing the number of elements in each sequence and the number of operations respectively. Each of the following (m) lines contains two integers (x) and (y), describing an operation as follows:

1. Set (a_x = y).
2. For each (i = 1, \dots, n), update (b_i = b_i + \max_{j=1}^{i} a_j).
3. Then, output (\sum_{i=1}^{x} b_i).

outputFormat

For each of the (m) operations, output a single line containing the query result: (\sum_{i=1}^{x} b_i) after performing the update.

sample

5 3
3 5
2 2
5 3

5
2
49