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.util.*;
import java.lang.*;
import java.io.*;

public class SegmentTree {
    private static final long INF = (long) 1e18;
    private static class Node {
        long mina;
        long lazy;

        public Node(long mina, long lazy) {
            this.mina = mina;
            this.lazy = lazy;
        }
    }

        private static void buildTree(ArrayList<Integer> a, ArrayList<Node> segTree, int left, int right, int index) {
            if (left == right) {
                segTree.get(index).mina = a.get(left);
                return;
            }
            int mid = (left + right) / 2;
            buildTree(a, segTree, left, mid, 2 * index + 1);
            buildTree(a, segTree, mid+1, right, 2 * index + 2);
            segTree.get(index).mina = Math.min(segTree.get(2 * index + 1).mina, segTree.get(2 * index + 2).mina);
        }

        private static void updateMinimumRange(ArrayList<Node> segTree, int left, int right, int from, int to, int val, int index) {
            if (left > right) return;
            if (segTree.get(index).lazy != 0) {
                segTree.get(index).mina += segTree.get(index).lazy;
                if (left != right) {
                    segTree.get(2 * index + 1).lazy += segTree.get(index).lazy;
                    segTree.get(2 * index + 2).lazy += segTree.get(index).lazy;
                }
                segTree.get(index).lazy = 0;
            }
            if (left >= from && right <= to) {
                segTree.get(index).mina += val;
                if (left != right) {
                    segTree.get(2 * index + 1).lazy += val;
                    segTree.get(2 * index + 2).lazy += val;
                }
                return;
            }
            if (from > right || to < left) return;
            int mid = (left + right) / 2;
            updateMinimumRange(segTree, left, mid, from, to, val, 2 * index + 1);
            updateMinimumRange(segTree, mid+1, right, from, to, val, 2 * index + 2);
            segTree.get(index).mina = Math.min(segTree.get(2 * index+1).mina, segTree.get(2 * index+2).mina);
            return;
        }

        private static long minimumRangeLazy(ArrayList<Node> segTree, int left, int right, int from, int to, int index) {
            if (left > right) return INF;
            if (segTree.get(index).lazy != 0) {
                segTree.get(index).mina += segTree.get(index).lazy;
                if (left != right) {
                    segTree.get(2 * index + 1).lazy += segTree.get(index).lazy;
                    segTree.get(2 * index + 2).lazy += segTree.get(index).lazy;
                }
                segTree.get(index).lazy = 0;
            }
            if (left >= from && right <= to) {
                return segTree.get(index).mina;
            }
            if (from > right || to < left) return INF;
            int mid = (left+right) / 2;
            long minLeft = minimumRangeLazy(segTree, left, mid, from, to, 2 * index+1);
            long minRight = minimumRangeLazy(segTree, mid+1, right, from, to, 2 * index+2);
            return Math.min(minLeft, minRight);
        }

        private static void circularUpdate(int n, ArrayList<Node> segTree, int from, int to, int delta) {
            if (from <= to) {
                updateMinimumRange(segTree, 0, n - 1, from, to, delta, 0);
                return;
            }
            updateMinimumRange(segTree, 0, n - 1, from, n - 1, delta, 0);
            updateMinimumRange(segTree, 0, n - 1, 0, to, delta, 0);
            return;
        }

        private static long circularQuery(int n, ArrayList<Node> segTree, int from, int to) {
            if (from <= to) {
                return minimumRangeLazy(segTree, 0, n - 1, from, to, 0);
            }
            return Math.min(minimumRangeLazy(segTree, 0, n - 1, from, n - 1, 0), minimumRangeLazy(segTree, 0, n - 1, 0, to, 0));
        }

        private static double logb(double a, double b) {
            return Math.log(a) / Math.log(b);
        }

        private static double log2(double a) {
            return logb(a, 2.0);
        }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter o = new PrintWriter(System.out);

        int n = in.nextInt();
        ArrayList<Integer> a = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            a.add(in.nextInt());
        }
        int h = (int) Math.ceil(log2(n));
        int sizeTree = 2 * (int) Math.pow(2, h) - 1;
        ArrayList<Node> segTree = new ArrayList<>();
        for (int i = 0; i < sizeTree; i++) {
            segTree.add(new Node(0, 0));
        }
        buildTree(a, segTree, 0, n-1, 0);
        int q = in.nextInt();
        String line = in.nextLine();
        while (q-- > 0) {
            line = in.nextLine();
            StringTokenizer st = new StringTokenizer(line);
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            if (st.hasMoreTokens()) {
                int delta = Integer.parseInt(st.nextToken());
                circularUpdate(n, segTree, from, to, delta);
            } else {
                o.println(circularQuery(n, segTree, from, to));
            }
        }
        o.close();
        return;


    }

}