Cho một mảng bao gồm \(N\) số nguyên. Một số phần tử sẽ được cập nhật, và sau mỗi lần cập nhật, nhiệm vụ của bạn là tìm tổng lớn nhất của tất cả các đoạn con (liên tiếp) trong mảng.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, Q\): Kích thước của mảng và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, ..., A_N\) \((|A_i| \leq 10^9)\).
• \(Q\) dòng tiếp theo, mỗi dòng có hai số nguyên \(k\) và \(x\) \((1 \leq k \leq N, |x| \leq 10^9)\): thay đổi phần tử \(k\) thành giá trị \(x\).

Output

• Sau mỗi lần cập nhật, in ra tổng lớn nhất của tất cả các đoạn con trong mảng. Các mảng con rỗng (với tổng bằng 0) vẫn được tính.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 2.10^5\).

Example

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

9
13
6