Cho một mảng số nguyên gồm \(n\) phần tử và \(q\) truy vấn. Mỗi truy vấn có dạng "\(p\ v\)": gán phần tử ở vị trí \(p\) trong mảng thành giá trị \(v\).

Sau mỗi truy vấn ta cần in ra tổng đoạn con liên tiếp (gồm các phần tử nằm liên tiếp nhau trên mảng) không rỗng có giá trị lớn nhất.

Input

• Dòng đầu tiên chứa \(2\) số nguyên dương \(n\) và \(q\): lần lượt là số lượng phần tử của mảng và số truy vấn \((1\leq n,\ q\leq2\times10^5)\);
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1,\ a_2,\ldots,\ a_n\), thể hiện giá trị của các phần tử trong mảng \((|a_i|\leq10^9)\);
• Tiếp theo là \(q\) dòng thể hiện \(q\) truy vấn, mỗi truy vấn có dạng "\(p\ v\)" \((1\leq p\leq n,\ |v|\leq10^9)\).

Output

• Sau mỗi truy vấn, in ra giá trị tổng lớn nhất trên một dòng.

Ví dụ

Sample input

5 4
5 -4 4 3 -5
5 3
4 -1
3 2
1 7

Sample output

11
7
5
7