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
// package CodeForces;

import java.io.*;
import java.util.*;

public class Problem_52C {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter pw = new PrintWriter(System.out);
		int n=sc.nextInt();
		int[]a=new int[n];
		for(int i=0;i<n;i++)a[i]=sc.nextInt();
		SegmentTree sgt=new SegmentTree(a);
		int q=sc.nextInt();
		while(q-->0)
		{
			StringTokenizer st=new StringTokenizer(sc.nextLine());
			int s=st.countTokens();
			int l=Integer.parseInt(st.nextToken());
			int r=Integer.parseInt(st.nextToken());
//			System.out.println(s);	
			if(s==3)
			{
				int v=Integer.parseInt(st.nextToken());
				if(r<l)
				{	
					sgt.increment_range(l, n-1, v);
					sgt.increment_range(0, r, v);
				}
				else
					sgt.increment_range(l, r, v);
			}
			else
			{
				if(r<l)
					pw.println(Math.min(sgt.query(l, n-1),sgt.query(0, r)));
				else
					pw.println(sgt.query(l, r));
			}
//			System.out.println(sgt);
		}
		pw.close();
	}

	static class SegmentTree
	{
		int[]sgt;
		int[]a;
		int[]lazy;
		int n;
		public SegmentTree(int[]a)
		{
			int log=(int)(Math.ceil(Math.log(a.length)/Math.log(2)));
			n=1<<log;
			sgt=new int[n<<1];//index 0 is unused
			lazy=new int[n<<1];
			this.a=a;
//			for(int i=0;i<a.length;i++)
//				sgt[a.length+i]=a[i];
//			builditer();
			buildrec(1,n,1);
		}
		public void builditer()
		{
			for(int i=a.length-1;i>0;i--)
				sgt[i]=sgt[i*2]+sgt[i*2+1];
		}
		public void buildrec(int l,int r,int n)
		{
			if(l==r)
			{	
				if(l-1<a.length)//l-1 because our array is zero indexed
					sgt[n]=a[l-1];
				return;
			}
			int mid=(r+l)/2;
			buildrec(l,mid,2*n);
			buildrec(mid+1,r,2*n+1);
			sgt[n]=Math.min(sgt[2*n],sgt[2*n+1]);
		}
		public int query(int l,int r)//take zero index parameters
		{
			return query(1,n,1,l+1,r+1);
		}
		public int query(int s,int e,int i,int l,int r)
		{
			if(l<=s && r>=e)
				return sgt[i];
			if(r<s || l>e)
				return (int)1e9;
			int mid=e+s>>1;
			if(lazy[i]!=0)
				propagate(i,(e-s+1)/2);
			int left=query(s,mid,i*2,l,r);
			int right=query(mid+1,e,i*2+1,l,r);
			return Math.min(left,right);
		}
		public void increment_rec(int l,int r,int idx,int i,int val)
		{
			if(l==r)
			{
				sgt[i]+=val;
				return;
			}
			int mid=l+r>>1;
			propagate(i,(r-l+1)/2);
			if(idx<=mid)
				increment_rec(l,mid,idx,i<<1,val);
			else
				increment_rec(mid+1,r,idx,i<<1|1 ,val);
			sgt[i]=Math.min(sgt[i<<1],sgt[i<<1|1]);
		}
		public void increment_iter(int idx,int v)//array zero indexed
		{
			idx+=a.length;
			while(idx>0)
			{
				sgt[idx]+=v;
				idx>>=1;
			}
		}
		public void update(int idx,int v)//array zero indexed
		{
			int diff=v-a[idx];
//			increment_iter(idx, diff);
			a[idx]=v;
			increment_rec(1, a.length, idx, 1, diff);
		}
		public void increment_range(int l,int r,int v)
		{
			increment_range(l+1, r+1, 1, n, v, 1);
		}
		public void increment_range(int l,int r,int s,int e,int v,int i)
		{
			if(l<=s && r>=e)
			{
				sgt[i]+=v;
				lazy[i]+=v;
				return;
			}
			if(l>r || r<s)
				return;
			int mid=e+s>>1;
			if(lazy[i]!=0)
				propagate(i,(e-s+1)/2);
			if(l<=mid)
				increment_range(l, r, s, mid, v, i<<1);
			if(e>=mid+1)
				increment_range(l, r, mid+1, e, v, i<<1|1);
			sgt[i]=Math.min(sgt[i<<1],sgt[i<<1|1]);
		}
		public void propagate(int i,int mid)
		{
			sgt[i*2]+=lazy[i];
			sgt[i*2+1]+=lazy[i];
			lazy[i*2]+=lazy[i];
			lazy[i*2+1]+=lazy[i];
			lazy[i]=0;
			return;
		}
		public String toString()
		{
			String s="";
//			int level=1;
			for(int i=1;i<sgt.length;i++)
			{
				s+=sgt[i]+" ";
			}
			return s;
		}
	}
	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return st.nextToken();
		}

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

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

		double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

		boolean hasnext() throws IOException {
			return br.ready();
		}

	}
}
