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.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class segmentTree {

	int [] tree;
	int []lazy;
	public segmentTree(int n){
		tree=new int[2*n];
		lazy=new int[2*n];
		Arrays.fill(tree, (int)1e9);
	}
	public void build(int cur, int l, int r , int []arr){
		lazy[cur]=0;
		if(l==r){
			tree[cur]=arr[l];
			return ;
		}
		int left=2*cur;
		int right=2*cur+1;
		int mid=(l+r)/2;
		build(left, l , mid ,arr); 
		build(right, mid+1,r, arr);
		tree[cur]=Math.min(tree[left], tree[right]);	
	}
	public void update(int cur, int l , int r, int idx, int val){
		if(idx<l||idx>r){
			return;
		}
		if(l==r&&l==idx){
			tree[cur]=val;
			return;
		}
		int left=2*cur;
		int right=2*cur+1;
		int mid=(l+r)/2;
		update(left, l , mid ,idx, val); 
		update(right, mid+1,r, idx, val);
		tree[cur]=Math.min(tree[left], tree[right]);
	}
	public void propagate(int cur, int l , int r, int left, int right){
		if(lazy[cur]!=0){
			tree[cur]+=lazy[cur];
			if(l!=r)
			{	lazy[left]+=lazy[cur];
			lazy[right]+=lazy[cur];}
			lazy[cur]=0;
		}
	}
	public void update(int cur, int l ,int r, int idxSt, int idxEnd, int val){
		int left=2*cur;
		int right=2*cur+1;
		propagate(cur, l , r, left, right);
		if(idxEnd<l||idxSt>r){
			return;
		}
		if(l>=idxSt&&r<=idxEnd)
		{
			tree[cur]+=val;
		if(left<tree.length)	lazy[left]+=val;
		if(right<tree.length)	lazy[right]+=val;
			return;
		}
		int mid=(l+r)/2;
		update(left, l , mid ,idxSt, idxEnd, val); 
		update(right, mid+1,r, idxSt,idxEnd, val);
		tree[cur]=Math.min(tree[left], tree[right]);
	}
	public int getMin(int cur, int l , int r, int x, int y){//x and y are the bounds of my range;
		int left=2*cur; 
		int right=2*cur+1;
		propagate(cur, l , r, left, right);
		if(x>r||y<l)
			return (int)1e9;
		if(l>=x&&r<=y){
			return tree[cur];
		}

		int mid=(l+r)/2;
		return Math.min(getMin(left, l , mid, x, y), getMin(right, mid+1, r, x, y));
		
	}
	public static void main (String[]args) throws NumberFormatException, IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n =Integer.parseInt(br.readLine());
		int an=(1<<(int)(Math.ceil((double)Math.log(n)/Math.log(2))));
		segmentTree t=new segmentTree(an);
		StringTokenizer st=new StringTokenizer(br.readLine());
		int [] arr=new int[an];
		Arrays.fill(arr, (int)1e9);
		for(int i =0 ; i <n; i++)arr[i]=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(br.readLine());
		t.build(1, 0, an-1, arr);
		while(m-->0){
			st=new StringTokenizer(br.readLine());
			int l=Integer.parseInt(st.nextToken());
			int r=Integer.parseInt(st.nextToken());
			if(st.hasMoreTokens()){
				int v=Integer.parseInt(st.nextToken());
				if(l>r){
					t.update(1, 0, an-1, 0, r, v);
					t.update(1, 0, an-1, l, n-1, v);
				}
				else
					t.update(1, 0, an-1, l, r,v);
			}
			else
			{
				int min;
				if(l>r){
					min=Math.min(t.getMin(1, 0,  an-1, 0, r), t.getMin(1, 0,  an-1, l, n-1));
				}
				else
					min=t.getMin(1, 0, an-1, l, r);
				System.out.println(min); 
			}
		}
	}
}
