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.PrintWriter;
import java.util.*;

//for testing segtree
public class rmq {
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		PrintWriter out=new PrintWriter(System.out);
		int n=scan.nextInt();
		node root=new node(1,n);
		for(int i=1;i<=n;i++) root.add(i,i,scan.nextInt());
		
		int q=scan.nextInt();
		scan.nextLine();
		for(int i=0;i<q;i++) {
			String[] in=scan.nextLine().split(" ");
			int u=Integer.parseInt(in[0])+1, v=Integer.parseInt(in[1])+1;
			if(in.length==3) {
				int delta=Integer.parseInt(in[2]);
				if(u>v) {
					root.add(u,n,delta);
					root.add(1,v,delta);
				}
				else {
					root.add(u,v,delta);
				}
			}
			else {
				long res=Long.MAX_VALUE;
				if(u>v) {
					res=Math.min(res,root.min(u,n));
					res=Math.min(res,root.min(1,v));
				}
				else {
					res=Math.min(res,root.min(u,v));
				}
				out.println(res);
			}
		}
		out.close();
	}
	static class node {
		node l=null,r=null;
		int lo,hi;
		long delta,min;
		
		node(int lo, int hi) {
			this.lo=lo;
			this.hi=hi;
			delta=0L;
			min=0L;
			if(lo!=hi) {
				int m=(lo+hi)/2;
				l=new node(lo,m);
				r=new node(m+1,hi);
			}
		}
		
		void add(int nlo, int nhi, int add) {
			if(nlo<=lo&&hi<=nhi) {
				//covers entire interval
				delta+=add;
				return;
			}
			if(lo>nhi||hi<nlo) {
				//covers nothing
				return;
			}
			push();
			l.add(nlo,nhi,add);
			r.add(nlo,nhi,add);
			update();		
		}
		
		long min(int nlo, int nhi) {
			if(nlo<=lo&&hi<=nhi) {
				//covers entire interval
				return min+delta;
			}
			if(lo>nhi||hi<nlo) {
				//covers nothing
				return Long.MAX_VALUE;
			}
			push();
			long left=l.min(nlo,nhi);
			long right=r.min(nlo,nhi);
			update();
			
			return Math.min(left,right);
		}
		void update() {
			min=Math.min(l.min+l.delta,r.min+r.delta);
		}
		void push() {
			l.delta+=delta;
			r.delta+=delta;
			delta=0;
		}
	}
}
/*
5
0 0 0 0 0
3
4 4 5
0 3 5
1 1

5
0 0 0 0 0
2
0 4 5
1 1

5
0 0 0 0 0
2
4 3 5
1 1

4
0 0 0 0
2
3 2 5
1 1
*/