Tổng Đoạn Liên Tiếp

Cho một dãy $a_1,a_2,\dots ,a_n$. Một đoạn con liên tiếp có dạng $a_l,a_{l+1},\dots ,a_r$. Ta cũng cho phép chọn đoạn rỗng, có tổng bằng $0$.

Có $m$ phép cập nhật. Sau mỗi lần gán một phần tử, hãy tìm tổng lớn nhất của một đoạn con liên tiếp trong toàn bộ dãy hiện tại.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên của dãy ban đầu.
• Mỗi dòng trong $m$ dòng tiếp theo chứa hai số $k$ $x$, nghĩa là gán $a_k=x$.

Output

• Sau mỗi cập nhật, in ra một dòng chứa tổng đoạn con liên tiếp lớn nhất. Kết quả không âm vì có thể chọn đoạn rỗng.

Constraints

• $1\le n,m\le 2\cdot 10^5$.
• $-10^9\le a_i,x\le 10^9$.
• $1\le k\le n$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5 4
-3 2 -1 4 -5
1 -2
5 3
2 -6
4 -8

5
8
7
3