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.*;
import static java.lang.Math.*;

public class Main {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner();

        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i=0; i<n; i++) 
            arr[i] = sc.nextInt();

        RMQTree tree = new RMQTree(arr);

        int m = sc.nextInt();

        StringBuilder sb = new StringBuilder();

        for (int i=0; i<m; i++) {
            String[] op = sc.readNextLine().split("\\s+");

            int lf = Integer.parseInt(op[0]);
            int rg = Integer.parseInt(op[1]);
            if (op.length == 2) {
                if (lf > rg) {
                    sb.append(min(tree.query(0, rg), tree.query(lf, n)) + "\n");
                } else {
                    sb.append(tree.query(lf, rg) + "\n");
                }
            } else {
                int v = Integer.parseInt(op[2]);
                if (lf > rg) {
                    tree.update(0, rg, v);
                    tree.update(lf, n, v);
                } else {
                    tree.update(lf, rg, v);
                }
            }
        }

        System.out.println(sb.toString());

    }

    static class RMQTree {
        int n;
        int[] arr, st, lazy;

        RMQTree(int[] arr) {
            this.n = arr.length;
            this.arr = arr;
            this.st = new int[3*n];
            this.lazy = new int[3*n];
            build(1, 0, n-1);
        }

        int query(int i, int j) {
            return query(1, 0, n-1, i, j);
        }

        void update(int i, int j, int v) {
            lazyupdate(1, 0, n-1, i, j, v);
        }

        private void build(int p, int l, int r) {
            if (l==r) {
                st[p] = arr[l];
            } else {
                build(p<<1, l, (l+r)/2);
                build((p<<1)+1, ((l+r)/2)+1, r);
                st[p] = min(st[p<<1], st[(p<<1)+1]);
            }
        }

        private int query(int p, int l, int r, int i, int j) {
            if (i>r || j<l) 
                return Integer.MAX_VALUE;

            if (lazy[p] != 0) {
                st[p] += lazy[p];
                if (l!=r) {
                    lazy[p<<1] += lazy[p];
                    lazy[(p<<1)+1] += lazy[p];
                }
                lazy[p] = 0;
            }

            if (i<=l && r<=j) 
                return st[p];

            return min(query(p<<1, l, (l+r)/2, i, j),
                    query((p<<1)+1, ((l+r)/2)+1, r, i, j));
        }

        private void lazyupdate(int p, int l, int r, int i, int j, int v) {
            if (lazy[p] != 0) {
                st[p] += lazy[p];
                if (l!=r) {
                    lazy[p<<1] += lazy[p];
                    lazy[(p<<1)+1] += lazy[p];
                }
                lazy[p] = 0;
            }

            if (i>r || j<l) 
                return;

            if (i<=l && r<=j) {
                st[p] += v;
                if (l!=r) {
                    lazy[p<<1] += v;
                    lazy[(p<<1)+1] += v;
                }
                return;
            }

            lazyupdate(p<<1, l, (l+r)/2, i, j, v);
            lazyupdate((p<<1)+1, ((l+r)/2)+1, r, i, j, v);
            st[p] = min(st[p<<1], st[(p<<1)+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;
        }
    }

}