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.io.*;
public class CircularRMQ
{

    public static void main(String[] args) throws IOException
    {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder str = new StringBuilder();
        int n = Integer.parseInt(input.readLine());
        int[] vals = new int[n];
        String nums = input.readLine();
        StringTokenizer tok = new StringTokenizer(nums);
        for (int i = 0; i < n; i++)
        {
            vals[i] = Integer.parseInt(tok.nextToken());
        }
        int m = Integer.parseInt(input.readLine());
        SegmentTree tree = new SegmentTree(0, n - 1, vals);
        for (int j = 0; j < m; j++)
        {
            tok = new StringTokenizer(input.readLine());
            int l = Integer.parseInt(tok.nextToken());
            int r = Integer.parseInt(tok.nextToken());
            if (tok.hasMoreTokens())
            {
                int v = Integer.parseInt(tok.nextToken());;
                if (l <= r)
                {
                    tree.updateInterval(l, r, v);
                }
                else
                {
                    tree.updateInterval(l, n-1, v);
                    tree.updateInterval(0, r, v);
                }
            }
            else
            {
                int result;
                if (l <= r)
                {
                    result = tree.queryInterval(l, r);
                }
                else
                {

                    result = Math.min(tree.queryInterval(0, r), tree.queryInterval(l, n-1));
                }
                str.append(result + "\n");
            }
        }
        System.out.print(str);
    }

    static class SegmentTree
    {
        int left;
        int right;
        SegmentTree leftTree;
        SegmentTree rightTree;
        int val;
        int addition;

        public SegmentTree(int left, int right, int[] vals)
        {
            this.left = left;
            this.right = right;
            if (left != right)
            {
                leftTree = new SegmentTree(left, left + (right-left)/2, vals);
                rightTree = new SegmentTree(left + (right-left)/2 + 1, right, vals);
                val = Math.min(leftTree.val, rightTree.val);
            }
            else
            {
                val = vals[left];
            }
            addition = 0;
        }

        public void updateInterval(int l, int r, int v)
        {
            if (l <= left && r >= right)
            {
                addition += v;
            }
            else if ((l >= left && l <= right) || (r >= left && r <= right))
            {
                leftTree.updateInterval(l, r, v);
                rightTree.updateInterval(l, r, v);
                val = Math.min(leftTree.val + leftTree.addition, rightTree.val + rightTree.addition);
            }
        }

        public int queryInterval(int l, int r)
        {
            if (l <= left && r >= right)
            {
                return val + addition;
            }
            else if ((l >= left && l <= right) || (r >= left && r <= right))
            {
                int lVal = leftTree.queryInterval(l, r);
                int rVal = rightTree.queryInterval(l, r);
                return Math.min(lVal, rVal) + addition;
            }
            return Integer.MAX_VALUE;
        }
    }
}
