Cấu trúc dữ liệu dạng Cây (Segment Tree) - Buổi 4

Cho dãy số a[1],a[2],...,a[n] (\(|a[i]| \leq 15000 ,n \leq 50000\)).

Hàm q(x,y)=maxtổng(\(a[i]+a[i+1]+...+a[j]\)), \(x \leq i \leq j \leq y\).

Cho \(m\) câu hỏi dạng \(x,y\) (\(1 \leq x \leq y \leq n\)). (\(m \leq 50000\)).

Hãy tính các \(q(x,y)\).

Input

• Dòng đầu là n
• Dòng thứ 2 là dãy \(A\)
• Dòng thứ 3 là m.
• \(m\) dòng tiếp theo mỗi dòng là \(1\) cặp số \(x,y\).

Output

• Lần lượt ghi ra các \(q(x,y)\) tương ứng. Mỗi kết quả ghi trên 1 dòng.

Example

3
-1 2 3
1
1 2

2

Quãng đường đi du lịch rất vui vẻ, nhưng đã gặp một vài biến cố...

Trên đường đi chơi quanh đất nước, cô "bạn gái" của shiba bỗng hướng ánh mắt vào một tiệm gấu nhồi bông. Để có thể lấy được gấu nhồi bông cho cô ấy, shiba quyết định sẽ chơi ném phi tiêu để nhận phần thưởng. Bằng kĩ năng "aim" "bách phát bách trượt" của mình, tất nhiên là cậu ấy không trúng phát nào rồi. Tuy nhiên, cô chủ tiệm gấu nhồi bông lại là một người đam mê tin học. Nhận ra dáng vẻ của một "lập trình viên" - ~lưng gù, trán có nếp nhăn, mặt già~ đẹp trai phong độ ngời ngợi tới từ shiba, cô chủ quyết định nhờ cậu ấy giải một bài toán, và hứa sẽ tặng tất cả gấu nhồi bông nếu cậu ấy giải được bài toán này. Bài toán đó như sau:

Cho một mảng \(a\) có \(n\) phần tử \(a_1,a_2,...,a_n\). Có hai loại truy vấn như sau:

• 1 p x: Gán giá trị cho phần tử \(a_1\) bằng \(x\).
• 2: Dựng \(n\) dãy:
  • Với \(i = 1\): \(b_{i,k} = a_k\), \(S = S + b_{i,k}\).
  • Với \(i > 1\): \(b_{i,k} = b_{i-1,k}\) \(\text AND\) \(b_{i-1,k+1}\), \(S = S + b_{i,k}\).

Do đang mải đi chơi, shiba quyết định gửi gắm bài toán này tới các bạn. Để shiba có thể quay lại với "người yêu cũ", sao các bạn không góp ~một chân~ một tay cho cậu ấy nhỉ?

Yêu cầu: Với mỗi thao tác loại \(2\), in ra kết quả của số \(S\).

Biểu thức \(x\) \(AND\) \(y\) biểu diễn phép toán tử AND của hai số \(x\) và \(y\).

Input

• Dòng thứ nhất chứa một số nguyên \(\phi\) - số thứ tự của subtask chứa test đó.
• Dòng thứ hai chứa một số nguyên dương \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ ba chứa \(n\) số nguyên \(a_1, a_2,..., a_n\) (\(0 \le a_i \le 10^5\)).
• Dòng thứ tư chứa một số nguyên \(q\) (\(q \le 10^5\)) - số lượng truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai dạng như trên, truy vấn dạng 1 p x có \(1 \le p \le n, 0 \le x \le 10^5\).

Output

• Với mỗi truy vấn loại \(2\), in ra kết quả bài toán trên một dòng.

Scoring

Gọi \(query\) là số lượng truy vấn loại \(2\).

• Subtask \(1\) (\(10\%\) số điểm): \(q = 1\), \(query = 1\), \(a_1 = a_2 = ... = a_n = 0\),
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 100, q \le 100\).
• Subtask \(3\) (\(15\%\) số điểm): \(q = 1\), \(query = 1\), \(a_1 = a_2 = ... = a_n\).
• Subtask \(4\) (\(20\%\) số điểm): \(query <= 10\).
• Subtask \(5\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

2
3
1 1 1
6
2
1 2 2
2
1 3 2
1 1 2
2

6
4
12