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

public class CircularRMQ {
	public static void main(String[] args)throws Throwable {
		Scanner sc=new Scanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		int n=sc.nextInt();
		N=1;
		while(N<n) N<<=1;
		a=new long [N+1];
		inf=(long)(1e17);
		Arrays.fill(a, inf);
		for(int i=1;i<=n;i++)
			a[i]=sc.nextInt();
		st=new long [N<<1];
		lazy=new long [N<<1];
		build();
		int m=sc.nextInt();
		while(m-->0){
			String s=sc.nextLine();
			String [] sa=s.split(" ");
			int x=Integer.parseInt(sa[0])+1;
			int y=Integer.parseInt(sa[1])+1;
			if(sa.length>2){
				int z=Integer.parseInt(sa[2]);
				if(x<=y)
					update_range(x, y, z);
				else{
					update_range(1, y, z);
					update_range(x, n, z);
				}
			}else{
				long ans=0;
				if(x<=y)
					ans=query(x, y);
				else
					ans=Math.min(query(1, y), query(x, n));
				pw.println(ans);
			}
		}
		
		
		pw.flush();
		pw.close();
	}
	static long inf;
	static int N;
	static long [] st;
	static long [] lazy;
	static long [] a;
	
	static void build(){
		build(1,N,1);
	}
	
	static long build(int s,int e,int p){
		if(s==e)
			return st[p]=a[s];
		else
			return st[p]=Math.min(build(s, (s+e)/2, 2*p),build((s+e)/2+1, e, 2*p+1));
	}
	
	static void update_range(int i,int j,int val){
		update(1,N,1,i,j,val);
	}
	
	static void update(int s,int e,int p,int i,int j,int val){
		if(j<s || i>e) //no intersection
			return;
		if(s>=i && e<=j){//total intersection
			st[p]+=val;
			lazy[p]+=val;
		}else{ //partial intersection
			propagate(s, e, p);
			update(s, (s+e)/2, 2*p, i, j, val);
			update((s+e)/2+1, e, 2*p+1, i, j, val);
			st[p]=Math.min(st[2*p],st[2*p+1]);
		}
	}
	
	static void propagate(int s,int e,int p){
		st[2*p]+=lazy[p];
		st[2*p+1]+=lazy[p];
		lazy[2*p]+=lazy[p];
		lazy[2*p+1]+=lazy[p];
		lazy[p]=0;
	}
	
	static long query(int i,int j){
		return query(1,N,1,i,j);
	}
	
	static long query(int s,int e,int p,int i,int j){
		if(j<s || i>e)
			return inf;
		if(s>=i && e<=j)
			return st[p];
		propagate(s, e, p);
		long q1=query(s, (s+e)/2, 2*p, i, j);
		long q2=query((s+e)/2+1, e, 2*p+1, i, j);
		return Math.min(q1,q2);
	}
	
	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 boolean ready() throws IOException {
			return br.ready();
		}

	}


}
