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.*;
import java.util.*;

public class C1{		
		
		private BufferedReader in;	
		private StringTokenizer st;
		private PrintWriter out;
		
		
		int []arr;
		long []tree;
		long []added;
		
		void build(int i, int st, int end ){
		
			if(st == end) {
				tree[i] = arr[st];
				return;
			}
			build(2*i,st,(st+end)>>1);
			build(2*i+1,1+((st+end)>>1),end);
			tree[i] = Math.min(tree[2*i],tree[2*i+1]);
			
		
	}
		
		
		void updateRange(int i ,int st,int end, int from, int to,int val){
			
			if(from>end || to<st) return;
			if(st>=from && end <= to){
				added[i] += val;
				tree[i] += (long)val;
				return;				
			}
			updateRange(2*i ,st, (st+end)>>1, from, to, val);
			updateRange(2*i+1 , 1+((st+end)>>1),end, from, to, val);
			
			tree[i] = Math.min(tree[2*i] , tree[2*i+1]) + added[i];
								
			
		}
		
		long query(int i, int st, int end, int from, int to){
			
			if(from > end || to < st) return Integer.MAX_VALUE;
			if(st>=from && end <= to) return tree[i] ;
			
			long ans = Math.min(query(2*i,st,(st+end)>>1,from, to) ,
					query(2*i+1,1+((st+end)>>1),end,from, to) );
			ans += added[i];			
			return ans;
		}
		
		void solve() throws IOException{
			
		
			int n = nextInt();
			arr = new int[n];
			tree = new long[4*n];
			added = new long[4*n];
			for (int i = 0; i < arr.length; i++) {
				arr[i] = nextInt();
			}
			build(1,0,n-1);
			int q = nextInt();
			while(q-->0){
				
				String[]tok = in.readLine().split("[ ]+");
				int from = Integer.parseInt(tok[0]);
				int to = Integer.parseInt(tok[1]);
				if(tok.length == 3){
					int val = Integer.parseInt(tok[2]);
					if(from <= to){
						updateRange(1, 0, n-1, from, to, val);
					}
					else{
						updateRange(1, 0, n-1, from, n-1, val);
						updateRange(1, 0, n-1, 0,to, val);
					}
				}
				else{
					if(from <= to){
						out.println(query(1, 0, n-1, from, to));
					}
					else{
						
						out.println(Math.min(query(1, 0, n-1, from, n-1), query(1, 0, n-1, 0, to)));
					}
				}
			}
			
		
					
		}
			

		C1() throws IOException {
			in = new BufferedReader(new InputStreamReader(System.in));	
			out = new PrintWriter(System.out);
			eat("");
			solve();	
			out.close();
		}

		private void eat(String str) {
			st = new StringTokenizer(str);
		}

		String next() throws IOException {
			while (!st.hasMoreTokens()) {
				String line = in.readLine();				
				if (line == null) {					
					return null;
				}
				eat(line);
			}
			return st.nextToken();
		}

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

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

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

		public static void main(String[] args) throws IOException {
			new C1();
		}


}