Subarray Sum Queries

There is an array consisting of n integers. Some values of the array will be updated, and after each update, your task is to report the maximum subarray sum in the array.

Input

The first input line contains integers n and m: the size of the array and the number of updates. The array is indexed 1,2,\ldots,n. The next line has n integers: x_1,x_2,\ldots,x_n: the initial contents of the array. Then there are m lines describing the changes. Each line has two integers k and x: the value at position k becomes x.

Output

After each update, print the maximum subarray sum. Empty subarrays (with sum 0) are allowed.

Constraints

$1 \le n, m \le 2 \cdot 10^5$

$-10^9 \le x_i \le 10^9$

$1 \le k \le n$

$-10^$9 \le x \le 10^9$

Example

Input

5 3
1 2 -3 5 -1
2 6
3 1
2 -2

Output

9
13
6