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.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class C {

	static StreamTokenizer st;
	static long[]delta,tree, a;
	static long INF = (long) 1e18;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		int n = Integer.parseInt(br.readLine().trim());
		a = new long[n];
		String[]s = br.readLine().trim().split(" ");
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(s[i].trim());
		}
		int m = Integer.parseInt(br.readLine().trim());
		delta = new long[4*n];
		tree = new long[4*n];
		Build(1, 0, n-1);
		for (int i = 1; i <= m; i++) {
			s = br.readLine().trim().split(" ");
			int L = Integer.parseInt(s[0]), R = Integer.parseInt(s[1]);
			if (s.length==3) {
				int delta = Integer.parseInt(s[2]);
				if (L <= R)
					inc(1, 0, n-1, L, R, delta);
				else {
					inc(1, 0, n-1, 0, R, delta);
					inc(1, 0, n-1, L, n-1, delta);
				}
			}
			else {
				if (L <= R)
					out.println(rmq(1, 0, n-1, L, R, 0));
				else
					out.println(Math.min(rmq(1, 0, n-1, 0, R, 0), rmq(1, 0, n-1, L, n-1, 0)));
			}
		}
		out.close();
	}
	private static void Build(int v, int Tleft, int Tright) {
		if (Tleft==Tright)
			tree[v] = a[Tleft];
		else {
			int Tmiddle = (Tleft+Tright) >> 1;
			Build(2*v, Tleft, Tmiddle);
			Build(2*v+1, Tmiddle+1, Tright);
			tree[v] = Math.min(tree[2*v], tree[2*v+1]);
		}
	}
	private static long rmq(int v, int Aleft, int Aright, int Tleft, int Tright, long add) {
		if (Tleft > Tright)
			return INF;
		add += delta[v];
		if (Aleft==Tleft && Aright==Tright)
			return tree[v]+add;
		int tm = (Aleft+Aright) >> 1;
		return Math.min(rmq(2*v, Aleft, tm, Tleft, Math.min(tm, Tright), add), rmq(2*v+1, tm+1, Aright, Math.max(Tleft, tm+1), Tright, add));
	}
	private static void inc(int v, int tl, int tr, int L, int R, int dd) {
		if (L > R)
			return;
		if (tl==L && tr==R)
			delta[v] += dd;
		else {
			int tm = (tl+tr) >> 1;
			inc(2*v, tl, tm, L, Math.min(tm, R), dd);
			inc(2*v+1, tm+1, tr, Math.max(L, tm+1), R, dd);
			tree[v] = Math.min(tree[2*v]+delta[2*v], tree[2*v+1]+delta[2*v+1]);
		}
	}
}