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 zizo {
	
	public static void main(String[]args) throws IOException {
		Scanner zizo=new Scanner(System.in);
		PrintWriter wr=new PrintWriter(System.out);
		
		int n = zizo.nextInt();
		int N=1;while(N<n) N<<=1 ;
		int[]a=new int[N+1];
		Arrays.fill(a,Integer.MAX_VALUE);
		for(int i = 1; i<=n ;i++)
			a[i] = zizo.nextInt();
		int m = zizo.nextInt();
		segmentTree st = new segmentTree(a);
		for(int i = 0;i < m;i++) {
			String[]s = zizo.nextLine().split(" ");
			int l = Integer.parseInt(s[0])+1;
			int r = Integer.parseInt(s[1])+1;
			if(s.length == 3) {
				int val = Integer.parseInt(s[2]);
				if(l>r) {
					st.update(l,n, val);
					st.update(1,r, val);
				}else st.update(l,r, val);
			}else {
				if(l>r) {
					wr.println(Math.min(st.query(l,n),st.query(1 , r)));
				}else wr.println(st.query(l,r));
			}
		}
		wr.close();
	}

}
class segmentTree{
	int N;
	int[] a,sTree,lazy;
	segmentTree(int[]a){
		this.a = a;
		N = a.length - 1;
		sTree = new int[N<<1];
		lazy = new int[N<<1];
		build(1,1,N);
	}
	void build(int v,int b,int e) {
		if(b == e)
			sTree[v] = a[b];
		else {
			int mid = b + e >> 1;
			build(v<<1,b,mid);
			build(v<<1|1,mid+1,e);
			sTree[v] = Math.min(sTree[v<<1] , sTree[v<<1|1]);
		}
	}
	void update(int i,int j,int val) {
		update(1,1,N,i,j,val);
	}
	void update(int v,int b,int e,int i,int j,int val) {
		if(i>e || j<b)
			return;
		if(b >= i && e <= j) {
			sTree[v]+=val;
			lazy[v]+=val;
		}else {
			int mid = b + e >>1;
			propagate(v,b,mid,e);
			update(v<<1,b,mid,i,j,val);
			update(v<<1|1,mid+1,e,i,j,val);
			sTree[v] = Math.min(sTree[v<<1] , sTree[v<<1|1]);
		}
	}
	void propagate(int v,int b,int mid,int e) {
		lazy[v<<1] += lazy[v];
		lazy[v<<1|1] += lazy[v];
		sTree[v<<1] += lazy[v];
		sTree[v<<1|1] += lazy[v];
		lazy[v]=0;
	}
	int query(int i, int j)
	{
		return query(1,1,N,i,j);
	}
	
	int query(int node, int b, int e, int i, int j)	// O(log n)
	{
		if(i>e || j <b)
			return Integer.MAX_VALUE;		
		if(b>= i && e <= j)
			return sTree[node];
		int mid = b + e >> 1;
		propagate(node, b, mid, e);
		int q1 = query(node<<1,b,mid,i,j);
		int q2 = query(node<<1|1,mid+1,e,i,j);
		return Math.min(q1,q2);	
	}
}

class Scanner 
{
	StringTokenizer st;
	BufferedReader br;

	public Scanner(InputStream s){br = new BufferedReader(new InputStreamReader(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 boolean ready() throws IOException {return br.ready();}

	public double nextDouble() throws IOException 
	{
		String x = next();
		StringBuilder sb = new StringBuilder("0");
		double res = 0, f = 1;
		boolean dec = false, neg = false;
		int start = 0;
		if(x.charAt(0) == '-')
		{
			neg = true;
			start++;
		}
		for(int i = start; i < x.length(); i++)
			if(x.charAt(i) == '.')
			{
				res = Long.parseLong(sb.toString());
				sb = new StringBuilder("0");
				dec = true;
			}
			else
			{
				sb.append(x.charAt(i));
				if(dec)
					f *= 10;
			}
		res += Long.parseLong(sb.toString()) / f;
		return res * (neg?-1:1);
	}

}