Đảo kho báu

Trên hòn đảo hình vòng tròn, có \(n\) chiếc rương báu vật xếp thành một vòng. Mỗi chiếc rương được đánh số từ \(0\) đến \(n - 1\) và chứa một số lượng vàng ban đầu là \(a_0, a_1, \ldots, a_{n-1}\).

Cướp biển Lập trình viên rất quan tâm đến giá trị của kho báu và thường xuyên thực hiện các hành động sau:

• inc(lf, rg, v) --- Thêm \(v\) thỏi vàng vào mỗi chiếc rương từ vị trí \(lf\) đến \(rg\) (tính cả hai đầu).
• rmq(lf, rg) --- Truy xuất thông tin: rương nào có ít vàng nhất trong đoạn từ \(lf\) đến \(rg\)?

Vì các rương được xếp thành vòng tròn, nên đoạn từ \(lf\) đến \(rg\) có thể được hiểu như sau:

• Nếu \(lf \le rg\): đoạn gồm các chỉ số từ \(lf\) đến \(rg\).
• Nếu \(lf > rg\): đoạn gồm các chỉ số từ \(lf\) đến \(n - 1\), rồi tiếp tục từ \(0\) đến \(rg\).

Hãy giúp Lập trình viên thực hiện tuần tự các thao tác, và ghi lại kết quả mỗi lần anh ta truy vấn rmq!

Input

• Dòng đầu chứa số nguyên \(n\) \((1 \leq n \leq 2 \cdot 10^5)\) --- số lượng rương.
• Dòng thứ hai chứa \(n\) số nguyên \(a_0, a_1, \ldots, a_{n-1}\) \((-10^6 \le a_i \le 10^6)\) --- số lượng vàng ban đầu ở mỗi rương.
• Dòng thứ ba chứa số nguyên \(m\) \((0 \le m \le 2 \cdot 10^5)\) --- số truy vấn.

• \(m\) dòng tiếp theo, mỗi dòng chứa một truy vấn, có thể ở một trong hai dạng:

• lf rg --- Truy vấn loại rmq.

• lf rg v --- Truy vấn loại inc.

Output

Với mỗi truy vấn loại rmq, in ra một dòng chứa số lượng vàng ít nhất trong đoạn được hỏi.

Example

4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1

1
0
0