Cho một mảng 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.

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 2 \cdot 10^5)~: kích thước 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 \le x_i \le 10^9)~: giá trị ban đầu của mảng.

• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~k~ và ~x~ ~(1 \le k \le n,\ -10^9 \le x \le 10^9)~: thay đổi phần tử ở vị trí ~k~ thành giá trị ~x~.

Kết quả:

• 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.

Input

Output

Sample Input 1

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

Sample Output 1

9
13
6