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.StringTokenizer;
 
public class lis {	
	static class stree{
		int n;
		long[]st;
		long[]lazy;
		stree(int[]in){
			st=new long[4*in.length];
			lazy=new long[4*in.length];
			n=in.length-1;
			build(1,1,n,in);
		}
		void build(int node,int l,int r,int[]in) {
			if(l==r) {
				st[node]=in[l];
			}
			else {
				int mid=(l+r)/2;
				build(2*node,l,mid,in);
				build(2*node+1,mid+1,r,in);
				st[node]=Math.min(st[2*node+1],st[2*node]);
			}
		}
		void updatecirc(int l,int r,int k) {
			if(l>r) {
				update(1,l,n,k,1,n);
				update(1,1,r,k,1,n);
			}
			else {
				update(1,l,r,k,1,n);
			}
		}
		void update(int node,int l,int r,int k,int curl,int curr) {
			if(l>curr || r<curl)return;
			else {
				if(curl>=l && curr<=r) {	
					st[node]+=k;
					lazy[node]+=k;
				}
				else {
					int mid=(curl+curr)/2;
					propagate(node, curl, mid, curr);
					update(2*node,l,r,k,curl,mid);
					update(2*node+1,l,r,k,mid+1,curr);
					st[node]=Math.min(st[2*node],st[2*node+1]);
				}
			}
		}
		void propagate(int node, int l, int mid, int r)		
		{
			lazy[node*2] += lazy[node];
			lazy[node*2 +1] += lazy[node];
			st[node*2] += lazy[node];		
			st[node*2+1] += lazy[node];		
			lazy[node] = 0;
		}
		long querycirc(int l,int r) {
			if(l>r) {
				return Math.min(query(1,1,n,l,n),query(1,1,n,1,r));
			}
			return query(1,1,n,l,r);
		}
		long query(int node, int l, int r, int i, int j)	{
			if(i>r || j <l)
				return (long)1e9;		
			if(l>= i && r <= j)
				return st[node];
			int mid =(l+r)/2;
			propagate(node, l, mid, r);
			long q1 = query(node<<1,l,mid,i,j);
			long q2 = query(node<<1|1,mid+1,r,i,j);
			return Math.min(q1,q2);	
					
		}
	}
	public static void main(String[] args) throws IOException {
		//MScanner sc = new MScanner(System.in);
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw=new PrintWriter(System.out);
		int n=Integer.parseInt(br.readLine());StringTokenizer st=new StringTokenizer(br.readLine());
		int[]in=new int[n+1];
		for(int i=1;i<in.length;i++) {
			in[i]=Integer.parseInt(st.nextToken());
		}
		stree z=new stree(in);
 
		int m=Integer.parseInt(br.readLine());
		for(int i=0;i<m;i++) {
			st=new StringTokenizer(br.readLine());
			int l=Integer.parseInt(st.nextToken())+1;
			int r=Integer.parseInt(st.nextToken())+1;
			if(!st.hasMoreTokens()) {
				pw.println(z.querycirc(l,r));
				
			}
			else {	
				int k=Integer.parseInt(st.nextToken());
				z.updatecirc(l,r,k);
			}
		}
 
		pw.close();
		pw.flush();
 
	}
 
	static class MScanner 
	{
	    StringTokenizer st;
	    BufferedReader br;
 
	    public MScanner(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();}
 
 
	}
}
 