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 Main {

	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		PrintWriter pw = new PrintWriter(System.out);
		int n = Integer.parseInt(bf.readLine());
		int[] arr = new int[n];
		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		SegmantTreeWLazy s = new SegmantTreeWLazy(arr);
		int q = Integer.parseInt(bf.readLine());
		while (q-- > 0) {
			st = new StringTokenizer(bf.readLine());
			int l1 = Integer.parseInt(st.nextToken());
			int r1 = Integer.parseInt(st.nextToken());
			int l2 = 0, r2 = 0;
			if(r1 < l1) {
				r2 = r1;
				r1 = n - 1;
				if (st.hasMoreTokens()) {
					int c = Integer.parseInt(st.nextToken());
					s.updateRange(l1, r1, c);
					s.updateRange(l2, r2, c);
				}
				else {
					pw.println(Math.min(s.getRange(l1, r1), s.getRange(l2, r2)));
				}
			} else {
				if (st.hasMoreTokens())
					s.updateRange(l1, r1, Integer.parseInt(st.nextToken()));
				else
					pw.println(s.getRange(l1, r1));
			}
		}
		pw.close();
	}

	static class SegmantTreeWLazy {
		static long[] tree;
		static int[] arr;
		static long[] lazy;
		static int N;

		public SegmantTreeWLazy(int[] a) {
			arr = a;
			N = arr.length;
			int n = 1;
			while (n < N)
				n <<= 1;
			tree = new long[2 * n];
			lazy = new long[2 * n];
			build(1, 0, N - 1);
		}

		public static long f(long a, long b) {
			return Math.min(a, b);
		}

		public void doLazy(int node) {
			if (2 * node < tree.length) {
				tree[2 * node] += lazy[node];
				lazy[2 * node] += lazy[node];
			}
			if (2 * node + 1 < tree.length) {
				tree[2 * node + 1] += lazy[node];
				lazy[2 * node + 1] += lazy[node];
			}
			lazy[node] = 0;
		}

		public void updateRange(int left, int right, int val) {
			doUpdateRange(1, val, 0, N - 1, left, right);
		}

		public void doUpdateRange(int node, int val, int left, int right, int lq, int rq) {
			if (node >= tree.length || left > rq || right < lq)
				return;
			if (left >= lq && right <= rq) {
				tree[node] = (val + tree[node]);
				lazy[node] = (val + lazy[node]);
				return;
			}
			doLazy(node);
			int mid = left + (right - left) / 2;
			doUpdateRange(2 * node, val, left, mid, lq, rq);
			doUpdateRange(2 * node + 1, val, mid + 1, right, lq, rq);
			tree[node] = f(tree[2*node], tree[2*node + 1]);
		}

		public void update(int idx, long val) {
			doUpdate(1, val, 0, N - 1, idx);
		}

		public void doUpdate(int node, long val, int left, int right, int idx) {
			if (node >= tree.length)
				return;
			if (left == right) {
				tree[node] = val;
				return;
			}
			int mid = left + (right - left) / 2;
			if (mid < idx) {
				doUpdate(2 * node + 1, val, mid + 1, right, idx);
			} else {
				doUpdate(2 * node, val, left, mid, idx);
			}
			tree[node] = f(tree[2 * node], tree[2 * node + 1]);
		}

		public void build(int node, int left, int right) {
			if (left == right) {
				tree[node] = arr[left];
				return;
			}
			int mid = left + (right - left) / 2;
			build(2 * node, left, mid);
			build(2 * node + 1, mid + 1, right);
			tree[node] = f(tree[2 * node], tree[2 * node + 1]);
		}

		public long get(int node, int left, int right, int lq, int rq) {
			long ans = (long) 1e9; // dummy variable
			if (node >= tree.length || left > rq || right < lq)
				return ans;
			if (left >= lq && right <= rq && left <= right)
				return tree[node];
			doLazy(node);
			int mid = left + (right - left) / 2;
			if (left < lq || right > rq) {
				ans = f(ans, get(node * 2 + 1, mid + 1, right, lq, rq));
				ans = f(ans, get(node * 2, left, mid, lq, rq));
			}
			return ans;
		}

		public long getRange(int lq, int rq) {
			return get(1, 0, N - 1, lq, rq);
		}

	}

}
