Subarray Sum Queries

Source: CSES

Version: Phuoc Hung OJ Extended

You are given an array of $N$ integers and $Q$ point updates. An update gives $k,x$ and assigns $A_k=x$. After each update, print the maximum contiguous subarray sum of the whole array.

The empty subarray with sum $0$ is allowed.

Input

The first line contains $N,Q$.

The second line contains $A_1,\ldots,A_N$.

Each of the next $Q$ lines contains $k,x$.

Output

After every update, print the maximum subarray sum.

Subtasks

• Subtask 1 — 20%: $1\le N,Q\le 50$, $|A_i|,|x|\le 10^4$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$, $|A_i|,|x|\le 10^9$.
• Subtask 3 — 50%: $1\le N,Q\le 2\cdot 10^5$, $|A_i|,|x|\le 10^9$.

Examples

Input

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

Output

9
13
6

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.