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 final class circular_rmq_lazy
{
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out=new PrintWriter(System.out);
	static long[] a,tree,lazy;
	
	static void build(int node,int l,int r)
	{
		if(l>r)
		{
			return;
		}
		if(l==r)
		{
			tree[node]=a[l];
		}
		else
		{
			int mid=(l+r)/2;
			build(2*node,l,mid);
			build((2*node)+1,mid+1,r);
			tree[node]=Math.min(tree[2*node],tree[(2*node)+1]);
		}
	}
	
	static void updateRange(int node,int s,int e,int l,int r,long val)
	{
		if(lazy[node]!=0)
		{
			tree[node]+=lazy[node];
			if(s!=e)
			{
				lazy[(2*node)]+=lazy[node];
				lazy[(2*node)+1]+=lazy[node];
			}
			lazy[node]=0;
		}
		if(s>e || l>e || r<s)
		{
			return;
		}
		if(l<=s && r>=e)
		{
			tree[node]+=val;
			if(s!=e)
			{
				lazy[(2*node)]+=val;
				lazy[(2*node)+1]+=val;
			}
			return;
		}
		else
		{
			int mid=(s+e)/2;
			updateRange(2*node,s,mid,l,r,val);
			updateRange((2*node)+1,mid+1,e,l,r,val);
			tree[node]=Math.min(tree[2*node],tree[(2*node)+1]);
		}
	}
	
	static long getMax(int node,int s,int e,int l,int r)
	{
		if(s>e || l>e || r<s)
		{
			return Long.MAX_VALUE;
		}
		if(lazy[node]!=0)
		{
			tree[node]+=lazy[node];
			if(s!=e)
			{
				lazy[(2*node)]+=lazy[node];
				lazy[(2*node)+1]+=lazy[node];
			}
			lazy[node]=0;
		}
		if(l<=s && r>=e)
		{
			return tree[node];
		}
		else
		{
			int mid=(s+e)/2;
			long l1=getMax(2*node,s,mid,l,r);
			long l2=getMax((2*node)+1,mid+1,e,l,r);
			return Math.min(l1,l2);
		}
	}
	
	public static void main(String args[]) throws Exception
	{
		int n=Integer.parseInt(br.readLine());
		a=new long[n];
		tree=new long[4*n];
		lazy=new long[4*n];
		String[] nums=br.readLine().split(" ");
		for(int i=0;i<n;i++)
		{
			a[i]=Integer.parseInt(nums[i]);
		}
		build(1,0,n-1);
		int q=Integer.parseInt(br.readLine());
		while(q>0)
		{
			String[] input=br.readLine().split(" ");
			if(input.length>2)
			{
				int l=Integer.parseInt(input[0]);
				int r=Integer.parseInt(input[1]);
				long k=Long.parseLong(input[2]);
				if(l>r)
				{
					updateRange(1,0,n-1,l,n-1,k);
					updateRange(1,0,n-1,0,r,k);
				}
				else
				{
					updateRange(1,0,n-1,l,r,k);
				}
			}
			else
			{
				int l=Integer.parseInt(input[0]);
				int r=Integer.parseInt(input[1]);
				if(l>r)
				{
					long l1=getMax(1,0,n-1,l,n-1);
					long l2=getMax(1,0,n-1,0,r);
					out.println(Math.min(l1,l2));
				}
				else
				{
					long ans=getMax(1,0,n-1,l,r);
					out.println(ans);
				}
			}
			q--;
		}
		out.close();
	}
}