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.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class segTree {
    static long INF= (long) 1e16;
    int n,a[];
    long []sum,lazy;
    segTree(int []a)
    {
        n=a.length;
        this.a=a;
        sum=new long [4*n];
        lazy= new long[4*n];
        Arrays.fill(sum,INF);
        build(1,0,n-1);
    }
    void build(int node,int tl,int tr) {
        if (tl == tr) { // leaf{
            sum[node] = a[tl];
        } else {
            int mid = tl + tr >> 1, left = node * 2, right = left + 1;
            build(left, tl, mid);
            build(right, mid + 1, tr);
            merge(node);
        }
    }
    long query(int l,int r){
        return query(1,0,n-1,l,r);
    }
    long query(int node,int tl,int tr ,int l,int r){
        if(r<tl || tr<l)
            return INF;
        if(tl>=l && tr<=r)
            return sum[node];
        propagate(node);
        int mid = tl + tr >> 1, left = node * 2, right = left + 1;
        return Math.min(query(left,tl,mid,l,r),query(right,mid+1,tr,l,r));
    }
    void merge(int node){
        sum[node]=Math.min(sum[node<<1],sum[node<<1|1]);
    }
    void updatePoint(int idx,int v){
        updatePoint(1,0,n-1,idx,v);
    }
    void updatePoint(int node,int tl,int tr,int idx,int v){
        if(tl==tr)
            sum[node]+=v;
        else{
            int mid = tl + tr >> 1, left = node * 2, right = left + 1;
            if(idx<=mid)
                updatePoint(left,tl,mid,idx,v);
            else
                updatePoint(right,mid+1,tr,idx,v);
            merge(node);
        }
    }
    void rangeupdate(int i ,int j,int val){
        rangeupdate(1,0,n-1,i,j,val);
    }
    void rangeupdate(int node,int tl,int tr,int l,int r,int val){
        if (r<tl || tr<l){
            return;
        }
        if (tl>=l&&tr<=r){
            sum[node]+=val;
            lazy[node]+=val;
        }
        else {
            int mid = tl + tr >> 1, left = node * 2, right = left + 1;
            propagate(node);
            rangeupdate(left,tl,mid,l,r,val);
            rangeupdate(right,mid+1,tr,l,r,val);
            merge(node);
        }


    }
    void propagate(int node)
    {
        lazy[node*2] += lazy[node];
        lazy[node*2+1] += lazy[node];
        sum[node*2] += lazy[node];
        sum[node*2+1] += lazy[node];
        lazy[node] = 0;
    }

    public static void main(String[]args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        int[]a= new int[n];
        for (int i =0;i<n;i++){
            a[i]=sc.nextInt();
        }
        HashMap<Integer,Integer>hm = new HashMap<>();
        segTree sg = new segTree(a);
        int q = sc.nextInt();
      //  pw.println(Arrays.toString(sg.sum));
        while (q-->0){
            StringTokenizer st = new StringTokenizer(sc.nextLine());
            if (st.countTokens()==2){
                long ans=INF;
                int l = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                if (l>r){
                    ans= Math.min(sg.query(0,r),sg.query(l,n-1));
                }
                else ans=sg.query(l,r);
                pw.println(ans);
            }
            else {
                int l = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                if (l>r){
                    sg.rangeupdate(0,r,v);
                    sg.rangeupdate(l,n-1,v);
                }
                else sg.rangeupdate(l,r,v);
            }
        }
        //pw.println(Arrays.toString(sg.sum));
        pw.flush();
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();
        }

    }

}

