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

public class CiklicheskieRMQ {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer in;
	static PrintWriter out = new PrintWriter(System.out);
	
	public static String nextToken() throws IOException{
		while (in == null || !in.hasMoreTokens()){
			in = new StringTokenizer(br.readLine());
		}
		
		return in.nextToken();
	}
	
	public static int nextInt() throws IOException{
		return Integer.parseInt(nextToken());
	}
	
	public static double nextDouble() throws IOException{
		return Double.parseDouble(nextToken());
	}

	static long[] Tree;
	static long[] add;
	static int n;
	static int k;
	
	public static void push(int v){
		if (add[v] == 0){
			return;
		}
		
		if (v >= k){
			Tree[v] += add[v];
			add[v] = 0;
			return;
		}
		
		Tree[v] += add[v];
		add[2 * v] += add[v];
		add[2 * v + 1] += add[v];
		add[v] = 0;
	}
	
	public static void update(int v, int l, int r, int a, int b, int x){
		if (l > b || r < a)
			return;
		
		push(v);
		if (a <= l && r <= b){
			add[v] += x;
			return;
		}
		
		update(2 * v, l, (l + r) / 2, a, b, x);
		push(2 * v);
		update(2 * v + 1, (l + r) / 2 + 1, r, a, b, x);
		push(2 * v + 1);
		
		Tree[v] = Math.min(Tree[2 * v], Tree[2 * v + 1]);
		
		return;
	}
	
	public static long RMQ(int v, int l, int r, int a, int b){
		if (l > b || r < a)
			return Integer.MAX_VALUE;
		
		push(v);
		if (a <= l && r <= b){
			return Tree[v];
		}
		
		long z1 = RMQ(2 * v, l, (l + r) / 2, a, b);
		long z2 = RMQ(2 * v + 1, (l + r) / 2 + 1, r, a, b);
		
		return Math.min(z1, z2);
	}
	
	public static void add(int l, int r, int x){
		if (l <= r){
			update(1, 1, k, l, r, x);			
		}else{
			update(1, 1, k, 1, r, x);
			update(1, 1, k, l, n, x);
		}
	}
	
	public static long get(int l, int r){
		if (l <= r){
			return RMQ(1, 1, k, l, r);			
		}else{
			return Math.min(RMQ(1, 1, k, 1, r), RMQ(1, 1, k, l, n));
		}		
	}
	
	public static void main(String[] args) throws IOException{
		n = nextInt();
		
		k = 1;
		while (k < n)
			k *= 2;
		
		Tree = new long[2 * k];
		add = new long[2 * k];
		
		for (int i = 0; i < n; i++) {
			Tree[i + k] = nextInt();
		} 
		
		for (int i = k - 1; i > 0; i--) {
			Tree[i] = Math.min(Tree[2 * i], Tree[2 * i + 1]);
		}
		
		int m = nextInt();
		String S;
		for (int i = 0; i < m; i++) {
			S = br.readLine();
			
			in = new StringTokenizer(S);
			
			if (in.countTokens() == 2){
				out.println(get(nextInt() + 1, nextInt() + 1));
			}else{
				add(nextInt() + 1, nextInt() + 1, nextInt());
			}
		}		
		
		out.close();
	}
}
