Bạn được cho một dãy số \(a_1, a_2, \dots, a_n\) và \(m\) thao tác cần thực hiện thuộc 2 loại sau:

• Loại 1: 0 x y - cập nhật giá trị phần tử vị trí \(x\) thành \(y\).
• Loại 2: 1 l r - in ra tổng lớn nhất của các dãy con liên tiếp thuộc đoạn từ \(l\) tới \(r\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) là số phần tử của mảng \(a\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\).
• Dòng thứ ba chứa số nguyên \(m\) là số lượng truy vấn.
• \(m\) dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại trên.

Output

• Với mỗi truy vấn loại 2, in ra câu trả lời tương ứng trên một dòng.

Constraints

• \(1 \le n \le 5 \cdot 10^4\)
• \(1 \le m \le 5 \cdot 10^4\)
• \(|a_i|, |y| \le 10^4\)
• \(1 \le x \le n\)
• \(1 \le l \le r \le n\)

Example

5
1 2 -3 4 5
4
1 1 3
0 1 -100
1 1 3
1 1 5

3
2
9