Cho mảng \(A = (a_1, a_2, \ldots, a_n)\) chứa các số nguyên. Người ta thực hiện \(m\) truy vấn thuộc một trong \(3\) dạng sau:

• 1 u v delta: Tăng \(a_u, a_{u + 1}, \ldots, a_v\) lên \(delta\) \((|delta| \le 10^4)\)
• 2 u v: Tính tổng \(\max(a_u, a_{u + 1}, \ldots, a_v)\).

Input

• Dòng đầu là số nguyên dương \(n\) \((n \le 10^5)\).
• Dòng tiếp theo là \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((|a_i| \le 10^4)\).
• Dòng thứ ba là số nguyên dương \(m\) \((m \le 10^5)\).
• \(m\) dòng tiếp theo, mỗi dòng là một truy vấn nhập vào theo dạng trên.

Output

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

Example

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

7
0