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 Main {
	
	private void solve() throws Exception {
		int n = nextInt();
		a = new long[n];
		for(int i = 0; i < n; i++) a[i] = nextLong();
		
		min = new long[4*n+1];
		lazy = new long[4*n+1];
		updated = new boolean[4*n+1];
		build(0,0,n-1);
		
		
		
		int m = nextInt();
		for(int mm = 1; mm <= m; mm++) {
			String line = nextLine();
			String[] split = line.split(" ");
			int l = Integer.parseInt(split[0]);
			int r = Integer.parseInt(split[1]);
			if(split.length > 2) {
				int value = Integer.parseInt(split[2]);
				if(l <= r) {
					updateRange(0, 0, n-1, l, r, value);
				} else {
					updateRange(0, 0, n-1, l, n-1, value);
					updateRange(0, 0, n-1, 0, r, value);
				}
			} else {
				if(l <= r) {
					out.println(query(0, 0, n-1, l, r));
				} else {
					out.println(Math.min(query(0, 0, n-1, l, n-1), query(0, 0, n-1, 0, r)));
				}
			}
		}
	}
	
	long[] a;
	long[] min;
	long[] lazy;
	boolean[] updated;
	
	void build(int node, int start, int end) {
		if(start == end) {
			min[node] = a[start];
		} else {
			int mid = (start+end)/2;
			build(2*node+1, start, mid);
			build(2*node+2, mid+1, end);
			min[node] = Math.min(min[2*node+1], min[2*node+2]);
		}
	}
	
	long query(int node, int start, int end, int l, int r) {
		if(end < l || start > r) return 1L<<60;

		lazyPropagate(node, start, end);
		
		if(l <= start && end <= r) return min[node];
		
		int mid = (start+end)/2;
		long min_l = query(2*node+1, start, mid, l, r);
		long min_r = query(2*node+2, mid+1, end, l, r);
		return Math.min(min_l, min_r);
	}
	
	void updateRange(int node, int start, int end, int l, int r, long value) {
		lazyPropagate(node, start, end);
		
		if(end < l || start > r) return;
		
		if(l <= start && end <= r) {
			lazyUpdate(node, value);
			lazyPropagate(node, start, end);			
			return;
		}
		
		int mid = (start+end)/2;
		updateRange(2*node+1, start, mid, l, r, value);
		updateRange(2*node+2, mid+1, end, l, r, value);
		min[node] = Math.min(min[2*node+1], min[2*node+2]);
	}
	
	void lazyPropagate(int node, int start, int end) {
		if(!updated[node]) {
			min[node] = min[node]+lazy[node];			
			if(start != end) {
				lazyUpdate(2*node+1, lazy[node]);
				lazyUpdate(2*node+2, lazy[node]);
			}
			lazyReset(node);
		}
	}
	
	void lazyUpdate(int node, long value) {
		updated[node] = false;
		lazy[node] = lazy[node]+value;
	}
	
	void lazyReset(int node) {
		updated[node] = true;
		lazy[node] = 0;
	}
	
	
	
	
	public static void main(String[] args) {
		new Thread(null, new Runnable() {
            public void run() {
                new Main().run();
            }
        }, "1", 1 << 27).start();
	}

	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer tokenizer;

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

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

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

	private float nextFloat() throws IOException {
		return Float.parseFloat(nextToken());
	}

	private String nextLine() throws IOException {
		return new String(in.readLine());
	}

	private String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(in.readLine());
		}
		return tokenizer.nextToken();
	}


}
