Sông Big Flat của xứ Flatland rất giàu tôm cá và toàn bộ con sông (từ đầu nguồn đến cửa biển) đều nằm trong Flatland. Dọc theo sông có ~n~ xí nghiệp đánh bắt và chế biến thủy sản, được đánh số từ ~1~ (thượng nguồn) đến ~n~ (hạ lưu).

Xí nghiệp thứ ~i~ ban đầu sở hữu quyền đánh bắt trên một đoạn sông liên tiếp có độ dài ~a_i~. Các đoạn này ghép kín toàn bộ con sông: không có đoạn nào bị bỏ trống và mỗi đoạn chỉ thuộc một xí nghiệp.

Thuế tài nguyên của một xí nghiệp bằng bình phương độ dài đoạn sông mà xí nghiệp đó đang sở hữu, tức là nếu xí nghiệp sở hữu độ dài ~L~ thì thuế là ~L^2~.

Trong quá trình hoạt động có ~k~ lần biến động, mỗi biến động được mô tả bởi cặp ~ (e, c) ~:

• ~e~ là loại sự kiện (~e = 1~ hoặc ~e = 2~),
• ~c~ là số thứ tự tính từ thượng nguồn của xí nghiệp xảy ra sự kiện tại thời điểm đó (sau các biến động trước đó).

Quy tắc biến động:

• Sự kiện loại 2 (tách xí nghiệp): xí nghiệp thứ ~c~ có đoạn sông độ dài ~L~ sẽ tách thành 2 xí nghiệp độc lập liền kề nhau theo thứ tự thượng nguồn → hạ lưu.

  • Nếu ~L~ chẵn: chia thành ~L/2~ và ~L/2~.
  • Nếu ~L~ lẻ: chia thành hai phần chênh nhau ~1~, trong đó xí nghiệp gần thượng lưu hơn nhận phần ngắn hơn (tức là nhận ~⌊L/2⌋~, phần còn lại là ~⌈L/2⌉~).

• Sự kiện loại 1 (phá sản): xí nghiệp thứ ~c~ bị giải thể, đoạn sông độ dài ~L~ của nó được chuyển cho các xí nghiệp liền kề.

  • Nếu chỉ có một xí nghiệp liền kề (tức là ~c~ ở đầu hoặc cuối danh sách): xí nghiệp đó nhận toàn bộ ~L~.
  • Nếu có hai xí nghiệp liền kề: đoạn ~L~ được chia thành 2 phần theo quy tắc như khi tách (nếu lẻ thì phần của xí nghiệp gần thượng lưu hơn ngắn hơn). Xí nghiệp liền kề thượng lưu nhận phần ngắn hơn, xí nghiệp liền kề hạ lưu nhận phần dài hơn.

Sau mỗi biến động, các xí nghiệp còn lại (và các xí nghiệp mới sinh ra) được đánh số lại từ ~1~ theo thứ tự thượng nguồn → hạ lưu.

Kiểm toán cần tính lại tổng số thuế phải thu:

• lúc ban đầu,
• và sau mỗi biến động.

Yêu cầu

In ra ~k+1~ giá trị:

• giá trị thứ ~1~: tổng ~(\sum L_i^2)~ ban đầu,
• giá trị thứ ~t+1~: tổng thuế sau biến động thứ ~t~ (với ~t = 1..k~).

Dữ liệu

• Dòng 1: hai số nguyên ~n~ và ~p~ (trong đó ~p~ là mã nhóm test dùng để chấm điểm).
• Dòng 2: ~n~ số nguyên ~a_1, a_2, ..., a_n~.
• Dòng 3: số nguyên ~k~.
• ~k~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~e~ và ~c~ mô tả một biến động.

Kết quả

Ghi ra ~k+1~ dòng, mỗi dòng là một số nguyên — tổng số thuế tương ứng (ban đầu và sau mỗi biến động).

Ví dụ

Ví dụ 1

Input

4 0
3 5 5 4
5
1 1
2 1
1 3
2 2
1 3

Output

75
105
73
101
83
113

Giải thích

Ví dụ 1

Ban đầu các độ dài: ~[3, 5, 5, 4]~ Tổng thuế: ~3^2 + 5^2 + 5^2 + 4^2 = 9 + 25 + 25 + 16 = 75~.

1. Sự kiện ~ (1, 1) ~: xí nghiệp 1 phá sản, chỉ có xí nghiệp kề bên (xí nghiệp 2) nhận toàn bộ ~3~ → ~[8, 5, 4]~, thuế: ~8^2 + 5^2 + 4^2 = 64 + 25 + 16 = 105~.

2. Sự kiện ~ (2, 1) ~: xí nghiệp 1 có ~8~ tách đều thành ~4~ và ~4~ → ~[4, 4, 5, 4]~, thuế: ~16 + 16 + 25 + 16 = 73~.

3. Sự kiện ~ (1, 3) ~: xí nghiệp 3 có ~5~ phá sản, hai xí nghiệp kề là độ dài ~4~ (thượng lưu) và ~4~ (hạ lưu). Chia ~5~ thành ~2~ và ~3~, thượng lưu nhận ~2~ → ~[4, 6, 7]~, thuế: ~16 + 36 + 49 = 101~.

4. Sự kiện ~ (2, 2) ~: xí nghiệp 2 có ~6~ tách thành ~3~ và ~3~ → ~[4, 3, 3, 7]~, thuế: ~16 + 9 + 9 + 49 = 83~.

5. Sự kiện ~ (1, 3) ~: xí nghiệp 3 có ~3~ phá sản, chia ~3~ thành ~1~ và ~2~, thượng lưu nhận ~1~ → ~[4, 4, 9]~, thuế: ~16 + 16 + 81 = 113~.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le n \le 10^5~
• ~0 \le p \le 4~
• ~1 \le a_i \le 10^4~ với ~i = 1..n~
• ~1 \le k \le 10^5~

• Dữ liệu đảm bảo:

  • xí nghiệp bị chia (trong sự kiện loại ~2~) có đoạn sông độ dài ~> 1~,
  • đoạn sông của xí nghiệp phá sản (trong sự kiện loại ~1~) cũng có độ dài ~> 1~,
  • nếu chỉ còn một xí nghiệp thì xí nghiệp đó không phá sản,
  • giá trị ~c~ luôn hợp lệ theo số xí nghiệp hiện có tại thời điểm xảy ra sự kiện.

Chấm điểm

• Tham số ~p~ chỉ dùng để phân loại nhóm test trong hệ thống chấm; không ảnh hưởng đến định dạng vào/ra và yêu cầu bài toán.