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 Main2 {
	static class FastReader{ 
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader(){br = new BufferedReader(new InputStreamReader(System.in));}
        String next(){ while (st == null || !st.hasMoreElements()){ 
                try{st = new StringTokenizer(br.readLine());} 
                catch (IOException  e){e.printStackTrace();}} 
            return st.nextToken();}
        int nextInt(){ return Integer.parseInt(next());}
        long nextLong(){return Long.parseLong(next());} 
        double nextDouble(){return Double.parseDouble(next());}
        String nextLine(){ 
            String str = ""; 
            try{str = br.readLine(); } 
            catch (IOException e) {e.printStackTrace();} 
            return str; } 
    }
	static Scanner in = new Scanner(System.in);
	public static void main (String[] args) {
		PrintWriter out = new PrintWriter(System.out);
		int t = 1;
//    	t = sc.nextInt();
    	while(t-->0) {
    		int n = in.nextInt();
    		long a[] = new long[n];
    		for(int i=0;i<n;i++) a[i] = in.nextLong();
    		int m = in.nextInt(); in.nextLine();
    		dSegTree seg = new dSegTree(a);
    		for (int i = 0; i < m; i++)
    		{
    			String[] line = in.nextLine().split(" ");
    			int l = Integer.parseInt(line[0]);
    			int r = Integer.parseInt(line[1]);
    			
    			if (line.length == 2)
    			{
    				if(l<=r) {
    					out.write(seg.query(l, r)+"\n");
    				}
    				else {
    					out.write(Math.min(seg.query(0, r),seg.query(l, n-1))+"\n");
    				}
    			}
    			
    			else
    			{
    				long val = Long.parseLong(line[2]);
    				if(l<=r) {
    					seg.update(l, r, val);
    				}
    				else {
    					seg.update(0, r, val);
    					seg.update(l, n-1, val);
    				}
    			}
    		}
		out.close();
    	}
	}
}
class dSegTree {
	static int n;
	static long segTree[], lazy[];
	static long a[];
	public dSegTree(long b[]) {
		segTree = new long[4*b.length+10];
		lazy = new long[4*b.length];
		Arrays.fill(segTree, Long.MAX_VALUE);
		a = b;
		build(0,0,a.length-1);
	}
	private static void build(int idx, int low, int high) {
		if(low == high) {
			segTree[idx] = a[low];
			return;
		}
		
		int mid = (low+high)>>1;
		
		build(2*idx+1,low,mid);
		build(2*idx+2,mid+1,high);
		
		segTree[idx] = Math.min(segTree[2*idx+1], segTree[2*idx+2]);
	}
	public static void update(int l, int r, long val) {
		Update(0,0,a.length-1,l,r,val);
	}
	private static void Update(int ind, int low, int high, int l, int r, long val) {
	    if(lazy[ind] != 0) {
	        segTree[ind] += lazy[ind]; 
	        if(low != high) {
	            lazy[2*ind+1] += lazy[ind];
	            lazy[2*ind+2] += lazy[ind]; 
	        }
	        lazy[ind] = 0; 
	    }
	    if(l>high || low > r) {
	        return; 
	    }
	    if(low >= l && high <= r) {
	        segTree[ind] += val ; 
	        
	        if(low != high) {
	            lazy[2*ind + 1] += val; 
	            lazy[2*ind+2] += val; 
	        }
	        return; 
	    }
	    int mid = (low + high) >> 1; 
	    Update(2*ind+1, low, mid, l, r, val); 
	    Update(2*ind+2, mid+1, high, l, r, val);
	    segTree[ind] = Math.min(segTree[2*ind+1], segTree[2*ind+2]); 
	}
	public static long query(int l, int r) {
		return Query(0,0,a.length-1,l,r);
	}
	private static long Query(int ind, int low, int high, int l, int r) {
	    if(lazy[ind] != 0) {
	        segTree[ind] += lazy[ind]; 
	        if(low != high) {
	            lazy[2*ind+1] += lazy[ind];
	            lazy[2*ind+2] += lazy[ind]; 
	        }
	        lazy[ind] = 0; 
	    }
	    if(l>high || low > r) {
	        return Long.MAX_VALUE; 
	    }
	    if(low >= l && high <= r) {
	        return segTree[ind]; 
	    }
	    int mid = (low + high) >> 1; 
	    long left = Query(2*ind+1, low, mid, l, r); 
	    long right = Query(2*ind+2, mid+1, high, l, r); 
	    return Math.min(left, right); 
	}
}

