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
//package practice;
import java.util.*;
import java.io.*;
public class CF52C {

	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(System.in);
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int size=Integer.parseInt(st.nextToken());
		int[] _A=new int[size];
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<size;i++)
		{
			_A[i]=Integer.parseInt(st.nextToken());
		}
		segment_tree tree=new segment_tree(size, _A);
		st=new StringTokenizer(br.readLine());
		int q=Integer.parseInt(st.nextToken());
		int numoftok;
		for(int i=0;i<q;i++)
		{
			st=new StringTokenizer(br.readLine());
			numoftok=st.countTokens();
			if(numoftok==2)
			{
				int a=Integer.parseInt(st.nextToken());
				int b=Integer.parseInt(st.nextToken());
				if(a>b)
				{
					long min=Math.min(tree.dynamic_rmq(a , tree.n-1),tree.dynamic_rmq(0, b) );
					System.out.println(min);
				}
				else
				{
					System.out.println(tree.dynamic_rmq(a, b));
				}
			}
			else
			{
				int a=Integer.parseInt(st.nextToken());
				int b=Integer.parseInt(st.nextToken());
				int c=Integer.parseInt(st.nextToken());
				if(a>b)
				{
//					System.out.println();
					tree.dynamic_update(a, size-1, c);
					tree.dynamic_update(0, b     , c);
				}
				else
				{
					tree.dynamic_update(a, b, c);
				}
			}
		}
		
		
	}
	
	
	public static class segment_tree
	{
		static long[] A;
		static long[] st;
		static long[] lazy;
		static int n;
		static int right(int p){ return (p<<1)+1;}
		static int left (int p){ return (p<<1);  }
		public segment_tree(int size,int[] _A)
		{
			n=size;
			A=new long[n];
			st=new long[4*n];
			lazy=new long[4*n];
			for(int i=0;i<size;i++)
				A[i]=_A[i];
			for(int i=0;i<4*n;i++)
			{
				
				lazy[i]=0;
				st[i]=0;
			}
			build(1,0,n-1);
		}
		
		
		
		static int rmq(int i,int j){ return rmq(1,0,n-1,i,j);}
		static int rmq(int p,int l,int r,int i,int j)
		{
			if(i>r||j<l) return -1;
//			if(l>=i&&r<=j) return st[p];
			int mid=(r+l)/2;
			int p1=rmq(left(p),l,mid,i,j);
			int p2=rmq(right(p),mid+1,r,i,j);
			if(p1==-1) return p1;
			if(p2==-1) return p1;
			
			
			return (A[p1]<=A[p2])?p1:p2;
		}
		static void build(int p,int l,int r)
		{
			if(l==r)
			{
				st[p]=A[l];
			}
			else
			{
				int mid=(l+r)/2;
				build(left(p) ,l    ,mid);
				build(right(p),mid+1,r  );
				long p1=st[left(p) ];
				long p2=st[right(p)];
				st[p]=(p1<=p2)?p1:p2;
			}
		}
//		static int update(int p,int l,int r,int idx,int new_value)
//		{
//			int i=idx; int j=idx;
//			if(i<r||j>l) return st[p];
//			if(r==i&&j==l)
//			{
//				A[i]=new_value;
//				st[p]=idx;
//			}
//			
//			int p1=update(left(p), l, (l+r)/2, idx, new_value);
//			int p2=update(right(p), ((l+r)/2)+1, r, idx, new_value);
//			
//			
//			return st[p]=(A[p1]<=A[p2])?p1:p2;
//		}
		
		// lazy propagation
		static void refresh(int idx)
		{
			lazy[right(idx)]+=lazy[idx];
			lazy[left(idx)] +=lazy[idx];
			lazy[idx]=0;
		}
		static long getValue(int idx,int l,int r)
		{
//			return st[idx]+(lazy[idx]*(r-l+1));
			return st[idx]+lazy[idx];
		}
		static void dynamic_update(int i,int j,int val){ dynamic_update(1, 0, n-1, i, j, val);}
		static void dynamic_update(int idx,int l,int r,int i,int j,long new_value)
		{
			if(i <= l && j >= r)
			{
				lazy[idx]+=new_value;
				return ;
			}
			else if(i > r || j < l)
				return ;
			else
			{
				refresh(idx);
				int mid=(l+r)/2;
				dynamic_update(left(idx) , l    , mid, i, j, new_value);
				dynamic_update(right(idx), mid+1, r  , i, j, new_value);
				st[idx]=Math.min(getValue(left(idx), l, mid),getValue(right(idx), mid+1, r));
			}
		}
		static long dynamic_rmq(int i,int j){return dynamic_rmq(1,0,n-1,i,j);}
		
		static long dynamic_rmq(int idx,int l,int r,int i,int j)
		{
			if(i <= l && j >= r)
				return getValue(idx, l, r);
			else if(i > r || j < l)
				return Long.MAX_VALUE;
			else
			{
				refresh(idx);
				int mid=(l+r)/2;
				long p1=dynamic_rmq(left(idx), l, mid, i, j);
				long p2=dynamic_rmq(right(idx), mid+1, r, i, j);
				st[idx]=Math.min(getValue(left(idx), l, mid),getValue(right(idx), mid+1, r));
//				return p1+p2;
				return Math.min(p1,p2);
			}
		}
	}

}
