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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] arr = new int[n];
		for (int i=0; i<n; i++) 
			arr[i] = sc.nextInt();

		RMQTree tree = new RMQTree(arr);

		int m = sc.nextInt(); sc.nextLine();

		StringBuilder sb = new StringBuilder();

		for (int i=0; i<m; i++) {
			String[] op = sc.nextLine().split("\\s+");
			
			int lf = Integer.parseInt(op[0]);
			int rg = Integer.parseInt(op[1]);
			if (op.length == 2) {
				if (lf > rg) {
					sb.append(min(tree.query(0, rg), tree.query(lf, n)) + "\n");
				} else {
					sb.append(tree.query(lf, rg) + "\n");
				}
			} else {
				int v = Integer.parseInt(op[2]);
				if (lf > rg) {
					tree.update(0, rg, v);
					tree.update(lf, n, v);
				} else {
					tree.update(lf, rg, v);
				}
			}
		}

		System.out.println(sb.toString());

		sc.close();
	}

	static class RMQTree {
		int n;
		int[] arr, st, lazy;

		RMQTree(int[] arr) {
			this.n = arr.length;
			this.arr = arr;
			this.st = new int[4*n];
			this.lazy = new int[4*n];
			build(1, 0, n-1);
		}

		int query(int i, int j) {
			return query(1, 0, n-1, i, j);
		}

		void update(int i, int j, int v) {
			lazyupdate(1, 0, n-1, i, j, v);
		}

		private void build(int p, int l, int r) {
			if (l==r) {
				st[p] = arr[l];
			} else {
				build(p<<1, l, (l+r)/2);
				build((p<<1)+1, ((l+r)/2)+1, r);
				st[p] = min(st[p<<1], st[(p<<1)+1]);
			}
		}

		private int query(int p, int l, int r, int i, int j) {
			if (i>r || j<l) 
				return Integer.MAX_VALUE;

			if (lazy[p] != 0) {
				st[p] += lazy[p];
				if (l!=r) {
					lazy[p<<1] += lazy[p];
					lazy[(p<<1)+1] += lazy[p];
				}
				lazy[p] = 0;
			}

			if (i<=l && r<=j) 
				return st[p];

			return min(query(p<<1, l, (l+r)/2, i, j),
			           query((p<<1)+1, ((l+r)/2)+1, r, i, j));
		}

		private void lazyupdate(int p, int l, int r, int i, int j, int v) {
			if (lazy[p] != 0) {
				st[p] += lazy[p];
				if (l!=r) {
					lazy[p<<1] += lazy[p];
					lazy[(p<<1)+1] += lazy[p];
				}
				lazy[p] = 0;
			}

			if (i>r || j<l) 
				return;

			if (i<=l && r<=j) {
				st[p] += v;
				if (l!=r) {
					lazy[p<<1] += v;
					lazy[(p<<1)+1] += v;
				}
				return;
			}

			lazyupdate(p<<1, l, (l+r)/2, i, j, v);
			lazyupdate((p<<1)+1, ((l+r)/2)+1, r, i, j, v);
			st[p] = min(st[p<<1], st[(p<<1)+1]);
		}

	}

}