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.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.TreeSet;

public class Solution {
	
	static InputReader in = new InputReader();
	static PrintWriter out = new PrintWriter(System.out);
	
	//static final int mod = 1000000000;
	static int n,q;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		n = in.nextInt();
		int[] A = in.nextArray(n);
		
		LST lst = new LST(A, "min");
		
		int q = in.nextInt();
		for(int lul=0; lul<q; lul++) {
			String line = in.nextLine();
			String[] arg = line.split(" ");
			if(arg.length==2) {
				int l = Integer.parseInt(arg[0]);
				int r = Integer.parseInt(arg[1]);
				if(l>r) {
					int val1 = lst.query(0, r);
					int val2 = lst.query(l,n-1);
					out.println(Math.min(val1, val2));
				} else {
					out.println(lst.query(l, r));
				}
			} else {
				int l = Integer.parseInt(arg[0]);
				int r = Integer.parseInt(arg[1]);
				int v = Integer.parseInt(arg[2]);
				if(l>r) {
					lst.increment(l, n-1, v);
					lst.increment(0, r, v);
				} else {
					lst.increment(l, r, v);
				}
				
			}
		}
		out.flush();
	}  
	
	static class LST{

		int[] tree;
		int[] lazy;
		int n;
		String type;
		public LST(int[] A, String type) {
			n = A.length;
			tree = new int[n<<2];
			lazy = new int[n<<2];
			this.type = type;
			buildTreeUtil(A, 0, 0, n-1);
		}
		
		private int op(int a, int b) {
			if(type.equalsIgnoreCase("min")) {
				return Math.min(a, b);
			}
			if(type.equalsIgnoreCase("max")) {
				return Math.max(a, b);
			}
			if(type.equalsIgnoreCase("sum")) {
				return a+b;
			}
			return 0;
		}
		/*
		 * node = current node
		 * s = start
		 * e = end
		 */
		private void buildTreeUtil(int[] a, int node, int s, int e) {
			if(e<s) return;
			if(e==s) {
				tree[node] = a[e];
				return;
			}
			
			int mid = (e+s)/2;
			buildTreeUtil(a, (node<<1) + 1, s, mid);
			buildTreeUtil(a, (node<<1) + 2, mid+1, e);
			tree[node] = op(tree[(node<<1) + 1], tree[(node<<1) + 2]);
		}
		
		public void increment(int l, int r, int v) {
			incrementUtil(0,l,r,0, n-1, v);
		}
		
		public int query(int l, int r) {
			return queryUtil(0, l, r, 0, n-1);
		}
		
		private int queryUtil(int node, int l, int r, int s, int e) {
			// TODO Auto-generated method stub
			
			if(lazy[node]!=0) {
				tree[node] += lazy[node];
				if(s!=e) {
					lazy[(node<<1)+1] += lazy[node];
					lazy[(node<<1)+2] += lazy[node];
				}
				
				lazy[node] = 0;
			}
			
			if(e<s || e<l || s>r) return Integer.MAX_VALUE;

			if(e<=r && s>=l) {
				return tree[node];
			}
			
			int mid = (s+e)/2;
			
			int n1 = queryUtil((node<<1)+1, l, r, s, mid);
			int n2 = queryUtil((node<<1)+2, l, r, mid+1, e);
			
			return op(n1,n2);
		}

		private void incrementUtil(int node, int l, int r, int s, int e, int v) {
			// TODO Auto-generated method stub
			if(lazy[node]!=0) {
				tree[node] += lazy[node];
				if(s!=e) {
					lazy[(node<<1)+1] += lazy[node];
					lazy[(node<<1)+2] += lazy[node];
				}
				lazy[node] = 0;
			}
			
			if(e<s || e<l || s>r) return;
			
			if(e<=r && s>=l) {
				tree[node] += v;
				if(e!=s) {
					lazy[(node<<1)+1] += v;
					lazy[(node<<1)+2] += v;
				}
				return;
			}
			
			int mid = (s+e)/2;
			
			incrementUtil((node<<1)+1, l, r, s, mid, v);
			incrementUtil((node<<1)+2, l, r, mid+1, e, v);
			
			tree[node] = op(tree[(node<<1) + 1], tree[(node<<1) + 2]);
		}
	}
	
	static class InputReader {
			private InputStream stream;
			private byte[] buf = new byte[1024];
			private int curChar;
			private int numChars;

			public InputReader(InputStream stream) {
				this.stream = stream;
			}
			
			public InputReader(String file){
				try {
					stream = new FileInputStream(file);
				} catch (FileNotFoundException e) {
					System.err.println(e);
				}
			}
			public InputReader() {
				this(System.in);
			}

			private int read() {
				if (numChars == -1)
					throw new InputMismatchException();
				if (curChar >= numChars) {
					curChar = 0;
					try {
						numChars = stream.read(buf);
					} catch (IOException e) {
						throw new InputMismatchException();
					}
					if (numChars <= 0)
						return -1;
				}
				return buf[curChar++];
			}

			public String nextLine() {
				int c = read();
				while (isSpaceChar(c))
					c = read();
				StringBuilder res = new StringBuilder();
				do {
					res.appendCodePoint(c);
					c = read();
				} while (!isEndOfLine(c));
				return res.toString();
			}

			public String nextString() {
				int c = read();
				while (isSpaceChar(c))
					c = read();
				StringBuilder res = new StringBuilder();
				do {
					res.appendCodePoint(c);
					c = read();
				} while (!isSpaceChar(c));
				return res.toString();
			}

			public long nextLong() {
				int c = read();
				while (isSpaceChar(c))
					c = read();
				int sgn = 1;
				if (c == '-') {
					sgn = -1;
					c = read();
				}
				long res = 0;
				do {
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					res *= 10;
					res += c - '0';
					c = read();
				} while (!isSpaceChar(c));
				return res * sgn;
			}

			public int nextInt() {
				int c = read();
				while (isSpaceChar(c))
					c = read();
				int sgn = 1;
				if (c == '-') {
					sgn = -1;
					c = read();
				}
				int res = 0;
				do {
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					res *= 10;
					res += c - '0';
					c = read();
				} while (!isSpaceChar(c));
				return res * sgn;
			}

			private boolean isSpaceChar(int c) {
				return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
			}

			private boolean isEndOfLine(int c) {
				return c == '\n' || c == '\r' || c == -1;
			}
			
			public int[] nextArray(int N){
				int[] a = new int[N];
				for(int i=0; i<N; i++)
					a[i] = nextInt();
				return a;
			}
			
			public int[][] nextMatrix(int n, int m)
			{
				int[][] matrix = new int[n][m];
				for (int i = 0; i < n; i++) {
					for(int j=0; j<m; j++){
						matrix[i][j] = nextInt();
					}
				}
				return matrix;
			}

		}
}