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.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
 
public class Main {
	public static final double EPS = 1e-9;
	static PrintWriter pr = new PrintWriter(System.out);
 
 
 
	public static void main(String args[]) throws IOException {
		// FileReader in = new FileReader("C:/test.txt");
		// Scanner sc = new Scanner("C:/Users/AlSawa7/Desktop/input.txt");
		// PrintWriter pr = new PrintWriter(new
		// File("C:/Users/AlSawa7/Desktop/output.txt"));
		Scanner sc = new Scanner(System.in);
 
		// BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
		// ArrayList<Object> ar = new ArrayList<Object>();
		String [] s = sc.nextLine().split(" ");
		
		int n = Integer.parseInt(s[0]);
		int N=1;
		while(N<n) {
			N<<=1;
		}
		long nums[] = new long[n];
		int index=0;
		s = sc.nextLine().split(" ");
		
		for(int i=0; i<n;++i)
			nums[i] = Long.parseLong(s[i]);
		
		
 
		SegmentTree str = new SegmentTree(nums);
		int m = sc.nextInt();
		while(m-->0) {
			s = sc.nextLine().split(" ");
			if(s.length==2) {
				int l = Integer.parseInt(s[0])+1;
				int r = Integer.parseInt(s[1])+1;
				if(l>r) {
					pr.println(Math.min(str.Query(l, n), str.Query(1, r)));
				}else {
					pr.println(str.Query(l, r));
				}
			}else {
				int l = Integer.parseInt(s[0])+1;
				int r = Integer.parseInt(s[1])+1;
				long val = Long.parseLong(s[2]);
				if(l>r) {
					str.Update(l, n, val);
					str.Update(1, r, val);
				}else {
					str.Update(l, r, val);
				}
			}
		}
		pr.close();
	}
 
 
	static class SegmentTree{
		long stree[],lazy[];
		int N;
		SegmentTree(long a[]){
			int n = a.length;
			N=1;
			while(N<a.length)
				N<<=1;
			stree = new long[N<<1];
			lazy = new long[N<<1];
			int index=0;
			for(;index<n;++index)
				stree[index+N] = a[index];
			for(;index<N;++index)
				stree[index+N] = Long.MAX_VALUE;
			for(int i=N-1; i>0; --i)
				stree[i]= Math.min(stree[i<<1], stree[(i<<1)|1]);
		}
 
		long Query(int l, int r) {
			return query(1,1,N,l,r);
		}
		long query(int v, int b, int e,int l, int r) {
			if(r<b || e<l)
				return Long.MAX_VALUE;
			if(l<=b && e<=r)
				return stree[v];
			push(v);
			int mid = (b+e)>>1;
			long q1 = query(v<<1,b, mid, l, r);
			long q2 = query(v<<1 | 1,mid+1,e,l,r);
			return Math.min(q1, q2);
 
		}
 
		void Update(int l, int r, long val) {
			update(1,1,N,l,r,val);
		}
 
		void update(int v, int b, int e,int l, int r, long val) {
			if(r<b || e<l)
				return;
			if(l<=b && e<=r) {
				stree[v]+=val;
				lazy[v]+=val;
				return;
			}
			push(v);
			int mid = (b+e)>>1;
			update(v<<1,b,mid,l,r,val);
			update(v<<1 | 1,mid+1,e,l,r,val);
			stree[v] = Math.min(stree[v<<1], stree[v<<1 | 1]);
		}
 
		void push(int v) {
			if(lazy[v]==0)
				return;
			stree[v<<1]+=lazy[v];
			stree[v<<1 | 1]+=lazy[v];
			lazy[v<<1]+=lazy[v];
			lazy[v<<1 | 1]+=lazy[v];
			lazy[v]=0;
		}
	}
 
 
 
 
 
 
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
	}
 
	//
 
}
