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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class CircularRMQ {

	public static void main(String[] args) throws IOException {
		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();
		SegmentTree tree=new SegmentTree(a);
		int q=sc.nextInt();
		while(q-->0)
		{
			StringTokenizer st=new StringTokenizer (sc.nextLine());
			int left=Integer.parseInt(st.nextToken());
			int right=Integer.parseInt(st.nextToken());
			
			if(!st.hasMoreTokens())
			{
				
				if(right>=left)
				{
					pw.println(tree.query(0, n-1, left, right, 1));
				}
				else
				{
					
					pw.println(Math.min(tree.query(0, n-1, left, n-1, 1), tree.query(0, n-1, 0, right, 1)));
				}
			}
			else
			{
				if(right>=left)
					tree.update(0, n-1, left, right, 1, Integer.parseInt(st.nextToken()));
				else
				{
					int v=Integer.parseInt(st.nextToken());
					tree.update(0, n-1, left, n-1, 1, v);
					tree.update(0, n-1, 0, right, 1, v);
				}
			}
			
		}
		pw.close();

	}
	static class SegmentTree
	{
		long []min,lazy;
		int []a;
		SegmentTree(int []b)
		{
			a=b;
			int size=1;
			while(size<a.length)
				size*=2;
			min=new long [size*2];
			lazy=new long [size*2];
			build(0,a.length-1,1);
		}
		public  void build(int start,int end,int node)
		{
			if(start==end)
			{
				min[node]=a[start];
				
			}	
			
			else
			{
				int mid=(start+end)/2;
				build(start,mid,2*node);
				build(mid+1,end,2*node+1);
				min[node]=Math.min(min[2*node], min[2*node+1]);
			
			}
		}
		public  void propagate(int node)
		{
			min[2*node]+=lazy[node];
			min[2*node+1]+=lazy[node];
			
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
			lazy[node]=0;
		}
		public long query(int start,int end,int left,int right,int node)
		{
			if(end<left || start>right)
			{	
				return Long.MAX_VALUE;
			}	
			
			if(start>=left && end<=right)
			{	
				//System.out.println(start+" "+end);
				return min[node];
			}	
			
				propagate(node);
			int mid=(start+end)/2;
			return Math.min(query(start,mid,left,right,2*node),query(mid+1,end,left,right,2*node+1));
		}
		public void update(int start,int end,int left,int right,int node,int v)
		{
			if(end<left || start>right)
				return ;
			
			if(start>=left && end<=right)
			{
				min[node]+=v;
				//System.out.println(start+" "+end+" "+min[node]);
				lazy[node]+=v;
				return ;
			}
			
			{	
				propagate(node);
				int mid=(start+end)/2;
				update(start,mid,left,right,2*node,v);
				update(mid+1,end,left,right,2*node+1,v);
				min[node]=Math.min(min[2*node], min[2*node+1]);
			}
		}
	}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		public Scanner(InputStream s)
		{
			br=new BufferedReader(new InputStreamReader(s));
		}
		public String nextLine() throws IOException
		{
			return br.readLine();
		}
		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 double nextDouble() throws IOException
		{
			return Double.parseDouble(next());
		}
		public boolean ready() throws IOException
		{
			return br.ready();
		}
		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}
	}
}
