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.*;
import java.lang.*;
public class CIRCULAR_RMQ {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		
		Scanner s = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = s.nextInt();
		
		long[] arr = new long[n];
		for(int i=0;i<n;i++) {
			arr[i] = s.nextLong();
		}
		
		int m = s.nextInt();
		s.nextLine();
		//System.out.println(m);
		int sz = (int)Math.pow(2, Math.ceil(Math.log(n)/Math.log(2)) + 1);
		
		long[] sg = new long[sz];
		long[] up = new long[sz];
		
		create(sg, 0, 0, n-1, arr);
		for(int i=0;i<m;i++) {
			String str = s.nextLine();
			String[] nums = str.split(" ");
			//System.out.println(nums.length);
			if(nums.length == 3) {
				int a = Integer.valueOf(nums[0]);
				int b = Integer.valueOf(nums[1]);
				int c = Integer.valueOf(nums[2]);
				
				if(a > b) {
					update(sg, up, 0, 0, n-1, a, n-1, c);
					update(sg, up, 0, 0, n-1, 0, b, c);
				}
				
				else {
					update(sg, up, 0, 0, n-1, a, b, c);
				}
			}
			
			else {
				int a = Integer.valueOf(nums[0]);
				int b = Integer.valueOf(nums[1]);
				
				if(a > b) {
					out.println(Math.min(getMin(sg, up, 0, 0, n-1, a, n-1), getMin(sg, up, 0, 0, n-1, 0, b)));
				}
				else {
					out.println(getMin(sg, up, 0, 0, n-1, a, b));
				}
			}
		}
		
		out.flush();

	}
	
	public static long getMin(long[] sg, long[] up, int index, int low, int high, int l, int r) {
		if(up[index] != 0) {
			sg[index] += up[index];
			if(low < high) {
				up[2*index + 1] += up[index];
				up[2*index + 2] += up[index];
			}
			
			up[index] = 0;
		}
		
		if(l > high || low > r)
			return Integer.MAX_VALUE;
		
		if(l <= low && r >= high) {
			return sg[index];
		}
		
		else {
			int mid = (low + high)/2;
			
			if(low == high) {
				return sg[index];
			}
			else {
				return Math.min(getMin(sg, up, 2*index + 1, low, mid, l, r), getMin(sg, up, 2*index + 2, mid + 1, high, l, r));
			}
			
		}
	}
	
	public static long create(long[] sg, int index, int low, int high, long[] arr) {
		if(low == high) {
			sg[index] = arr[low];
			return sg[index];
		}
		
		int mid = (low + high)/2;
		
		long v1 = create(sg, 2*index + 1, low, mid, arr);
		long v2 = create(sg, 2*index + 2, mid + 1, high, arr);
		
		sg[index] = Math.min(v1, v2);
		return sg[index];
	}

	public static void update(long[] sg, long[] up, int index, int low, int high, int l, int r, int val) {
		if(up[index] != 0) {
			sg[index] += up[index];
			if(low < high) {
				up[2*index + 1] += up[index];
				up[2*index + 2] += up[index];
			}
			up[index] = 0;
		}
		
		if(l > high || low > r)
			return;
		
		if(l <= low && r >= high) {
			sg[index] += val;
			if(low < high) {
				up[2*index + 1] += val;
				up[2*index + 2] += val;
			}
		}
		
		else {
			int mid = (low + high)/2;
			
			if(low == high) {
				sg[index] += val;
			}
			else {
				update(sg, up, 2*index + 1, low, mid, l, r, val);
				update(sg, up, 2*index + 2, mid + 1, high, l, r, val);
				
				sg[index] = Math.min(sg[2*index + 1], sg[2*index + 2]);
			}
			
		}
	}
	
	static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }

}

