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.ArrayList;
import java.util.StringTokenizer;

public class CircularRMQ {

    public static void main(String[] args) throws IOException {

        FastReader reader = new FastReader();
        FastWriter writer = new FastWriter();
        int n = reader.readSingleInt();

        int[] array = reader.readIntArray(n);
        SegmentTree segmentTree = new SegmentTree(0, n-1, array);

        int m = reader.readSingleInt();
        for(int i = 0; i<m; i++){
            ArrayList<Integer> operation = reader.arrayReader();
            if(operation.size() == 3){
                int l = operation.get(0);
                int r = operation.get(1);
                int v = operation.get(2);
                if(l > r){
                    segmentTree.rangeUpdate(l, n-1, v);
                    segmentTree.rangeUpdate(0, r, v);
                } else {
                    segmentTree.rangeUpdate(l,r,v);
                }
            } else {
                int l = operation.get(0);
                int r = operation.get(1);
                if(l > r){
                    writer.writeSingleLong(Math.min(segmentTree.getRangeMin(l, n-1), segmentTree.getRangeMin(0, r)));
                } else {
                    writer.writeSingleLong(segmentTree.getRangeMin(l, r));
                }
            }
        }


    }



    public static class SegmentTree {

        SegmentTree leftChild, rightChild;
        long delta; //For lazy propagation.
        int left, right;
        long rangeMin, rangeMax;
        long rangeSum;


        public SegmentTree(int left, int right, int[] array) {
            this.left = left;
            this.right = right;
            if(left == right){
                rangeSum = array[left];
                rangeMin = array[left];
                rangeMax = array[left];
            } else {
                int middle = left + (right-left)/2;
                leftChild = new SegmentTree(left, middle, array);
                rightChild = new SegmentTree(middle+1, right, array);
                reCalcRangeSum();
                reCalcRangeMin();
                reCalcRangeMax();
            }
        }

        public void pointUpdate(int index, int newVal){
            if(left == right) {
                rangeSum = newVal;
                rangeMin = newVal;
                rangeMax = newVal;
                return;
            }
            if(index <= leftChild.right){
                leftChild.pointUpdate(index, newVal);
            } else {
                rightChild.pointUpdate(index, newVal);
            }
            reCalcRangeSum();
            reCalcRangeMin();
            reCalcRangeMax();
        }

        public void rangeUpdate(int l, int r, int value){
            //Three cases
            if(right < l || left > r){
                return;
            }
            if(l <= left && right <= r){
                delta += value;
                return;
            }
            propagateDelta();
            leftChild.rangeUpdate(l, r, value);
            rightChild.rangeUpdate(l, r, value);
            reCalcRangeSum();
            reCalcRangeMin();
            reCalcRangeMax();

        }

        public long getRangeMin(int l, int r){
            //Three cases:
            if(right < l || left > r){
                return Integer.MAX_VALUE;
            }
            if(l <= left && right <= r){
                return rangeMin + delta;
            } else {
                propagateDelta();
                reCalcRangeSum();
                reCalcRangeMin();
                reCalcRangeMax();
                return Math.min(leftChild.getRangeMin(l, r), rightChild.getRangeMin(l, r));
            }
        }

        public long getRangeMax(int l, int r){
            //Three cases:
            if(right < l || left > r){
                return Integer.MIN_VALUE;
            }
            if(l <= left && right <= r){
                return rangeMax + delta;
            } else {
                propagateDelta();
                reCalcRangeSum();
                reCalcRangeMin();
                reCalcRangeMax();
                return Math.max(leftChild.getRangeMax(l, r), rightChild.getRangeMax(l, r));
            }
        }

        public long getRangeSum(int l, int r){
            //Three cases:
            if(right < l || left > r){
                return 0;
            }
            if(l <= left && right <= r){
                return rangeSum + (right-left+1)*delta;
            } else {
                propagateDelta();
                reCalcRangeSum();
                reCalcRangeMin();
                reCalcRangeMax();
                return leftChild.getRangeSum(l, r) + rightChild.getRangeSum(l, r) + (r-l+1);
            }
        }

        public void propagateDelta(){
            leftChild.delta += delta;
            rightChild.delta += delta;
            this.delta = 0;
        }

        public void reCalcRangeSum(){
            if(left == right) return;
            long plusLeft = (leftChild.right-leftChild.left+1)*leftChild.delta;
            long plusRight = (rightChild.right-rightChild.left+1)*rightChild.delta;
            rangeSum = leftChild.rangeSum + rightChild.rangeSum + plusLeft + plusRight;
        }

        public void reCalcRangeMin(){
            if(left == right) return;
            rangeMin = Math.min(leftChild.rangeMin + leftChild.delta, rightChild.rangeMin + rightChild.delta);
        }

        public void reCalcRangeMax(){
            if(left == right) return;
            rangeMax = Math.max(leftChild.rangeMax + leftChild.delta, rightChild.rangeMax + rightChild.delta);
        }
    }




    public static void mergeSort(int[] a, int n) {
        if (n < 2) {
            return;
        }
        int mid = n / 2;
        int[] l = new int[mid];
        int[] r = new int[n - mid];

        for (int i = 0; i < mid; i++) {
            l[i] = a[i];
        }
        for (int i = mid; i < n; i++) {
            r[i - mid] = a[i];
        }
        mergeSort(l, mid);
        mergeSort(r, n - mid);

        merge(a, l, r, mid, n - mid);
    }


    public static void merge(int[] a, int[] l, int[] r, int left, int right) {

        int i = 0, j = 0, k = 0;
        while (i < left && j < right) {
            if (l[i] <= r[j]) {
                a[k++] = l[i++];
            }
            else {
                a[k++] = r[j++];
            }
        }
        while (i < left) {
            a[k++] = l[i++];
        }
        while (j < right) {
            a[k++] = r[j++];
        }
    }


    public static class FastReader {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer;


        public int readSingleInt() throws IOException {
            return Integer.parseInt(reader.readLine());
        }

        public int[] readIntArray(int numInts) throws IOException {
            int[] nums = new int[numInts];
            tokenizer = new StringTokenizer(reader.readLine());
            for(int i = 0; i<numInts; i++){
                nums[i] = Integer.parseInt(tokenizer.nextToken());
            }
            return nums;
        }

        public String readString() throws IOException {
            return reader.readLine();
        }

        public ArrayList<Integer> arrayReader() throws IOException {
            ArrayList<Integer> array = new ArrayList<>();
            tokenizer = new StringTokenizer(reader.readLine());
            while(tokenizer.hasMoreTokens()){
                array.add(Integer.parseInt(tokenizer.nextToken()));
            }
            return array;
        }


    }



    public static class FastWriter {

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));


        public void writeSingleInteger(int i) throws IOException {
            writer.write(Integer.toString(i));
            writer.newLine();
            writer.flush();
        }

        public void writeSingleLong(long i) throws IOException {
            writer.write(Long.toString(i));
            writer.newLine();
            writer.flush();
        }

        public void writeIntArrayWithSpaces(int[] nums) throws IOException {
            for(int i = 0; i<nums.length; i++){
                writer.write(nums[i] + " ");
            }
            writer.newLine();
            writer.flush();
        }

        public void writeIntArrayWithoutSpaces(int[] nums) throws IOException {
            for(int i = 0; i<nums.length; i++){
                writer.write(Integer.toString(nums[i]));
            }
            writer.newLine();
            writer.flush();
        }

        public void writeString(String s) throws IOException {
            writer.write(s);
            writer.newLine();
            writer.flush();
        }

    }
}
