You are given circular array a0, a1, ..., an - 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: a0, a1, ..., an - 1 ( - 106 ≤ ai ≤ 106), ai 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; - 106 ≤ v ≤ 106) — 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).

Examples

Input

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


Output

1
0
0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
    static int[] a, tree;
    static int[] f;
    static int n;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(r.readLine());
        a = new int[n];
        tree = new int[4*n];
        f = new int[4*n];
        
        String[] line = r.readLine().split("[ ]+");
        for(int i = 0; i < n; i++)
            a[i] = Integer.parseInt(line[i]);
        
        init(1, 0, n-1);
        
        int m = Integer.parseInt(r.readLine());
        for(int k = 0; k < m; k++){
            line = r.readLine().split("[ ]+");
            if(line.length == 3){
                int lf = Integer.parseInt(line[0]);
                int rf = Integer.parseInt(line[1]);
                int inc = Integer.parseInt(line[2]);
                
                if(lf <= rf)update(1, 0, n-1, lf, rf, inc);
                else{
                    update(1, 0, n-1, 0, rf, inc);
                    update(1, 0, n-1, lf, n-1, inc);
                }
            }else{
                int lf = Integer.parseInt(line[0]);
                int rf = Integer.parseInt(line[1]);
                
                int min = Integer.MAX_VALUE;
                if(lf <= rf)min = query(1, 0, n-1, lf, rf);
                else{
                    min = Math.min(min, query(1, 0, n-1, 0, rf));
                    min = Math.min(min, query(1, 0, n-1, lf, n-1));
                }
                
                System.out.println(min);
            }
        }
    }

    private static void refresh(int i) {
        tree[i] += f[i];
        if(2*i < 4*n){
            f[2*i] += f[i];
        }
        if(2*i+1 < 4*n){
            f[2*i + 1] += f[i]; 
        }
        f[i] = 0;
    }
    private static void update(int i, int s, int e, int qs, int qe, int inc) {
        refresh(i);
            
        if(qe < s || e < qs)return;
        if(qs <= s && e <= qe){
            f[i] += inc;
            return;
        }
        
        int md = (s + e) / 2;
        update(2*i, s, md, qs, qe, inc);
        update(2*i+1, md + 1, e, qs, qe, inc);
        
        tree[i] = Math.min(tree[2 * i] + f[2 * i], tree[2 * i + 1] + f[2 * i + 1]);
    }
    static int inf = 1 << 30;
    private static int query(int i, int s, int e, int qs, int qe) {
        refresh(i);
        
        if(qe < s || e < qs)return inf;
        if(qs <= s && e <= qe)return tree[i];
        
        int w1 = query(2*i, s, (s+e)/2, qs, qe);
        int w2 = query(2*i+1, (s+e)/2+1, e, qs, qe);
        
        return Math.min(w1, w2);
    }
    private static void init(int i, int s, int e) {
        if(s == e){
            tree[i] = a[s];
        }else{
            init(2*i, s, (s+e)/2);
            init(2*i+1, (s+e)/2+1, e);
            
            tree[i] = Math.min(tree[2*i], tree[2*i+1]);
        }
    }
}
