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.math.*;
public class spoj {
    InputStream is;
    PrintWriter out; 
	
	static long segTree[];
	static long lazy[];
	static long arr[];
	
	public static void build(int pos,int l,int r)
	{
		if(l==r)
		{
			segTree[pos]=arr[l];
			return;
		}
		int m=(l+r)/2;
		build(2*pos+1,l,m);
		build(2*pos+2,m+1,r);
		segTree[pos]=Math.min(segTree[2*pos+1],segTree[2*pos+2]);
	}
	
	public static void update(int pos,int l,int r,int qs,int qe,long val)
	{
		if(l>r)
			return;
		
		if(lazy[pos]!=0)
		{
			segTree[pos]+=(lazy[pos]);
			if(l!=r)
			{
				lazy[2*pos+1]+=lazy[pos];
				lazy[2*pos+2]+=lazy[pos];
			}
			lazy[pos]=0;
		}
		if(qe<l || qs>r)
			return;
		
		if(qs<=l && r<=qe)
		{
			segTree[pos]+=(val);
			if(l!=r)
			{
				lazy[2*pos+1]+=val;
				lazy[2*pos+2]+=val;
			}
			
			return;
		}
		int m=(l+r)/2;
		update(2*pos+1,l,m,qs,qe,val);
		update(2*pos+2,m+1,r,qs,qe,val);
		
		segTree[pos]=Math.min(segTree[2*pos+1],segTree[2*pos+2]);
	}
	
	
	public static long query(int pos,int qs,int qe,int l,int r)
	{
		if(l>r)
			return Integer.MAX_VALUE;
		
		if(lazy[pos]!=0)
		{
			segTree[pos]+=(lazy[pos]);
			if(l!=r)
			{
				lazy[2*pos+1]+=lazy[pos];
				lazy[2*pos+2]+=lazy[pos];
			}
			lazy[pos]=0;
		}
		
		if(qs>r || qe<l)
			return Integer.MAX_VALUE;
		if(l>=qs && r<=qe)
		{
			return segTree[pos];
		}
		int m=(l+r)/2;
		return Math.min(query(2*pos+1,qs,qe,l,m),query(2*pos+2,qs,qe,m+1,r));
	}
	
    void solve()
    {
		int n=ni();
		segTree=new long[4*n];
		lazy=new long[4*n];
		arr=new long[n];
		for(int i=0;i<n;i++) arr[i]=nl();
		build(0,0,n-1);
		int ll=0,rr=0;
		long hit=0;
		int q=ni();
		
		while(q-->0)
		{
			String s[]=nLine().split(" ");
		//	System.out.println(s.length+" s");
			ll=Integer.parseInt(s[0]);
			rr=Integer.parseInt(s[1]);
			if(s.length==2)
			{
				if(ll<=rr)
				{
					out.println(query(0,ll,rr,0,n-1));
				}
				else
				{
					long v1=query(0,ll,n-1,0,n-1);
					long v2=query(0,0,rr,0,n-1);
					out.println(Math.min(v1,v2));
				}
			}
			else if(s.length==3)
			{
				hit=Long.parseLong(s[2]);
				if(ll<=rr)
				{
					update(0,0,n-1,ll,rr,hit);
				}
				else
				{
					update(0,0,n-1,ll,n-1,hit);
					update(0,0,n-1,0,rr,hit);
				}
				
			}
			
			//out.println(ll+" "+rr+" "+hit+" dah");
			
		}
		
		
		//out.println("Maa ki chut");
	
	}
	
	
	
	
	
	
 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 /*
	 import java.io.*;
import java.util.*;
import java.math.*;
public class nov {
    InputStream is;
    PrintWriter out;
	static long mod=(long)(1e9+7);
	public static void update(long segTree[],long lazy[],int pos,int s,int e,int qs,int qe,long val)
	{
	
		if(s>e)
			return;
		
		if(lazy[pos]!=0)
		{
			segTree[pos]+=(e-s+1)*(lazy[pos]);
			if(e!=s)
			{
				lazy[2*pos+1]+=lazy[pos];
				lazy[2*pos+2]+=lazy[pos];
			}
			lazy[pos]=0;
		}
		
		if(qs>e || qe<s)
			return;
		
		if(s>=qs && e<=qe)
		{
			lazy[pos]+=val;
			return;
		}
		int m=(e+s)/2;
		update(segTree,lazy,2*pos+1,s,m,qs,qe,val);
		update(segTree,lazy,2*pos+2,m+1,e,qs,qe,val);
		segTree[pos]=(segTree[2*pos+1]+ lazy[2*pos+1]*(m-s+1))+(segTree[2*pos+2]+ lazy[2*pos+2]*(e-m));
	}
	
	public static long query(long segTree[],long lazy[],int pos,int s,int e,int qs,int qe)
	{
		if(s>e)
			return 0l;
		if(lazy[pos]!=0)
		{
			segTree[pos]+=(e-s+1)*lazy[pos];
			if(e!=s)
			{
				lazy[2*pos+1]+=lazy[pos];
				lazy[2*pos+2]+=lazy[pos];
			}
			lazy[pos]=0;
		}
		
		if(qs>e || qe<s)
			return 0;
		if(s>=qs && e<=qe)
			return segTree[pos];
		
		int m=(s+e)/2;
		return query(segTree,lazy,2*pos+1,s,m,qs,qe)+query(segTree,lazy,2*pos+2,m+1,e,qs,qe);
	}
	
	void relax(long segTree[],long lazy[],int pos, int s, int e){
		if(s>e)
			return;
		
		if(lazy[pos]!=0)
		{
			segTree[pos]+=(e-s+1)*(lazy[pos]);
			if(e!=s)
			{
				lazy[2*pos+1]+=lazy[pos];
				lazy[2*pos+2]+=lazy[pos];
			}
			lazy[pos]=0;
		}
		int m= (e+s)/2;
		if(s==e)
			return;
		relax(segTree,lazy,2*pos+1,s,m);
		relax(segTree,lazy,2*pos+2,m+1,e);
	}
		
	
	void solve()
	{
		int t=ni();
		while(t-->0){
		int n=ni(),q=ni();
		long segTree[]=new long[4*n+5];
		long lazy[]=new long[4*n+5];
		int ss=0,ee=0;
		while(q-->0)
		{
			//int type=ni();
			ss=ni();ee=ni();
			/*if(type==1)
			{
				
				out.println(query(segTree,lazy,0,0,n-1,ss,ee));
				continue;
			}
			long val=nl();
			//	public static void update(long segTree[],long lazy[],int pos,int s,int e,int qs,int qe,long val)

			update(segTree,lazy,0,0,n-1,ss,ee,val);
		}
			relax(segTree, lazy,0,0,n-1);
			
			for(int i=0;i<15;i++)
			{
				out.print((segTree[i]+" "+ i + " \n"));
			}
	}
		
}
*/
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	
 
 
	  
	  
	  
	
    //---------- I/O Template ----------
    
    public static void main(String[] args) { new spoj().run(); }
    void run() { 
        is = System.in; 
        out = new PrintWriter(System.out);
        solve();
        out.flush();
    }
    
    byte input[] = new byte[1024];
    int len = 0, ptr = 0;
    
    int readByte() { 
        if(ptr >= len) { ptr = 0; 
            try { len = is.read(input); } 
            catch(IOException e) { throw new InputMismatchException(); } 
            if(len <= 0) { return -1; } 
        } return input[ptr++];
    }
    boolean isSpaceChar(int c) { return !( c >= 33 && c <= 126 ); }
    int skip() { 
        int b = readByte(); 
        while(b != -1 && isSpaceChar(b)) { b = readByte(); } 
        return b;
    }
    
    char nc() { return (char)skip(); }
    String ns() { 
        int b = skip(); 
        StringBuilder sb = new StringBuilder(); 
        while(!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); } 
        return sb.toString();
    }
    String nLine() { 
        int b = skip(); 
        StringBuilder sb = new StringBuilder(); 
        while( !(isSpaceChar(b) && b != ' ') ) { sb.appendCodePoint(b); b = readByte(); } 
        return sb.toString();
    }
    int ni() { 
        int n = 0, b = readByte(); 
        boolean minus = false; 
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); } 
        if(b == '-') { minus = true; b = readByte(); } 
        if(b == -1) { return -1; }  //no input 
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } 
        return minus ? -n : n;
    }
    long nl() { 
        long n = 0L;    int b = readByte(); 
        boolean minus = false; 
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); } 
        if(b == '-') { minus = true; b = readByte(); } 
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } 
        return minus ? -n : n;
    }
 
    double nd() { return Double.parseDouble(ns()); }
    float nf() { return Float.parseFloat(ns()); }
    int[] na(int n) { 
        int a[] = new int[n]; 
        for(int i = 0; i < n; i++) { a[i] = ni(); } 
        return a;
    }
    char[] ns(int n) { 
        char c[] = new char[n]; 
        int i, b = skip(); 
        for(i = 0; i < n; i++) { 
            if(isSpaceChar(b)) { break; } 
            c[i] = (char)b; b = readByte(); 
        } return i == n ? c : Arrays.copyOf(c,i);
    }
	void pa(int a[])
	{
		for(int i=0;i<a.length;i++)
		out.print(a[i]+" ");
		out.println();
	}
	
}