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.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class CircularRMQ {

	public static int n, m;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		n = Integer.parseInt(br.readLine());
		
		lo = new long[4 * n + 1];
		hi = new long[4 * n + 1];
		delta = new long[4 * n + 1];
		
		tree = new long[4 * n + 1][2];
		
		init(1, 1, n);
		
		for (int i = 0; i <= 4 * n; i++) {
			tree[i][0] = tree[i][1] = delta[i] = 0;
		}
		
		StringTokenizer tokenizer = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < n; i++) {
			CircularRMQ.inc(1, i + 1, i + 1, Integer.parseInt(tokenizer.nextToken()));
		}
		
		m = Integer.parseInt(br.readLine());
		
		//System.out.println(Math.min(minquery(1, 3, 4), minquery(1, 1, 1)));
		
		for(int i = 0; i < m; i++) {
			tokenizer = new StringTokenizer(br.readLine());
			
			int left = Integer.parseInt(tokenizer.nextToken()) + 1;
			int right = Integer.parseInt(tokenizer.nextToken()) + 1;
			
			if(tokenizer.hasMoreTokens()) {
				//Increment
				int incrementAmount = Integer.parseInt(tokenizer.nextToken());
				
				if(right < left) {
					inc(1, left, n, incrementAmount);
					inc(1, 1, right, incrementAmount);
				}else{
					inc(1, left, right, incrementAmount);
				}
			}else{
				//Query
				if(right < left) {
					long k = minquery(1, left, n);
					long j = minquery(1, 1, right);
					
					bw.append("" + Math.min(k, j));
					bw.append('\n');
				}else{
					bw.append("" + minquery(1, left, right));
					bw.append('\n');
				}
			}
		}
		
		bw.close();
	}
	
	public static long[] lo;
	public static long[] hi;
	public static long[] delta;
	public static long[][] tree;

	public static void init(int i, int l, int r)
	{
		lo[i] = l;
		hi[i] = r;
		if (l == r)
		{
			return;
		}
		int m = (l + r) / 2;
		init(2 * i, l, m);
		init(2 * i + 1, m + 1, r);
	}

	public static void prop(int i)
	{
		delta[2 * i] += delta[i];
		delta[2 * i + 1] += delta[i];
		delta[i] = 0;
	}

	public static void update(int i) {
		tree[i][0] = Math.min(tree[2 * i][0] + delta[2 * i], tree[2 * i + 1][0] + delta[2 * i + 1]);
		tree[i][1] = tree[2 * i][1] + delta[2 * i] * (hi[2 * i] - lo[2 * i] + 1) + tree[2 * i + 1][1] + delta[2 * i + 1] * (hi[2 * i + 1] - lo[2 * i + 1] + 1);
	}

	public static long minquery(int i, int l, int r) {
		if (r < lo[i] || hi[i] < l) {
			return Integer.MAX_VALUE; //not in range
		}
		if (hi[i] <= r && lo[i] >= l) {
			return tree[i][0] + delta[i]; //completely in range
		}
		prop(i);
		long minLeft = minquery(2 * i, l, r);
		long minRight = minquery(2 * i + 1, l, r);
		update(i);
		return Math.min(minLeft, minRight);
	}
	public static long sumquery(int i, int l, int r) {
		if (r < lo[i] || hi[i] < l) {
			return 0; //not in range
		}
		if (hi[i] <= r && lo[i] >= l) {
			   // cout << tree[i][1] << " " << delta[i] << "\n";
		  return tree[i][1] + delta[i] * (hi[i] - lo[i] + 1); //completely in range
		}
		prop(i);
		long sumLeft = sumquery(2 * i, l, r);
		long sumRight = sumquery(2 * i + 1, l, r);
		update(i);
		return sumLeft + sumRight;
	}

	public static void inc(int i, int l, int r, int val) {
		if (r < lo[i] || l > hi[i]) { // segment i completely in range
			return;
		}
		
		if (l <= lo[i] && r >= hi[i]) {
			delta[i] += val;
			return;
		}
		
		prop(i);
		inc(2 * i, l, r, val);
		inc(2 * i + 1, l, r, val);
		update(i);
	}
	
}
