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 C {
	
	
	
	
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		int n=sc.nextInt();
		long []a=new long [n];
		for(int i=0;i<n;i++)
			a[i]=sc.nextInt();
		SegmentTree tree=new SegmentTree(a);
		
		int q=sc.nextInt();
		while(q-->0)
		{
			StringTokenizer st=new StringTokenizer(sc.nextLine());
			if(st.countTokens()==2)
			{
				int l=Integer.parseInt(st.nextToken()),r=Integer.parseInt(st.nextToken());
				
				long x;
				if(r<l)
				{
					 x=tree.query(l, n-1);
					x=Math.min(x, tree.query(0, r));
				}
				else
				{
					x=tree.query(l, r);
				}
				pw.println(x);
			}
			else
			{
				int l=Integer.parseInt(st.nextToken()),r=Integer.parseInt(st.nextToken()),v=Integer.parseInt(st.nextToken());
				if(r<l)
				{
					 tree.updateRange(l, n-1,v);
					 tree.updateRange(0, r,v);
				}
				else
				{
					tree.updateRange(l, r,v);
				}
			}
			
		}
		pw.close();
		

	}
	static class SegmentTree
	{
		
		long []min,lazy;
		long []a;
		SegmentTree(long []a)
		{
			this.a=a;
			int n=a.length;
			min=new long [4*n];
			lazy=new long [4*n];
			build(1,0,n-1);
		}
		
		void build(int node,int tl,int tr)
		{
			if(tl==tr)
				min[node]=a[tl];
			else 
			{
				int mid=tl+tr>>1;
				build(node*2,tl,mid);
				build(node*2+1,mid+1,tr);
				merge(node);
			}
		}
		void merge(int node) 
		{
			min[node]=Math.min(min[node*2],min[node*2+1]);
		}
		long query(int l,int r)
		{
			return query(1,0,a.length-1,l,r);
		}
		long query(int node,int tl,int tr,int l,int r)
		{
			if(tr < l || r<tl)
				return Integer.MAX_VALUE;
			if(tl>=l && tr<=r)
				return min[node];
			int mid=tl+tr>>1;
			propagate(node);
			return Math.min(query(node*2,tl,mid,l,r),query(node*2+1,mid+1,tr,l,r));
			
		}
		void updateRange(int l,int r,int v)
		{
			updateRange(1,0,a.length-1,l,r,v);
		}
		void updateRange(int node,int tl,int tr,int l,int r,int v)
		{
			if(tr<l || r<tl)
				return;
			if(tl>=l && tr<=r)
			{
				min[node]+=v;
				lazy[node]+=v;
			}
			else
			{
				int mid=tl+tr>>1;
				propagate(node);
				updateRange(node*2,tl,mid,l,r,v);
				updateRange(node*2+1,mid+1,tr,l,r,v);
				merge(node);
			}
		}
		void propagate(int node)
		{
			int left=node*2,right=left+1;
			min[left]+=lazy[node];
			lazy[left]+=lazy[node];
			min[right]+=lazy[node];
			lazy[right]+=lazy[node];
			lazy[node]=0;
		}
	}
	
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
		public Scanner(String s) throws FileNotFoundException {br = new BufferedReader(new FileReader(s));}
		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
		
		public double nextDouble() throws IOException
		{
			return Double.parseDouble(next());
		}
		
		public boolean ready() throws IOException {return br.ready();}


	}
}