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 javax.print.DocFlavor;
import java.awt.*;
import java.io.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    static long[]diff,SegTree;


    static void buildSegTree() {
        int n = arr.length;
        int n2=(int)(Math.log(n)/Math.log(2));
        if(n!=(1<<n2))
            n=1<<(n2+1);
        SegTree = new long[n << 1];
        diff = new long[n << 1];
        build(0, arr.length - 1, 1);
    }

    static int build( int beg, int end, int indxInTree) {
        if (beg == end) {
            SegTree[indxInTree] = arr[beg];
            return arr[beg];
        }
        int mid = (beg + end)>>1;
        int lc = build( beg, mid,indxInTree<<1);
        int rc = build( mid + 1, end, (indxInTree)<<1|1);
        int parent = Math.min(lc, rc);
        SegTree[indxInTree]=parent;
        return parent;
    }

    static void update(int lf, int ri, int val) {

        update2(lf, ri, val, 0, arr.length - 1, 1);
    }

    static long update2(int lf, int ri, int val, int beg, int end, int indxInTree) {
        if (beg >= lf && end <= ri) {
            diff[indxInTree] += val;
            return SegTree[indxInTree]+diff[indxInTree];
        }
        int mid = (beg + end) / 2;
        //System.out.println(lf+" "+ri+" "+beg+" "+end+" "+mid);
        if (ri <= mid) {
            long l=update2(lf, ri, val, beg, mid, indxInTree << 1);
            SegTree[indxInTree]=Math.min(l,SegTree[(indxInTree<<1)|1]+diff[(indxInTree<<1)|1]);
            return SegTree[indxInTree]+diff[indxInTree];
        }
        if (lf > mid) {
            long r=update2(lf, ri, val, mid + 1, end, (indxInTree << 1) | 1);
            SegTree[indxInTree]=Math.min(r,SegTree[(indxInTree<<1)]+diff[(indxInTree<<1)]);
            return SegTree[indxInTree]+diff[indxInTree] ;
        }
        long l=update2(lf, mid, val, beg, mid, indxInTree << 1);
        long r=update2(mid + 1, ri, val, mid + 1, end, (indxInTree << 1) | 1);
        SegTree[indxInTree]=Math.min(r,l);
        return SegTree[indxInTree]+diff[indxInTree] ;
    }

    static long query(int beg, int end) {
        return query2(beg, end, 0, arr.length - 1, 1);
    }

    static long query2(int begq, int endq, int begI, int endI, int indxInTree) {
        SegTree[indxInTree] += diff[indxInTree];
        if (begI!=endI) {
            diff[indxInTree << 1] += diff[indxInTree];
            diff[(indxInTree << 1) | 1] += diff[indxInTree];
        }
        diff[indxInTree] = 0;
        if (begI >= begq && endI <= endq)
            return SegTree[indxInTree];
        int mid = (begI + endI) / 2;
        if (endq <= mid)
            return query2(begq, endq, begI, mid, indxInTree << 1);
        if (begq > mid)
            return query2(begq, endq, mid + 1, endI, (indxInTree << 1) | 1);
        long minl = query2(begq, mid, begI, mid, indxInTree << 1);
        long minr = query2(mid + 1, endq, mid + 1, endI, (indxInTree << 1) | 1);
        return Math.min(minl, minr);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PrintWriter out = new PrintWriter(System.out);

        int n = Integer.parseInt(br.readLine());


        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int m = Integer.parseInt(br.readLine());
        buildSegTree();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int lf = Integer.parseInt(st.nextToken());
            int ri = Integer.parseInt(st.nextToken());
            int val;
            boolean b = st.hasMoreTokens();
            if (!b) {
                if (lf <= ri)
                    out.println(query(lf, ri));
                else
                    out.println(Math.min(query(lf, n - 1), query(0, ri)));
            } else {
                val = Integer.parseInt(st.nextToken());
                if (lf <= ri)
                    update(lf, ri, val);
                else {
                    update(lf,n-1,val);
                    update(0,ri,val);
                }


            }


        }

        out.flush();
    }
}
