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.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
public class segmentTree {
	public static int max=(int)Double.POSITIVE_INFINITY;
	public static int[] lazy;
	public static void constructTree(int[] array,int[] segArray,int low,int high,int pos) {
		if(low==high) {segArray[pos]=array[low];return ;}
		int mid = (low+high)/2;
		constructTree(array,segArray,low,mid,2*pos);
		constructTree(array,segArray,mid+1,high,2*pos+1);
		segArray[pos]=Math.min(segArray[pos*2], segArray[pos*2+1]);
	}
	public static int[] construct(int[] array) {
		double t=Math.log(array.length)/Math.log(2);
		int[] segArray;
		if(t==(int)t) {
			segArray=new int[2*array.length];
		}
		else {
			segArray= new int[(int) (Math.pow(2, (int)t+1)*2)];
		}
		constructTree(array,segArray,0,array.length-1,1);
		lazy= new int[segArray.length];
		return segArray;
	}
	
	public static int minQ(int[] segArray,int qlow,int qhigh,int low,int high,int pos) {
		if(lazy[pos]!=0) {
			segArray[pos]+=lazy[pos];
			if(low!=high) {
				lazy[pos*2]+=lazy[pos];
				lazy[pos*2+1]+=lazy[pos];
			}
			lazy[pos]=0;
		}		
		//total overlap
		if(qlow<=low&&qhigh>=high)return segArray[pos];
		//no overlap
		if(qlow>high||qhigh<low)return max;
		//partial overlap
		int mid=(low+high)/2;
		return Math.min(minQ(segArray,qlow,qhigh,low,mid,2*pos), minQ(segArray,qlow,qhigh,mid+1,high,pos*2+1));
	}
	public static int getMin(int[] segArray,int[] array,int qlow,int qhigh) {
		if(qlow>qhigh) {
			return Math.min(minQ(segArray,qlow,array.length-1,0,array.length-1,1), minQ(segArray,0,qhigh,0,array.length-1,1));
		}
		return minQ(segArray,qlow,qhigh,0,array.length-1,1);
	}
	
	public static void updateSegTree(int[] segArray, int[] lazy, int low, int high, int qlow, int qhigh,int pos,int val) {
		if(low>high)return;
		if(lazy[pos]!=0) {
			segArray[pos]+=lazy[pos];
			if(low!=high) {
				lazy[pos*2]+=lazy[pos];
				lazy[pos*2+1]+=lazy[pos];
			}
			lazy[pos]=0;
		}
		//total overlap
		if(qlow<=low&&qhigh>=high) {
			segArray[pos]+=val;
			if(low!=high) {
				lazy[pos*2]+=val;
				lazy[pos*2+1]+=val;
			}
			return ;
		}
		//no overlap
		if(qlow>high||qhigh<low)
			return ;
		//partial overlap
		int mid=(low+high)/2;
		updateSegTree(segArray,lazy,low,mid,qlow,qhigh,pos*2,val);
		updateSegTree(segArray,lazy,mid+1,high,qlow,qhigh,pos*2+1,val);
		segArray[pos]=Math.min(segArray[pos*2],segArray[pos*2+1]);
	}
									
										
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		PrintWriter pw= new PrintWriter(System.out);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
		}
		int[] segTree=construct(a);
		int t=sc.nextInt();
		sc.nextLine();
		while(t>0) {
			String[] op=sc.nextLine().split(" ");
			if(op.length==2) {
				pw.println(getMin(segTree,a,Integer.parseInt(op[0]),Integer.parseInt(op[1])));
			}
			else {
				if(Integer.parseInt(op[0])>Integer.parseInt(op[1]))
				{
					updateSegTree(segTree,lazy,0,a.length-1,0,Integer.parseInt(op[1]),1,Integer.parseInt(op[2]));
					updateSegTree(segTree,lazy,0,a.length-1,Integer.parseInt(op[0]),a.length-1,1,Integer.parseInt(op[2]));
				}
				else
				updateSegTree(segTree,lazy,0,a.length-1,Integer.parseInt(op[0]),Integer.parseInt(op[1]),1,Integer.parseInt(op[2]));
			}
			t--;
		}
		pw.flush();
	}
}
