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
//package seg_tree;

import java.util.*;
import java.io.*;

public class circular_rmq 
{
	int n, m;
	seg s;
	
	Scanner in;
	PrintWriter out;
	
	circular_rmq(Scanner in, PrintWriter out)
	{
		this.in = in;
		this.out = out;
		
		n = in.nextInt();
		s = new seg(n);
		
		for (int i = 0; i < n; i++)
			s.inc(i, i, in.nextInt());
		
		m = in.nextInt();
		in.nextLine();
		for (int i = 0; i < m; i++)
		{
			String[] line = in.nextLine().split(" ");
			int l = Integer.parseInt(line[0]);
			int r = Integer.parseInt(line[1]);
			
			if (line.length == 2)
			{
				long res = 0;
				if (l > r)
					res = Math.min(s.min(0, r), s.min(l, n-1));
				else 
					res = s.min(l, r);
				out.println(res);
			}
			
			else
			{
				long val = Long.parseLong(line[2]);
				if (l > r)
				{
					s.inc(0, r, val);
					s.inc(l, n-1, val);
				}
				else
					s.inc(l, r, val);
			}
		}
		
	}
	
	class seg 
	{
		int n;
		long[] lo, hi, min, del;
		
		seg(int nn)
		{
			n = nn;
			lo = new long[4*n+1];
			hi = new long[4*n+1];
			min = new long[4*n+1];
			del = new long[4*n+1];
			init(1, 0, n-1);
		}
		
		void inc(int l, int r, long val)
		{
			inc(1, l, r, val);
		}
		
		void inc(int i, int l, int r, long val)
		{
			if (r < lo[i] || hi[i] < l)
				return;
			if (l <= lo[i] && hi[i] <= r)
			{
				del[i] += val;
				return;
			}
			prop(i);
			inc(2*i, l, r, val); inc(2*i+1, l, r, val);
			update(i);
		}
		
		void prop(int i)
		{
			del[2*i] += del[i];
			del[2*i+1] += del[i];
			del[i] = 0;
		}
		
		void update(int i)
		{
			min[i] = Math.min(min[2*i]+del[2*i], min[2*i+1]+del[2*i+1]);
		}
		
		long min(int l, int r)
		{
			return min(1, l, r);
		}
		
		long min(int i, int l, int r)
		{
			if (r < lo[i] || hi[i] < l)
				return Long.MAX_VALUE;
			if (l <= lo[i] && hi[i] <= r)
				return min[i]+del[i];	
			prop(i);
			long L = min(2*i, l, r), R = min(2*i+1, l, r);
			update(i);
			return Math.min(L, R);
		}
		
		void init(int i, int l, int r)
		{	
			lo[i] = l; hi[i] = r;
			if (l == r)
				return;
			int m = (l+r)/2;
			
			init(2*i, l, m); init(2*i+1, m+1, r);
		}
	}

	
	public static void main(String[] args) 
	{
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		new circular_rmq(in ,out);
		out.close();
	}
}

/*

3
0 0 0
8
1 1 0
0 0 -1
0 1 0
2 0
2 2
0 1
0 0 1
1 1

*/
