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.*;

public class Program
{
	private static StreamTokenizer in;
	private static PrintWriter out;

	public static int[] orderNoFromLeaf;

	
	private static void init() throws FileNotFoundException, IOException
	{
		Boolean oj = System.getProperty("ONLINE_JUDGE") != null;
		Reader r = oj ? new InputStreamReader(System.in) : new FileReader("Input.txt");
		Writer w = oj ? new OutputStreamWriter(System.out) : new FileWriter("Output.txt");
		
		in = new StreamTokenizer(new BufferedReader(r));
		out = new PrintWriter(w);
	}
	private static void close()
	{
		if (out != null)
		{
			out.flush();
			out = null;
		}
		if (in != null)
			in = null;
	}
	
	public static void main(String[] args) throws IOException
	{
		init();
		//print();
		solve();
		close();
	}
	@SuppressWarnings("unused")
	private static void print()
	{
	}
	private static void solve()	throws IOException
	{
		in.nextToken();
		int n = (int)in.nval;
		
		int[] ar = new int[n];
		
		for (int i = 0; i < n; i++)
		{
			in.nextToken();
			int a = (int)in.nval;
			ar[i] = a;
		}
		
		int sn = 1;
		while (sn < 2 * n) sn *= 2;

		Struct[] tree = new Struct[--sn];
		SegmentTree.constructTree(ar, tree, 0, n - 1, 0);
		
		in.nextToken();
		int m = (int)in.nval;
		in.eolIsSignificant(true);
		in.nextToken();
		
		for (int i = 0; i < m; i++)
		{
			in.nextToken();
			int l = (int)in.nval;
			in.nextToken();
			int r = (int)in.nval;
			in.nextToken();
			
			if (in.ttype == StreamTokenizer.TT_EOL || in.ttype == StreamTokenizer.TT_EOF)
			{
				if (l <= r)
				{
					int value = SegmentTree.query(tree, l, r, 0);
					out.println(value);
				}
				else
				{
					int value1 = SegmentTree.query(tree, l, n - 1, 0);
					int value2 = SegmentTree.query(tree, 0, r, 0);
					out.println(Math.min(value1, value2));
				}
			}
			else
			{
				int v = (int)in.nval;
				if (v != 0)
				{
					if (l <= r)
						SegmentTree.set(tree, l, r, 0, v);
					else
					{
						SegmentTree.set(tree, l, n - 1, 0, v);
						SegmentTree.set(tree, 0, r, 0, v);
					}
				}
				in.nextToken();
			}
		}
	}
}
class Struct
{
	public int value;
	public int l;
	public int r;
	public int inc;
	
	public Struct(int _l, int _r, int _value)
	{
		this.l = _l;
		this.r = _r;
		this.value = _value;
		this.inc = 0;
	}
}
class SegmentTree
{
	public static void constructTree(int[] base, Struct[] tree, int l, int r, int pos)
	{
		if (l == r)
		{
			tree[pos] = new Struct(l, r, base[l]);
			return;
		}
		int t = (l + r) / 2;
		constructTree(base, tree, l, t, pos * 2 + 1);
		constructTree(base, tree, t + 1, r, pos * 2 + 2);
		
		Struct sl = tree[2 * pos + 1];
		Struct sr = tree[2 * pos + 2];
		
		tree[pos] = new Struct(sl.l, sr.r, Math.min(sl.value, sr.value));
	}
	
	public static int query(Struct[] tree, int ql, int qr, int p)
	{
		Struct s = tree[p];
		if (s == null)
			return Integer.MAX_VALUE;
		
		if (ql <= s.l && qr >= s.r)
			return s.value;
		
		if (ql > s.r || qr < s.l)
			return Integer.MAX_VALUE;

		int min = Math.min(query(tree, ql, qr, p * 2 + 1), query(tree, ql, qr, p * 2 + 2));
		if (min == Integer.MAX_VALUE)
			return min;
		return min + s.inc;
	}
	
	public static void set(Struct[] tree, int l, int r, int pos, int v)
	{
		Struct s = tree[pos];
		
		if (s.l > r || s.r < l || s.value == Integer.MAX_VALUE)
			return;
		
		if (s.l >= l && s.r <= r)
		{
			s.inc += v;
			s.value += v;
			return;
		}
		
		set(tree, l, r, pos * 2 + 1, v);
		set(tree, l, r, pos * 2 + 2, v);
		int min = Math.min(tree[pos * 2 + 1].value, tree[pos * 2 + 2].value);
		if (min == Integer.MAX_VALUE)
			s.value = min;
		else
			s.value = min + s.inc;
	}
}