RMQ trên mảng vòng tròn

Cho một mảng vòng tròn $a_0,a_1,\dots ,a_{n-1}$. Ta cần xử lý hai loại thao tác trên mảng này:

• inc(lf, rg, v) — tăng mỗi phần tử trên đoạn $[lf,rg]$ (bao gồm hai đầu mút) thêm $v$.
• rmq(lf, rg) — trả về giá trị nhỏ nhất trên đoạn $[lf,rg]$ (bao gồm hai đầu mút).

Vì mảng là vòng tròn nên các đoạn cũng được hiểu theo nghĩa vòng tròn: nếu $lf\le rg$ thì đoạn gồm các chỉ số $lf,lf+1,\dots ,rg$; còn nếu $lf>rg$ thì đoạn "vòng qua" cuối mảng, gồm các chỉ số $lf,lf+1,\dots ,n-1,0,1,\dots ,rg$.

Ví dụ với $n=5$, $lf=3$, $rg=1$ thì đoạn gồm các chỉ số $3,4,0,1$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_0,a_1,\dots ,a_{n-1}$ — trạng thái ban đầu của mảng.
• Dòng thứ ba chứa số nguyên $m$ — số thao tác.
• $m$ dòng tiếp theo, mỗi dòng mô tả một thao tác:
  • Nếu dòng chứa hai số nguyên $lf$, $rg$ thì đó là thao tác rmq(lf, rg).
  • Nếu dòng chứa ba số nguyên $lf$, $rg$, $v$ thì đó là thao tác inc(lf, rg, v).

Dữ liệu ra

Với mỗi thao tác rmq, in ra trên một dòng giá trị nhỏ nhất tương ứng.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $-{10}^6\le a_i\le {10}^6$
• $0\le m\le 2·{10}^5$
• $0\le lf,rg\le n-1$
• $-{10}^6\le v\le {10}^6$

Lưu ý rằng kết quả có thể vượt quá phạm vi số nguyên 32 bit.

Ví dụ