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.*;

public class Main {
    static PrintWriter pw;
    static Scanner sc;
    static char[][] arr;
    static long[][] dp;
    static long ceildiv(long x, long y){ return (x+y-1)/y;}
    public static void main(String[] args) throws Exception {
        sc = new Scanner(System.in);
        pw = new PrintWriter(System.out);
        int n=sc.nextInt();
        int len=1;
        while(len<n)
            len<<=1;
        long[] arr=new long[len];
        Arrays.fill(arr, (long)1e18);
        for(int i=0; i<n; i++)
            arr[i]=sc.nextInt();
        SegmentTree stree= new SegmentTree(arr);
        int m=sc.nextInt();
        while(m-->0){
            st=new StringTokenizer(sc.nextLine());
            int x=Int(), y=Int();
            if(st.hasMoreTokens())
                stree.update(x, y, Int());
            else
                pw.println(stree.query(x, y));
        }
        pw.close();
    }
    static int Int(){
        return Integer.parseInt(st.nextToken());
    }
    static StringTokenizer st;
    static void printArr(int[] arr){
        for(int i=0; i<arr.length-1; i++)
            pw.print(arr[i]+" ");
        pw.println(arr[arr.length-1]);
    }
    static void printArr(long[] arr){
        for(int i=0; i<arr.length-1; i++)
            pw.print(arr[i]+" ");
        pw.println(arr[arr.length-1]);
    }
    static void printArr(Integer[] arr){
        for(int i=0; i<arr.length; i++)
            pw.print(arr[i]+" ");
        pw.println();
    }
    static void printArr(char[] arr){
        for(int i=0; i<arr.length; i++)
            pw.print(arr[i]);
        pw.println();
    }
    static void printArr(ArrayList list){
        for(int i=0; i<list.size(); i++)
            pw.print(list.get(i)+" ");
        pw.println();
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;
        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        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 {
            return Double.parseDouble(next());
        }

        public int[] nextArr(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++)
                arr[i] = nextInt();
            return arr;
        }
        public Integer[] nextsort(int n) throws IOException{
            Integer[] arr=new Integer[n];
            for(int i=0; i<n; i++)
                arr[i]=nextInt();
            return arr;
        }
        public Pair nextPair() throws IOException{
            return new Pair(nextInt(), nextInt());
        }
        public Pair[] nextPairArr(int n) throws IOException{
            Pair[] arr=new Pair[n];
            for(int i=0; i<n; i++)
                arr[i]=new Pair(nextInt(), nextInt());
            return arr;
        }
        public boolean ready() throws IOException {
            return br.ready();
        }
    }
    static class Pair implements Comparable<Pair>{
        int x;
        int y;
        public Pair(int x, int y) {
            this.x=x;
            this.y=y;
        }
        public int hashCode() {
            return this.x*1000+this.y;
        }
        public int compareTo(Pair p){
            return this.x-p.x;
        }
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (this.getClass() != obj.getClass()) {
                return false;
            }
            Pair p = (Pair) obj;
            return this.x==p.x && this.y==p.y;
        }
        public boolean equal(Pair p){
            if(this.x==p.x)
                return this.y==p.y;
            if(this.x==p.y)
                return this.y==p.x;
            else
                return false;
        }
        public Pair clone(){
            return new Pair(x, y);
        }
        public String toString(){
            return this.x+" "+this.y;
        }
    }
    static class Triple{
        int x, y, z;
        public Triple(int x, int y, int z){
            this.x=x;
            this.y=y;
            this.z=z;
        }
        public int hashCode(){
            return this.x*100+this.y;
        }
        public boolean equals(Object obj){
            if (obj == null) {
                return false;
            }
            if (this.getClass() != obj.getClass()) {
                return false;
            }
            Triple t = (Triple) obj;
            return this.x==t.x && this.y==t.y && this.z==t.z;
        }
    }
    static class SegmentTree{
        long[] arr, tree, lazy;
        public SegmentTree(long[] arr){
            this.arr=arr.clone();
            int n=arr.length;
            tree=new long[(n<<1)-1];
            lazy=new long[(n<<1)-1];
            build(0, 0, n-1);
        }
        public void build(int node, int l, int r){
            if(l==r){
                tree[node]=arr[l];
            }else{
                int mid=(l+r)>>1;
                int left=2*node+1, right=2*node+2;
                build(left, l, mid);
                build(right, mid+1, r);
                tree[node]=Math.min(tree[left], tree[right]);
            }
        }
        public long query(int l, int r){
            if(l>r)
                return Math.min(query(l, arr.length-1), query(0, r));
            return query(0, 0, arr.length-1, l, r);
        }
        public long query(int node, int l, int r, int i, int j){
            if(i>r || j<l)
                return Long.MAX_VALUE;
            if(i<=l && j>=r)
                return tree[node];
            int mid=(l+r)/2;
            int left=(node<<1)+1, right=(node<<1)+2;
            propagate(node, left, right);
            return Math.min(query(left, l, mid, i, j), query(right, mid+1, r, i, j));
        }
//        public void update(int idx, int x){
//            int i=idx+arr.length-1;
//            tree[i]=x;
//            i=(i-1)>>1;
//            while(i>=0){
//                if(i==0){
//                    int left=2*i+1, right=2*i+2;
//                    tree[i]=or[i]? tree[left]|tree[right]: tree[left]^tree[right];
//                    i=(i-1)>>1;
//                    break;
//                }else{
//                    int left=2*i+1, right=2*i+2;
//                    tree[i]=or[i]? tree[left]|tree[right]: tree[left]^tree[right];
//                    i=(i-1)>>1;
//                }
//            }
//        }
        public void propagate(int node, int left, int right){
            lazy[left]+=lazy[node];
            lazy[right]+=lazy[node];
            tree[left]+=lazy[node];
            tree[right]+=lazy[node];
            lazy[node]=0;
        }
        public void update(int l, int r, int x){
            if(l>r){
                update(l, arr.length-1, x);
                update(0, r, x);
            }else{
                update(0, 0, arr.length-1, l, r, x);
            }
        }
        public void update(int node, int l, int r, int i, int j, int x){
            if(i>r || j<l)
                return;
            if(i<=l && j>=r){
                lazy[node]+=x;
                tree[node]+=x;
            }else{
                int mid=(l+r)>>1;
                int left=(node<<1)+1, right=(node<<1)+2;
                propagate(node, left, right);
                update(left, l, mid, i, j, x); update(right, mid+1, r, i, j, x);
                tree[node]=Math.min(tree[left], tree[right]);
            }
        }
    }
}