Cập nhật đoạn

Cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là xử lý \(q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• Loại 1: 1 x y val — Tăng giá trị của các phần tử từ chỉ số \(x\) đến \(y\) thêm \(val\) đơn vị (\(1 \le x \le y \le n\), \(1 \le val \le 10^9\)).
• Loại 2: 2 l r — In ra giá trị lớn nhất của các phần tử trong đoạn từ chỉ số \(l\) đến \(r\) (\(1 \le l \le r \le n\)).

Yêu cầu như bài trước, sử dụng chia căn để giải bài toán.

Input

• Dòng đầu chứa số nguyên \(n\) — số phần tử trong mảng (\(1 \le n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(|a_i| \le 10^9\)).
• Dòng thứ ba chứa số nguyên \(q\) — số truy vấn (\(1 \le q \le 10^5\)).
• \(q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng ở trên.

Output

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

Sample Input 1

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

Sample Output 1

4
6
7