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>();
     
    		int n = sc.nextInt();
    		int N=1;
    		while(N<n) {
    			N<<=1;
    		}
    		int nums[] = new int[n];
    		int index=0;
    		for(int i=0; i<n;++i)
    			nums[i] = sc.nextInt();
     
     
    		SegmentTree str = new SegmentTree(nums);
    		int m = sc.nextInt();
    		while(m-->0) {
    			StringTokenizer st = new StringTokenizer(sc.nextLine());
    			if(st.countTokens()==2) {
    				int l = Integer.parseInt(st.nextToken())+1;
    				int r = Integer.parseInt(st.nextToken())+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(st.nextToken())+1;
    				int r = Integer.parseInt(st.nextToken())+1;
    				long val = Long.parseLong(st.nextToken());
    				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(int 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();
    		}
     
    	}
     
    	//
     
    }