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.util.*;
import java.io.*;

public class CircularRMQ {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int N = scanner.nextInt();
        SegmentTree segmentTree = new SegmentTree(N);
        segmentTree.init(0, N-1, 1);
        for(int i = 0; i < N; i++) {
            segmentTree.increment(i,i,scanner.nextInt());
        }
        int M = scanner.nextInt();
        while(M-->0) {
            String[] line = scanner.readNextLine().split(" ");
            int l = Integer.parseInt(line[0]);
            int r = Integer.parseInt(line[1]);
            if (line.length > 2) {
                int v = Integer.parseInt(line[2]);
                if (l > r) {
                    segmentTree.increment(0,r,v);
                    segmentTree.increment(l,N-1, v);
                }
                else {
                    segmentTree.increment(l,r,v);
                }
            }
            else {
                long ans = Long.MAX_VALUE;
                if (l > r) {
                    ans = Math.min(segmentTree.minimum(0,r), ans);
                    ans = Math.min(segmentTree.minimum(l,N-1), ans);
                }
                else {
                    ans = Math.min(segmentTree.minimum(l,r), ans);
                }
                out.println(ans);
            }
        }
        out.flush();
    }
    public static class SegmentTree {
        int size;
        int[] hi, lo;
        long[] min, delta;
        public SegmentTree(int ss) {
            size = ss;
            lo = new int[4*size+1];
            hi = new int[4*size+1];
            min = new long[4*size+1];
            delta = new long[4*size+1];
        }
        public void init(int l, int r, int cur) {
            lo[cur] = l;
            hi[cur] = r;
            //segment of size one (bottom)
            if (l==r) return;
            //otherwise recursively build
            int mid = (l + r) /2;
            //left child
            init(l, mid, cur*2);
            //right child
            init(mid+1, r,cur*2+1);
        }
        //functions to start off the recursion
        public void increment(int l, int r, long amt) {
            //start off at root (1)
            increment(1, l, r, amt);
        }
        public long minimum (int l, int r) {
            return minimum(1, l, r);
        }
        //actual increment function (recursive)
        public void increment(int cur, int l, int r, long amt) {
            //no coverage
            if (r < lo[cur] || l > hi[cur]) return;
            //complete coverage
            if (r >= hi[cur] && l <= lo[cur]) {
                delta[cur] += amt;
                return;
            }
            //partial coverage (need to recurse and propogate)
            //first propogate
            prop(cur);
            //left child
            increment(cur*2, l, r, amt);
            //right child
            increment(cur*2+1, l, r, amt);
            //update min values based on updates
            update(cur);
        }
        public long minimum(int cur, int l, int r) {
            //no coverage case
            if (r < lo[cur] || l > hi[cur]) return Long.MAX_VALUE;
            //complete coverage
            if (r >= hi[cur] && l <= lo[cur]) return min[cur] + delta[cur];
            //partial coverage cases
            //need to propogate before recursion
            prop(cur);
            //left child
            long left = minimum(cur*2, l, r);
            //right child
            long right = minimum(cur*2+1, l, r);
            //recompute mins
            update(cur);
            return Math.min(left, right);
        }
        public void prop(int cur) {
            delta[cur*2] += delta[cur];
            delta[cur*2+1] += delta[cur];
            delta[cur] = 0;
        }
        public void update(int cur) {
            min[cur] = Math.min(min[cur*2]+delta[cur*2], min[cur*2+1] + delta[cur*2+1]);
        }
    }
    
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}
