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 {
//    private final CustomReader in = new CustomReader("input.txt");
//    private final PrintWriter out = setupOutput("output.txt");
    private final CustomReader in = new CustomReader();
    private final PrintWriter out = setupOutput(null);

    void solve() {
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = in.nextInt();
        }
        int m = in.nextInt();
        SegmentTreeLazy st = new SegmentTreeLazy(arr);
        for (int m0 = 0; m0 < m; m0++) {
            String[] q = in.nextLine().split(" ");
            int l = Integer.parseInt(q[0]);
            int r = Integer.parseInt(q[1]);
            if (q.length == 3) {
                if (r < l) {
                    st.update(l, n-1, Integer.parseInt(q[2]));
                    st.update(0, r, Integer.parseInt(q[2]));
                }
                else {
                    st.update(l, r, Integer.parseInt(q[2]));
                }
            }
            else {
                if (r < l) {
                    out.println(Math.min(
                            st.query(l, n-1), st.query(0, r)));
                }
                else {
                    out.println(st.query(l, r));
                }
            }
        }
    }

    public class SegmentTreeLazy {

        /* *********************************** */
        /* CHANGE HERE FOR OTHER FUNCTIONALITY */

        static final int DEFAULT_LAZY = 0;

        int getLeafValue(int arrayValue) {
            return arrayValue;
        }

        int combineValues(int value1, int value2) {
            return Math.min(value1, value2);
        }

        int updateLazy(int oldLazy, int queryValue, int left, int right) {
            return oldLazy + queryValue;
        }

        int applyLazy(int treeValue, int lazyValue, int left, int right) {
            return treeValue + lazyValue;
        }

        /* CHANGE HERE FOR OTHER FUNCTIONALITY */
        /* *********************************** */

        private final int n;
        private int[] tree;
        private int[] lazy;

        public SegmentTreeLazy(int[] arr) {
            n = arr.length;
            int h = 32 - Integer.numberOfLeadingZeros(n-1) + 1;
            tree = new int[1<<h];
            lazy = new int[1<<h];
            if (DEFAULT_LAZY != 0) Arrays.fill(lazy, DEFAULT_LAZY);
            build(1, 0, arr.length-1, arr);
        }

        private void build(int i, int l, int r, int[] arr) {
            if (l == r) tree[i] = getLeafValue(arr[l]);
            else {
                int m = (l+r+1) / 2;
                build(2*i, l, m-1, arr);
                build(2*i+1, m, r, arr);
                tree[i] = combineValues(tree[2*i], tree[2*i+1]);
            }
        }

        private int ql, qr, val;

        public void update(int ql, int qr, int val) {
            this.ql = ql;
            this.qr = qr;
            this.val = val;
            updateHelper(1, 0, n-1);
        }

        private void updateHelper(int i, int l, int r) {
            if (qr < l || ql > r) return;
            if (qr >= r && ql <= l) {
                lazy[i] = updateLazy(lazy[i], val, l, r);
                tree[i] = applyLazy(tree[ i], val, l, r);
            } else {
                propagateLazy(i, l, r);
                int m = (l+r+1) / 2;
                updateHelper(2*i, l, m-1);
                updateHelper(2*i+1, m, r);
                tree[i] = combineValues(tree[2*i], tree[2*i + 1]);
            }
        }

        public int query(int ql, int qr) {
            this.ql = ql;
            this.qr = qr;
            return queryHelper(1, 0, n-1);
        }

        private int queryHelper(int i, int l, int r) {
            if (qr < l || ql > r) return Integer.MIN_VALUE;
            if (qr >= r && ql <= l) return tree[i];
            propagateLazy(i, l, r);
            int m = (l+r+1) / 2;

            int ansLeft = queryHelper(2*i, l, m-1);
            int ansRight = queryHelper(2*i + 1, m, r);
            if (ansLeft == Integer.MIN_VALUE) return ansRight;
            if (ansRight == Integer.MIN_VALUE) return ansLeft;
            return combineValues(ansLeft, ansRight);
        }

        private void propagateLazy(int i, int l, int r) {
            if (lazy[i] != DEFAULT_LAZY) {
                int m = (l+r+1) / 2;
                lazy[2*i] = updateLazy(lazy[2*i], lazy[i], l, m-1);
                tree[2*i] = applyLazy(tree[2*i], lazy[i], l, m-1);
                lazy[2*i+1] = updateLazy(lazy[2*i+1], lazy[i], m, r);
                tree[2*i+1] = applyLazy(tree[2*i+1], lazy[i], m, r);
                lazy[i] = DEFAULT_LAZY;
            }
        }
    }


    public static void main(String[] args) { Main s = new Main(); s.solve(); s.out.close(); }
    private static class CustomReader {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar;
        private int numChars;

        CustomReader() {
            stream = System.in;
        }

        CustomReader(String fileName) {
            InputStream temp = null;
            try { temp = new FileInputStream(fileName); }
            catch (FileNotFoundException e) { e.printStackTrace(); }
            stream = temp;
        }

        String nextLine() {
            int c = read();
            StringBuilder res = new StringBuilder();
            while (!isEndOfLine(c)) {
                res.appendCodePoint(c);
                c = read();
            }
            if (c == '\r') read();
            return res.toString();
        }

        String nextString() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            while (!isSpaceChar(c)) {
                res.appendCodePoint(c);
                c = read();
            }
            if (c == '\r') read();
            return res.toString();
        }

        long nextLong() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            while (!isSpaceChar(c)) {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '\r') read();
            return res * sgn;
        }

        int nextInt() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            while (!isSpaceChar(c)) {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '\r') read();
            return res * sgn;
        }

        int[] nextArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) arr[i] = nextInt();
            return arr;
        }

        double nextDouble() {
            return Double.parseDouble(nextString());
        }

        boolean hasNext() {
            if (numChars == -1) return false;
            return curChar < numChars || curChar == buf.length || numChars == 0; // Probably
        }

        int read() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try { numChars = stream.read(buf); }
                catch (IOException e) { throw new InputMismatchException(); }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }

        private static boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; }

        private static boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; }
    }
    private static PrintWriter setupOutput(String fileName) {
        if (fileName == null) return new PrintWriter(System.out);
        PrintWriter temp = null;
        try { temp = new PrintWriter(fileName); }
        catch (FileNotFoundException e) { e.printStackTrace(); }
        return temp;
    }
}
