You are given circular array $*a*_{0}, *a*_{1}, ..., *a*_{*n* - 1}$. There are two types of operations with it:

• $*inc*(*lf*, *rg*, *v*)$ — this operation increases each element on the segment $[*lf*, *rg*]$ (inclusively) by $*v*$;
• $*rmq*(*lf*, *rg*)$ — this operation returns minimal value on the segment $[*lf*, *rg*]$ (inclusively).

Assume segments to be circular, so if $*n* = 5$ and $*lf* = 3, *rg* = 1$, it means the index sequence: $3, 4, 0, 1$.

Write program to process given sequence of operations.

Input

The first line contains integer $*n*$ ($1 ≤ *n* ≤ 200000$). The next line contains initial state of the array: $*a*_{0}, *a*_{1}, ..., *a*_{*n* - 1}$ ($- 10^{6} ≤ *a*_{*i*} ≤ 10^{6}$), $*a*_{*i*}$ are integer. The third line contains integer $*m*$ ($0 ≤ *m* ≤ 200000$), $*m*$ — the number of operartons. Next $*m*$ lines contain one operation each. If line contains two integer $*lf*, *rg*$ ($0 ≤ *lf*, *rg* ≤ *n* - 1$) it means $*rmq*$ operation, it contains three integers $*lf*, *rg*, *v*$ ($0 ≤ *lf*, *rg* ≤ *n* - 1; - 10^{6} ≤ *v* ≤ 10^{6}$) — $*inc*$ operation.

Output

For each $*rmq*$ operation write result for it. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).