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, m\) \((1 \leq n, m \leq 2 \times 10^{5})\) - Kích thước của mảng và số truy vấn. Mảng được đánh chỉ số từ \(1\) đến \(n\).
• Dòng thứ hai gồm \(n\) số nguyên \(x_{1}, x_{2}, \ldots, x_{n}\) \((-10^{9} \leq x_{i} \leq 10^{9})\) - giá trị ban đầu của mảng.
• \(m\) dòng tiếp theo, mỗi dòng có hai số nguyên \(k\) và \(x\) \((1 \leq k \leq n, -10^{9} \leq x \leq 10^{9})\) - thay đổi phần tử ở vị trí \(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.

Example

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

9
13
6