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.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class CCircularRMQ {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FastScanner input = new FastScanner();
		int n = input.nextInt();
		int[] arr = new int[n];
		for (int a = 0; a < n; a++) {
			arr[a] = input.nextInt();
		}
		MinSegmentTree tree = new MinSegmentTree(0, n-1);
		for (int a = 0; a < n; a++) {
			tree.setValue(a, arr[a]);
		}
		int r = input.nextInt();
		StringBuilder output =new StringBuilder();
		for (int a = 0; a < r; a++) {
			String in = input.readNextLine();
			int countSpace  = 0;
			for(int b = 0; b <  in.length(); b++){
				countSpace += (in.charAt(b) == ' ')?1:0;
			}
			StringTokenizer st = new StringTokenizer(in);
			String[] inStr = new String[countSpace+1];
			int   count = 0;
			while(st.hasMoreTokens()){
				inStr[count] = st.nextToken();
				count++;
			}
			if(inStr.length == 3){
				int left = Integer.parseInt(inStr[0]);
				int right = Integer.parseInt(inStr[1]);
				int v = Integer.parseInt(inStr[2]);
				if(left > right){
					tree.rangeUpdate(0, right, v);
					tree.rangeUpdate(left, n-1, v);
				}
				else{
					tree.rangeUpdate(left, right, v);					
				}
			}
			else{
				int left = Integer.parseInt(inStr[0]);
				int right = Integer.parseInt(inStr[1]);
				if(left > right){
					output.append(Math.min(tree.rangeCheck(0, right), tree.rangeCheck(left, n-1)) + "\n");
				}
				else{
					output.append(tree.rangeCheck(left, right)+"\n");					
				}
			}
		}
		System.out.print(output);
	}

	public static class MinSegmentTree {
		int left;
		int right;
		MinSegmentTree leftTree;
		MinSegmentTree rightTree;
		long value;
		long min;

		public MinSegmentTree(int lSize, int rSize) {
			left = lSize;
			right = rSize;
			if (left != right) {
				leftTree = new MinSegmentTree(lSize, lSize + (rSize - lSize)
						/ 2);
				rightTree = new MinSegmentTree(lSize + (rSize - lSize) / 2 + 1,
						rSize);
			}
			value = 0;
			min = Integer.MAX_VALUE;
		}

		public void setValue(int index, int value2) {
			if (left <= index && right >= index) {
				if (left == right) {
					value = value2;
					min = value;
				} else {
					leftTree.setValue(index, value2);
					rightTree.setValue(index, value2);
					min = Math.min(leftTree.min, rightTree.min) + value;
				}
			}
		}
		public long rangeCheck(int  leftVal, int rightVal){
			if (left > rightVal || right < leftVal) {
				return Integer.MAX_VALUE;
			}
			if (leftVal <= left && rightVal >= right) {
				return min;
			}
			return value + Math.min(leftTree.rangeCheck(leftVal, rightVal), rightTree.rangeCheck(leftVal, rightVal));
		}
		public void rangeUpdate(int leftVal, int rightVal, int quant) {
			if (left > rightVal || right < leftVal) {
				return;
			}
			if (leftVal <= left && rightVal >= right) {
				value += quant;
				min += quant;
				return;
			}
			leftTree.rangeUpdate(leftVal, rightVal, quant);
			rightTree.rangeUpdate(leftVal, rightVal, quant);
			min = Math.min(leftTree.min, rightTree.min) + value;

		}

		public String toString() {
			if (left == right) {
				return left + " " + right + " " + min + "\n";
			}
			return left + " " + right + " " + min +  "\n"
					+ leftTree + "" + rightTree;
		}

	}

	public static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(Reader in) {
			br = new BufferedReader(in);
		}

		public FastScanner() {
			this(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		// Slightly different from java.util.Scanner.nextLine(),
		// which returns any remaining characters in current line,
		// if any.
		String readNextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}
