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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Alex
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
    static class TaskC {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            int[] input = IOUtils.readIntArray(in, n);
            ST st = new ST(input);
            int queries = in.readInt();
            for(int query = 0; query < queries; query++) {
                String[] line = in.readLine(true).split(" ");
                int[] args = new int[line.length];
                for(int i = 0; i < args.length; i++)
                    args[i] = Integer.parseInt(line[i]);
                if(line.length == 2) out.printLine(st.get(args[0], args[1]));
                else st.incr(args[0], args[1], args[2]);
            }
        }

        class ST {
            long INF = Long.MAX_VALUE / 30;
            Vertex parent;
            int[] input;

            public ST(int[] input) {
                this.input = input;
                parent = init(0, input.length - 1);
            }

            Vertex init(int l, int r) {
                if(l == r) return new Vertex(l, r, input[l]);
                Vertex left = init(l, (l + r) / 2);
                Vertex right = init((l + r) / 2 + 1, r);
                Vertex ret = new Vertex(l, r, Math.min(left.get(), right.get()));
                ret.left = left;
                ret.right = right;
                return ret;
            }

            long get(int l, int r) {
                if(l > r) return Math.min(get(0, r), get(l, input.length - 1));
                return get(parent, l, r);
            }

            long get(Vertex v, int l, int r) {
                if(l <= v.l && v.r <= r) return v.get();
                if(l <= v.r && v.l <= r)
                    return v.pot + Math.min(get(v.left, l, r), get(v.right, l, r));
                return INF;
            }

            void incr(int l, int r, long val) {
                if(l > r) {
                    incr(parent, 0, r, val);
                    incr(parent, l, input.length - 1, val);
                } else {
                    incr(parent, l, r, val);
                }
            }

            long incr(Vertex v, int l, int r, long val) {
                if(l <= v.l && v.r <= r) v.pot += val;
                else if(l <= v.r && v.l <= r) {
                    v.val = Math.min(incr(v.left, l, r, val), incr(v.right, l, r, val));
                }
                return v.get();
            }

            class Vertex {
                int l;
                int r;
                long val;
                long pot = 0;
                Vertex left;
                Vertex right;

                public Vertex(int l, int r, long val) {
                    this.l = l;
                    this.r = r;
                    this.val = val;
                }

                long get() {
                    return val + pot;
                }

            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(long i) {
            writer.println(i);
        }

    }

    static class IOUtils {
        public static int[] readIntArray(InputReader in, int size) {
            int[] array = new int[size];
            for(int i = 0; i < size; i++)
                array[i] = in.readInt();
            return array;
        }

    }

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

        public InputReader(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 readInt() {
            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 String readLine(boolean ignoreEmptyLines) {
            if(ignoreEmptyLines)
                return readLine();
            else
                return readLine0();
        }

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

        }

    }
}

