Cho số nguyên \(n\) và dãy số nguyên không âm \(a_1,a_2,…,a_n\). Cho \(m\) truy vấn, mỗi truy vấn có dạng:

• \(i\) \(v\): thay đổi phần tử ở vị trí \(i\) thành giá trị \(v (1≤i≤n,0≤v≤10^9).\)

Yêu cầu: Trước tất cả thao tác và sau mỗi thao tác, tìm đoạn con có tổng lớn nhất của dãy.

Input

• Dòng thứ nhất chứa số nguyên \(n,m(1≤n,m≤10^5 )\).

• Dòng thứ 2 chứa \(n\) số nguyên \(a_1,a_2,…,a_n (0≤a_i≤10^9 );\)

• \(m\) dòng tiếp theo, mỗi dòng có dạng sau:

  • \(i\) \(v\): thay đổi phần tử ở vị trí \(i\) thành giá trị \(v (1≤i≤n,0≤v≤10^9).\)

Output

• Gồm \(m+1\) dòng:

  • Dòng 1: ghi tổng lớn nhất của đoạn con tìm được trước khi thực hiện tất cả thao tác.
  • Dòng thứ \(i\) trong \(m\) dòng tiếp theo, ghi tổng lớn nhất của đoạn con tìm được sau khi thực hiện thao tác thứ \(i\).

Ràng buộc

• Subtask 1: 50% test có \(n,m≤10^3.\)

• Subtask 2: 50% test có \(n,m≤10^5.\)

Sample Input

5 5
-9 4 -9 1 -3
4 4
4 -3
3 -4
5 0
2 -6

Sample Output

4
4
4
4
4
0