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.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

import static java.lang.Double.*;
import static java.math.BigInteger.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main implements Runnable {

	private void solve() throws IOException {
//		long start = System.currentTimeMillis();
//		if (false) {
//			createTest();
//		}
//		else {
			readData();
			processing();
//		}
	}
	
	private void createTest() {
		Random rnd = new Random(System.currentTimeMillis());
		int n = 7 + rnd.nextInt(3);
		println(n);
		int[] a = new int[n];
		for (int i = 0; i < n; ++i) {
			a[i] = rnd.nextInt(10) - 5;
			print(a[i]);
			print(" ");
		}
		println();
		int m = 27;
		println(m);
		for (int i = 0; i < m; ++i) {
			int l = rnd.nextInt(n);
			int r = rnd.nextInt(n);
			if (l > r) {
				int temp = r;
				r = l;
				l = temp;
			}
			print(l);
			print(" ");
			print(r);
			if (rnd.nextInt(3) == 1) {
				int value = rnd.nextInt(10)-5;
				print(" ");
				print(value);
			}
			println();
		}
	}

	private void processing() {
		
	}

	private void readData() throws IOException {
		tree = new TreeMaxInterval(true);
		int m = nextInt();
		for (int i = 0; i < m; ++i) {
			String[] tokens = reader.readLine().trim().split("[ ]+");
			int l = Integer.parseInt(tokens[0]);
			int r = Integer.parseInt(tokens[1]);
			if (tokens.length == 2) {
				if (l <= r) {
					println(tree.extractMinValue(l, r));
				}
				else {
					println(min(tree.extractMinValue(l, n-1), tree.extractMinValue(0, r)));
				}
			}
			else {
				if (l <= r) {
					tree.change(l, r, Integer.parseInt(tokens[2]));
				}
				else {
					long value = Integer.parseInt(tokens[2]);
					tree.change(l, n-1, value);
					tree.change(0, r, value);
				}
			}
		}
	}
	
//	private long[] a;
//	private long check;
	
	private TreeMaxInterval tree;
	private int n;
	
	private class TreeMaxInterval {
		
		public TreeMaxInterval(boolean fromInput) throws IOException {
			n = nextInt();
//			a = new long[n];
			init(n, 1000000000000L);
			for (int i = 0; i < n; ++i) {
				tree[start+i] = nextInt();
//				a[i] = tree[start+i];
			}
			for (int i = start-1; i > 0; --i) {
				tree[i] = min(tree[i<<1], tree[i<<1|1]);
			}
		}
		
		public TreeMaxInterval(int n, long initValue) {
			init(n, initValue);
		}
		
		public void init(int n, long initValue) {
			start = 1;
			while (start < n) {
				start <<= 1;
			}
			tree = new long[start<<1];
			change = new long[start<<1];
			fill(change, 0);
			fill(tree, initValue);
		}
		
		public void change(int l, int r, long value) {
//			for (int i = l; i <= r; ++i) {
//				a[i] += value;
//			}
			l += start;
			r += start;
			tree[l] += value;
			if (l != r) {
				tree[r] += value;
			}
			if (l/2 != r/2) {
				if (l%2 == 0) {
					tree[l+1] += value;
				}
				if (r%2 == 1) {
					tree[r-1] += value;
				}
				l >>= 1;
				r >>= 1;
				while (l/2 != r/2) {				
					tree[l] = min(tree[l<<1], tree[l<<1|1]) + change[l];
					tree[r] = min(tree[r<<1], tree[r<<1|1]) + change[r];
					if (l%2 == 0) {
						tree[l+1] += value;
						change[l+1] += value;
					}
					if (r%2 == 1) {
						tree[r-1] += value;
						change[r-1] += value;
					}
					l >>= 1;
					r >>= 1;
				}
				if (l+1 == r) {
					tree[l] = min(tree[l<<1], tree[l<<1|1]) + change[l];
					tree[r] = min(tree[r<<1], tree[r<<1|1]) + change[r];
					l >>= 1;
				}
			}
			else {
				l >>= 1;
			}
			while (l > 0) {
				tree[l] = min(tree[l<<1], tree[l<<1|1]) + change[l];
				l >>= 1;
			}
		}
		
		public long extractMinValue(int l, int r) {
//			long right = a[l];
//			for (int i = l+1; i <= r; ++i) {
//				right = min(right, a[i]);
//			}
//			check = right;
//			print(right);
//			print(" ");
			l += start; 
			r += start;
			long minLeft = tree[l];
			long minRight = tree[r];
			while (l/2 != r/2) {
				minLeft += change[l];
				if (l%2 == 0) {
					minLeft = min(minLeft, tree[l+1]);
				}
				minRight += change[r];
				if (r%2 == 1) {
					minRight = min(minRight, tree[r-1]);
				}
				l >>= 1;
				r >>= 1;
			}
			if (l+1 == r) {
				minLeft += change[l];
				minRight += change[r];
				l >>= 1;
			}
			long correction = 0;
			while (l > 0) {
				correction += change[l];
				l >>= 1;
			}
			return correction + min(minLeft, minRight);
		}
		
		private int start;
		public long[] tree;
		private long[] change;
	}

	public static void main(String[] args) throws InterruptedException {
		new Thread(null, new Runnable() {
			public void run() {
				new Main().run();
			}
		}, "1", 1 << 24).start();
	}

	// @Override
	public void run() {
		try {
			boolean onlineJudge = System.getProperty("ONLINE_JUDGE") != null;
			reader = onlineJudge ? new BufferedReader(new InputStreamReader(
					System.in)) : new BufferedReader(
					new FileReader("input.txt"));
			writer = onlineJudge ? new PrintWriter(new BufferedWriter(
					new OutputStreamWriter(System.out))) : new PrintWriter(
					new BufferedWriter(new FileWriter("output.txt")));
			Locale.setDefault(Locale.US);
			tokenizer = null;
			solve();
			writer.flush();
		} catch (Exception error) {
			error.printStackTrace();
			System.exit(1);
		}
	}

	private BufferedReader reader;
	private PrintWriter writer;
	private StringTokenizer tokenizer;

	private void println() {
		writer.println();
	}

	private void print(Object obj) {
		writer.print(obj);
	}

	private void println(Object obj) {
		writer.println(obj);
	}

	private void printf(String f, Object... d) {
		writer.printf(f, d);
	}

	private int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	private long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	private double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	private String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}
}