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.util.*;
import java.io.*;
public class CircularRMQ {
	public static void main(String[] args) throws IOException {
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = in.nextInt();
		SegmentTree st = new SegmentTree(n);
		for(int i = 0; i < n; i++)
		{
			st.inc(i, i, in.nextInt());
		}
		
		int m = in.nextInt();
		for(int i = 0; i < m; i++)
		{
			String[] test = in.nextLine().split(" ");
			if(test.length == 3)
			{
				int l = Integer.parseInt(test[0]);
				int r = Integer.parseInt(test[1]);
				int v = Integer.parseInt(test[2]);
				if(l > r)
				{
					st.inc(0, r, v);
					st.inc(l, n-1, v);
				}
				else
					st.inc(l, r, v);
				
			}
			if(test.length==2)
			{
				int l = Integer.parseInt(test[0]);
				int r = Integer.parseInt(test[1]);
				if(l > r)
				{
					long temp = Math.min(st.minQuery(0, r), st.minQuery(l, n-1));
					out.println(temp);
				}
				else
				{
					long temp = st.minQuery(l, r);
					out.println(temp);
				}
			}
		}
		out.close();
	}

}
class FastScanner
{
	BufferedReader br;
	StringTokenizer st;
	public FastScanner(InputStream in)
	{
		br = new BufferedReader(new InputStreamReader(in));
		st = new StringTokenizer("");
	}
	public String next() throws IOException
	{
		while(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}
	public String nextLine() throws IOException
	{
		st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		while(st.hasMoreTokens()) sb.append(st.nextToken()+" ");
		return sb.toString();
	}
	public int nextInt() throws IOException
	{
		return Integer.parseInt(next());
	}
}
class SegmentTree
{
	long[] lo, hi, delta, min;
	
	SegmentTree(int n)
	{
		lo = new long[n*4+1];
		hi = new long[n*4+1];
		delta = new long[n*4+1];
		min = new long[n*4+1];
		init(0, n-1, 1);
	}
	void init(int l, int r, int c)
	{
		if(l==r)
		{
			lo[c] = l;
			hi[c] = r;
			return;
		}
		lo[c] = l;
		hi[c] = r;
		init(l, (l+r)/2, c*2);
		init((l+r)/2+1, r, c*2+1);
	}
	
	void inc(int l, int r, long val)
	{
		inc(l, r, val, 1);
	}
	
	void inc(int l, int r, long val, int c)
	{
		if(lo[c] >= l && hi[c] <= r)
		{
			delta[c] += val;
			min[c] += val;
			return;
		}
		if(hi[c] < l || lo[c] > r)
			return;
		
		prop(c);
		inc(l,r,val,c*2);
		inc(l,r,val,c*2+1);
		min[c] = Math.min(min[c*2], min[c*2+1]);
		
	}
	
	void prop(int c)
	{
		delta[c*2]+= delta[c];
		delta[c*2+1]+= delta[c];
		min[c*2]+= delta[c];
		min[c*2+1]+= delta[c];
		delta[c] = 0;
	}
	
	long minQuery(int l, int r)
	{
		return minQuery(l, r, 1);
	}
	long minQuery(int l, int r, int c)
	{
		if(lo[c] >= l && hi[c] <= r)
		{
			return min[c];
		}
		if(lo[c] > r || hi[c] < l)
			return Long.MAX_VALUE;
		
		prop(c);
		return Math.min(minQuery(l,r,c*2), minQuery(l,r,c*2+1));
	}
}
/*
4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1


*/
