Hiếu rất thích làm bài trên Codeforces. Một lần, trong contest Hiếu gặp bài toán như sau: "Cho một dãy số có \(n\) \((n \leq 1000)\) số \(a_1,a_2,\dots,a_n\). Tìm hai chỉ số \(i<j\) sao cho \(a_i+a_j\) lớn nhất. Bạn phải giải bài toán cho \(t\) \((t\leq 10^3)\) trường hợp khác nhau. Biết rằng tổng các số n trong một input không vượt quá \(1000\)". "Quá đơn giản", Hiếu thốt lên và bắt tay ngay vào code thuật toán \(O(n^2)\) đỉnh cao mà anh chỉ tốn \(1000ms\) để nghĩ ra. Ơ mà khoan, mỗi trường hợp là \(n^2\), có \(t\) test, vậy tổng cộng là \(n^2∗t=10^9\) phép tính cơ mà. "TLE mất rồi", Hiếu suy sụp. Hiếu sau đó nghĩ ra được thuật \(O(n)\) và AC dễ dàng. Tuy nhiên, sau khi thử submit lại code \(O(n^2)\), anh lại nhận được dòng chữ AC trong sự ngỡ ngàng. Vì sao vậy? Để đơn giản bài toán, Hiếu đã viết lại đề như sau (các bạn không cần đọc phía trên đâu :)):

Cho hai số nguyên \(n, s\) và dãy số nguyên gồm \(n\) số \(a_1, a_2, \dots , a_n\). Hãy tìm dãy số nguyên \(x_1, x_2, \dots , x_n\) thỏa mãn:

• \(x_1 + x_2 + \dots + x_n \leq s\)
• \(x_i \geq a_i, i=1,2,\dots ,n\)
• \(A = x_1^2 + x_2^2 + \dots + x_n^2\) đạt giá trị lớn nhất

Bạn cần phải tìm giá trị lớn nhất của \(A\). Ngoài ra, bạn phải xử lý \(q\) truy vấn, mỗi truy vấn gồm hai số \(i,x\) và bạn cần update \(a_i=x\). Hãy in ra giá trị lớn nhất của \(A\) sau mỗi lần truy vấn.

Input

• Dòng đầu tiên bao gồm 2 số nguyên \(n, s\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots , a_n\).
• Dòng thứ ba chứa 1 số nguyên \(q\).
• \(q\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên \(i,x\) biểu diễn truy vấn cập nhật \(a_i=x\).

Output

• Hãy in ra \(q+1\) dòng. Dòng đầu chứa kết quả khi chưa thực hiện truy vấn nào, và \(q\) dòng sau chứa kết quả sau khi thực hiện mỗi truy vấn.

Constraints

• \(n \leq 10^5\)
• \(s \leq 10^9\)
• \(0 \leq a_i \leq 10^4\)
• \(q \leq 10^5\)
• \(1 \leq i \leq n\)
• \(0 \leq x \leq s\)
• Dữ liệu đảm bảo \(\sum_{i=1}^{n}a_i \leq s\) tại mọi thời điểm.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(q=0, a_i=0, \forall i=1,2,\dots, n\)
• Subtask \(2\) (\(20\%\) số điểm): \(q=0, a_1=a_2=\dots=a_n\)
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^3, q=0\)
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 10^5, q=0\)
• Subtask \(5\) (\(20\%\) số điểm): \(n \leq 10^5, q \leq 10^5\)

Example

3 4
1 1 1
0

6

3 5
1 1 1
3
1 2
2 2
1 1

11
11
9
11