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.BufferedInputStream;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.PrintWriter;


public class C52 {
	
	final long oo = (long) 1e18;
	
	class Node {
		int l, r;
		long value, lazy;
		
		Node left, right;
		
		Node(int ll, int rr, int[] a) {
			l = ll; r = rr;
			if(l == r) {
				value = a[l];
				return;
			}
			int mid = ll + rr >> 1;
			left = new Node(ll, mid, a);
			right = new Node(mid + 1, rr, a);
			value = Math.min(left.value, right.value);
		}
		
		void prop() {
			value += lazy;
			left.lazy += lazy;
			right.lazy += lazy;
			lazy = 0;
		}
		
		long get() {
			return value + lazy;
		}
		
		void add(int ll, int rr, long delta) {
			if(rr < l || ll > r) return;
			if(ll <= l && r <= rr) {
				lazy += delta;
				return;
			}
			prop();
			left.add(ll, rr, delta);
			right.add(ll, rr, delta);
			value = Math.min(left.get(), right.get());
		}
		
		long query(int ll, int rr) {
			if(rr < l || ll > r) return oo;
			if(ll <= l && r <= rr) return get();
			prop();
			return Math.min(left.query(ll, rr), right.query(ll, rr));
		}
	}
	
	public void solve(BufferedReader in, PrintWriter out) throws Exception {
		int n = Integer.parseInt(in.readLine());
		int[] a = new int[n];
		String[] sa = in.readLine().split(" ");
		for(int i = 0; i < n; ++i) a[i] = Integer.parseInt(sa[i]);
		Node st = new Node(0, n - 1, a);
		int m = Integer.parseInt(in.readLine());
		while(m-->0) {
			String[] line = in.readLine().split(" ");
			int l = Integer.parseInt(line[0]), r = Integer.parseInt(line[1]);
			if(line.length == 3) {
				int val = Integer.parseInt(line[2]);
				if(l <= r) st.add(l, r, val);
				else {
					st.add(l, n - 1, val);
					st.add(0, r, val);
				}
			} else {
				long ans = oo;
				if(l <= r) ans = st.query(l, r);
				else {
					ans = Math.min(ans, st.query(l, n - 1));
					ans = Math.min(ans, st.query(0, r));
				}
				out.println(ans);
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		new C52().solve(in, out);
		in.close();
		out.close();
	}
	
	static class JS{
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;
		
		public JS() {
			in = new BufferedInputStream(System.in, BS);
		}
		
		public JS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}
		
		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}				
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}
		
		public int nextInt() {
			return (int)nextLong();
		}
		
		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}
		
		public double nextDouble() {
		    while(c!='.'&&c!='-'&&(c <'0' || c>'9')) c = nextChar();
		    boolean neg = c=='-';
		    if(neg)c=nextChar();
		    boolean fl = c=='.';
		    double cur = nextLong();
		    if(fl) return neg ? -cur/num : cur/num;
		    if(c == '.') {
			double next = nextLong();
			return neg ? -cur-next/num : cur+next/num;
		    }
		    else return neg ? -cur : cur;
		}
		
		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}
		
		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
	}
}
