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 {
        int BLOCK;
        long[] a;
        long[] parentmoar;
        long[] parentmin;

        void getmin(int block) {
            long res = Long.MAX_VALUE;
            for(int i = block * BLOCK; i < a.length && i < (block + 1) * BLOCK; i++)
                res = Math.min(res, a[i]);
            parentmin[block] = res + parentmoar[block];
        }

        void incr(int l, int r, int val) {
            if(r < l) {
                implincr(0, r, val);
                implincr(l, a.length - 1, val);
            } else {
                implincr(l, r, val);
            }
        }

        void implincr(int l, int r, int val) {
            int lowblock = l / BLOCK;
            int highblock = r / BLOCK;
            for(int block = lowblock; block <= highblock; block++) {
                if(block == lowblock || block == highblock) {
                    int left = Math.max(l, block * BLOCK);
                    int right = Math.min(r, (block + 1) * BLOCK - 1);
                    if(right - left + 1 == BLOCK) {
                        parentmoar[block] += val;
                        parentmin[block] += val;
                    } else {
                        for(int i = left; i <= right; i++)
                            a[i] += val;
                        getmin(block);
                    }
                } else {
                    parentmoar[block] += val;
                    parentmin[block] += val;
                }
            }
        }

        long get(int l, int r) {
            if(r < l) return Math.min(implget(0, r), implget(l, a.length - 1));
            return implget(l, r);
        }

        long implget(int l, int r) {
            int lowblock = l / BLOCK;
            int highblock = r / BLOCK;
            long ans = Long.MAX_VALUE;
            for(int block = lowblock; block <= highblock; block++) {
                if(block == lowblock || block == highblock) {
                    int low = Math.max(l, block * BLOCK);
                    int high = Math.min(r, (block + 1) * BLOCK - 1);
                    if(high - low + 1 == BLOCK) {
                        ans = Math.min(ans, parentmin[block]);
                    } else {
                        long anshere = Long.MAX_VALUE;
                        for(int i = low; i <= high; i++)
                            anshere = Math.min(anshere, a[i]);
                        ans = Math.min(ans, anshere + parentmoar[block]);
                    }
                } else {
                    ans = Math.min(ans, parentmin[block]);
                }
            }
            return ans;
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            int[] input = IOUtils.readIntArray(in, n);

            a = new long[input.length];
            BLOCK = (int) Math.sqrt(input.length) + 1;
            parentmoar = new long[BLOCK];
            parentmin = new long[BLOCK];
            for(int i = 0; i < input.length; i++) a[i] = input[i];
            for(int block = 0; block < BLOCK; block++) getmin(block);

            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(get(args[0], args[1]));
                else incr(args[0], args[1], args[2]);
            }
        }

    }

    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);

        }

    }
}

