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 C {
	public static class segtree {
		long[] t;
		long[] lazy;
		int n;
		
		void update(int l, int r, long a) {update(1, 0, n-1, l, r, a);}
		long query(int l, int r) {return query(1,0,n-1,l,r);}
		public segtree(int len) {
			n=len;
			t = new long[n*4];
			lazy = new long[n*4];
		}
		
		void push(int v) {
			if (lazy[v] == 0) return;
			// t[v*2] = t[v*2+1] = t[v];
			// lazy[v*2] = lazy[v*2+1] = lazy[v];
			t[v*2] += lazy[v];
			lazy[v*2] += lazy[v];
			t[v*2+1] += lazy[v];
			lazy[v*2+1] += lazy[v];
			lazy[v] = 0;
		}
		
		void update(int v, int tl, int tr, int l, int r, long new_val) {
			if (l > r) return;
			if (l == tl && r == tr) {
				t[v] += new_val;
				lazy[v] += new_val;
			}
			else {
				push(v);
				int tm = (tl+tr)/2;
				update(v*2, tl, tm, l, Integer.min(r, tm), new_val);
				update(v*2+1, tm+1,tr, Integer.max(l, tm+1),r, new_val);
				t[v] = Long.min(t[v*2] , t[v*2+1]);
			}
		}
		
		long query(int v, int tl, int tr, int l, int r) {
			if (l > r) return Long.MAX_VALUE;
			if (l == tl && tr == r) return t[v];
			push(v);
			int tm = (tl+tr)/2;
			return Long.min(query(v*2, tl, tm, l, Integer.min(r, tm)) , query(v*2+1, tm+1, tr, Integer.max(l, tm+1), r));
		}
	}

	//public static Reader sc = new Reader();
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {
		//BufferedReader br = new BufferedReader(new FileReader("input.in"));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		segtree s  = new segtree(n);
		for (int i = 0; i < n; i++) {
			s.update(i, i, Integer.parseInt(st.nextToken()));
		}
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			int lf = Integer.parseInt(st.nextToken());
			int rg = Integer.parseInt(st.nextToken());
			if (st.hasMoreElements()) {
				long v = Long.parseLong(st.nextToken());
				if (lf <= rg) {
					s.update(lf, rg, v);
				}
				else {
					s.update(lf,n-1,v);
					s.update(0, rg, v);
				}
			}
			else {
				long ans;
				if (lf <= rg) {
					ans = s.query(lf, rg);
				}
				else {
					ans=s.query(lf,n-1);
					ans=Long.min(ans,s.query(0, rg));
				}
				out.println(ans);
			}
			
		}

		out.close();
	}

	static long ceil(long a, long b) {
		return (a + b - 1) / b;
	}

	static long powMod(long base, long exp, long mod) {
		if (base == 0 || base == 1)
			return base;
		if (exp == 0)
			return 1;
		if (exp == 1)
			return base % mod;
		long R = powMod(base, exp / 2, mod) % mod;
		R *= R;
		R %= mod;
		if ((exp & 1) == 1) {
			return base * R % mod;
		} else
			return R % mod;
	}

	static long pow(long base, long exp) {
		if (base == 0 || base == 1)
			return base;
		if (exp == 0)
			return 1;
		if (exp == 1)
			return base;
		long R = pow(base, exp / 2);
		if ((exp & 1) == 1) {
			return R * R * base;
		} else
			return R * R;
	}

	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[64]; // line length 
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n') {
					break;
				}
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, Integer.max(cnt - 1, 0));
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

	public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
}
