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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CCircularRMQ solver = new CCircularRMQ();
        solver.solve(1, in, out);
        out.close();
    }

    static class CCircularRMQ {
        public void solve(int testNumber, FastReader s, PrintWriter out) {
            int n = s.nextInt();
            int[] arr = s.nextIntArray(n);
            CCircularRMQ.SegmentTree st = new CCircularRMQ.SegmentTree(n);
            for (int i = 0; i < n; i++) {
                st.increment(i, i, arr[i]);
            }

            int q = s.nextInt();
            while (q-- > 0) {
                String str = s.readLine();
//            System.out.println(str);
                String[] strings = str.split(" ");
//            System.out.println(arrays.printArr(strings));
                if (strings.length == 3) {
                    int left = (int) Long.parseLong(strings[0]);
                    int right = (int) Long.parseLong(strings[1]);
                    long v = Long.parseLong(strings[2]);
                    if (right >= left) {
                        st.increment(left, right, v);
                    } else {
                        st.increment(left, n - 1, v);
                        st.increment(0, right, v);
                    }
                } else {
                    int left = Integer.parseInt(strings[0]);
                    int right = Integer.parseInt(strings[1]);
                    long a;
                    if (right >= left) {
                        a = (st.minimum(left, right));
                    } else {
                        a = st.minimum(left, n - 1);
                        a = Math.min(a, st.minimum(0, right));
                    }
                    if (a == Integer.MAX_VALUE) {
                        out.println(0);
                    } else {
                        out.println(a);
                    }

                }
            }
        }

        private static class SegmentTree {
            long[] lo;
            long[] hi;
            long[] min;
            long[] delta;
            int n;

            public SegmentTree(int n) {
                this.n = n;
                this.hi = new long[4 * n + 1];
                this.lo = new long[4 * n + 1];
                this.min = new long[4 * n + 1];
                this.delta = new long[4 * n + 1];
                init(1, 0, n - 1);
            }

            void prop(int i) {
                delta[2 * i] += delta[i];
                delta[2 * i + 1] += delta[i];
                delta[i] = 0;
            }

            void update(int i) {
                min[i] = Math.min(min[2 * i + 1] + delta[2 * i + 1], min[2 * i] + delta[2 * i]);
            }

            void increment(int a, int b, long val) {
                increment(1, a, b, val);
            }

            private void increment(int i, int a, int b, long val) {
                if (a > hi[i] || b < lo[i]) {
                    return;
                }

                //Fully overlap case.
                if (a <= lo[i] && hi[i] <= b) {
                    delta[i] += val;
                    return;
                }

                //Partial overlap case.
                prop(i);

                increment(2 * i, a, b, val);
                increment(2 * i + 1, a, b, val);

                update(i);
            }

            private long minimum(int a, int b) {
                return minimum(1, a, b);
            }

            private long minimum(int i, int a, int b) {
                if (a > hi[i] || b < lo[i]) {
                    return Integer.MAX_VALUE;
                }

                if (a <= lo[i] && hi[i] <= b) {
                    return min[i] + delta[i];
                }

                prop(i);

                long minLeft = minimum(2 * i, a, b);
                long minRight = minimum(2 * i + 1, a, b);

                update(i);

                return Math.min(minLeft, minRight);

            }

            private void init(int i, int from, int to) {
                lo[i] = from;
                hi[i] = to;

                if (from == to) {
                    return;
                }

                int mid = (from + to) / 2;
                init(2 * i, from, mid);
                init(2 * i + 1, mid + 1, to);
            }

        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public 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++];
        }

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

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

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

        private String readLine0() {
            StringBuilder buf = new StringBuilder();
            int c = read();
            while (c != '\n' && c != -1) {
                if (c != '\r') {
                    buf.appendCodePoint(c);
                }
                c = read();
            }
            return buf.toString();
        }

        public String readLine() {
            String s = readLine0();
            while (s.trim().length() == 0) {
                s = readLine0();
            }
            return s;
        }

        public int[] nextIntArray(int n) {
            int[] array = new int[n];
            for (int i = 0; i < n; ++i) array[i] = nextInt();
            return array;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

