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.BufferedReader;
import java.io.IOException;
import java.io.*;

public class CircularRMQ {

    static class SegmentTree {

        long[] tree;
        long[] num;
        int[] update;

        public SegmentTree(long[] array) {
            int n = array.length;
            double logN = Math.log(n) / Math.log(2);
            int size = (int) (2 * (Math.pow(2, logN + 1)));
            tree = new long[size];
            update = new int[size];
            num = array;
            build(1, 0, n - 1);
        }

        public void build(int index, int start, int end) {
            if (start == end)
                tree[index] = num[start];
            else {
                int left = 2 * index;
                int right = left + 1;
                int mid = (start + end) / 2;
                build(left, start, mid);
                build(right, mid + 1, end);
                if (tree[left] < tree[right])
                    tree[index] = tree[left];
                else
                    tree[index] = tree[right];
            }
        }

        public long query(int index, int i, int j, int start, int end) {
            // RMQ ( i , j )
            if (i > end || j < start)
                return Long.MAX_VALUE;
            if (start >= i && end <= j)
                return tree[index];

            int left = 2 * index;
            int right = left + 1;
            int mid = (start + end) / 2;
            if (update[index] != 0) {
                propagate(left, start, mid, update[index]);
                propagate(right, mid + 1, end, update[index]);
                update[index] = 0;
            }
            long leftQuery = query(left, i, j, start, mid);
            long rightQuery = query(right, i, j, mid + 1, end);
            return Math.min(leftQuery, rightQuery);
        }

        public void propagateToRoot(int index, int value) {
            while (index >= 1) {
                tree[index] += value;
                index /= 2;
            }
        }

        public void propagate(int index, int start, int end, int value) {
            update[index] += value;
            tree[index] += value;
            if (start == end)
                update[index] = 0;
        }

        public void update(int index, int from, int to, int value, int start,
                int end) {
            if (from > end || to < start)
                return;
            if (start >= from && end <= to) {
                update[index] += value;
                tree[index] += value;
                if (start == end)
                    update[index] = 0;
                propagateToRoot(index / 2, value);
            } else {
                int left = 2 * index;
                int right = left + 1;
                int mid = (start + end) / 2;
                if (update[index] != 0) {
                    propagate(left, start, mid, update[index]);
                    propagate(right, mid + 1, end, update[index]);
                    update[index] = 0;
                }
                update(left, from, to, value, start, mid);
                update(right, from, to, value, mid + 1, end);
                if (tree[left] < tree[right])
                    tree[index] = tree[left];
                else
                    tree[index] = tree[right];
                // -----------------

            }
        }
    }

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(
                System.out));
        String s = r.readLine();
        s = r.readLine();
        String[] sp = s.split(" ");
        long[] arr = new long[sp.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Long(sp[i]);
        }
        SegmentTree seg = new SegmentTree(arr);
        int m = new Integer(r.readLine());
        while (m-- > 0) {
            s = r.readLine();
            sp = s.split(" ");
            if (sp.length == 3) {
                int left = new Integer(sp[0]);
                int right = new Integer(sp[1]);
                int v = new Integer(sp[2]);
                if (left <= right) {
                    seg.update(1, left, right, v, 0, arr.length - 1);
                } else {
                    seg.update(1, left, arr.length - 1, v, 0, arr.length - 1);
                    seg.update(1, 0, right, v, 0, arr.length - 1);
                }
            } else {
                int left = new Integer(sp[0]);
                int right = new Integer(sp[1]);
                long query = -1;
                if (left <= right) {
                    query = seg.query(1, left, right, 0, arr.length - 1);
                    writer.write("" + query);
                    writer.newLine();

                } else {
                    long query1 = seg.query(1, left, arr.length - 1, 0,
                            arr.length - 1);
                    long query2 = seg.query(1, 0, right, 0, arr.length - 1);
                    writer.write("" + (Math.min(query1, query2)));
                    writer.newLine();
                }

            }
        }
        writer.flush();
        writer.close();
    }
}
