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.*;



public class Main {

    static long[] tree;
    static long[] lazy;
    static long[] a;

    static void build(int node,int start,int end){
        if(start == end)
            tree[node] = a[start];
        else{
            int mid = (start+end)/2;
            build(2*node,start,mid);
            build(2*node+1,mid+1,end);
            tree[node] = Math.min(tree[2*node+1], tree[2*node]);
        }
    }

    

    static long queryRange(int node, int start, int end, int l, int r){
        // This node needs to be updated
        if(lazy[node] != 0){
            tree[node] += lazy[node];
            if(start != end)
            {
                lazy[node*2] += lazy[node];
                lazy[node*2+1] += lazy[node];
            }
            lazy[node] = 0;
        }
        if(start > end || start > r || end < l)
            return Long.MAX_VALUE;

        if(start >= l && end <= r)
            return tree[node];
        int mid = (start + end) / 2;
        long p1 = queryRange(node*2, start, mid, l, r);
        long p2 = queryRange(node*2 + 1, mid + 1, end, l, r);
        return Math.min(p1,p2);
    }


    static void updateRange(int node, int start, int end, int l, int r, long val){

        // If we need to update it
        if(lazy[node] != 0){
            //add the propagated value to the tree
            tree[node] += lazy[node];
            if(start != end){
                //push the propagated value further down the tree, if we are not at a leaf node
                lazy[node*2] += lazy[node];
                lazy[node*2+1] += lazy[node];
            }
            lazy[node] = 0;
        }
        /*if we are entirely out of range, just return*/
        if(start > end || start > r || end < l)
            return;

        /*if we are entirely capturing the segment, add value to current tree node,
           then do a lazy propagation on the level above
         */
        if(start >= l && end <= r){
            tree[node] += val;
            if(start != end){
                lazy[node*2] += val;
                lazy[node*2+1] += val;
            }
            return;
        }
        /*If we are partly in range, recurse further down*/
        int mid = (start + end) / 2;
        updateRange(node*2, start, mid, l, r, val);
        updateRange(node*2 + 1, mid + 1, end, l, r, val);
        tree[node] = Math.min(tree[node*2],tree[node*2+1]);
    }



    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        a = new long[n+1];
        int treeheight = (int)(Math.ceil(Math.log(n)/Math.log(2)));
        int stLen = 2 * (int)Math.pow(2,treeheight);
        tree = new long[stLen];
        lazy = new long[stLen];
        String[] splitter = reader.readLine().split(" ");
        for(int i=1; i<=splitter.length; i++)
            a[i] = Long.parseLong(splitter[i-1]);
        build(1,1,n);

        int q = Integer.parseInt(reader.readLine());
        for(int i=0; i<q; i++){
            splitter = reader.readLine().split(" ");
            int left = Integer.parseInt(splitter[0])+1;
            int right = Integer.parseInt(splitter[1])+1;
            //If updating  values in a range with val
            if(splitter.length == 3){
                int val = Integer.parseInt(splitter[2]);
                if(left > right){
                    updateRange(1,1,n,left,n,val);
                    updateRange(1,1,n,1,right,val);
                }
                else
                    updateRange(1,1,n,left,right,val);
            }
            //if finding min value in a given range
            else {
                if(left > right){
                    long alt1 = queryRange(1,1,n,left,n);
                    long alt2 = queryRange(1,1,n,1,right);
                    System.out.println(Math.min(alt1,alt2));
                }
                else
                    System.out.println( queryRange(1,1,n,left,right));
            }
        }
        reader.close();
    }
}










