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.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.Random;


/*

4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1

4
1 2 3 4
1
3 0 -1


10
1 2 3 4 5 6 7 8 9 10
5
1 1 -20
0 5 500
0 9
4 9 -300
9 9


 */
public class TournamentTree {

	class Node
	{
		long delta;
		long minValue;
		
		int rl;
		int rr;
		
		Node left;
		Node right;
		
		Node(int rangeL, int rangeR)
		{
			//System.out.println(rangeL +" "+rangeR);
			rl = rangeL;
			rr = rangeR;
			
			if(rangeL != rangeR)
			{
				int mid = (rangeR + rangeL)/2;
				left = new Node(rangeL, mid);
				right = new Node(mid+1, rangeR);
			}
		}
		
		void update(int l, int r, long val)
		{
			prop();
			
			//System.out.println("update: ["+l+","+r+"] "+val);
			//System.out.println((minValue + delta)+"["+rl+","+rr +"]("+minValue+"){"+delta+"} ");
			
			//Found the range
			if(l == rl && r == rr)
			{
				delta += val;
			}
			else
			{
				int mid = (rr + rl)/2;
				if(l <= mid)
					left.update(l, Math.min(mid, r), val);
				if(r > mid)
					right.update(Math.max(mid+1, l), r, val);
				
				if(left != null && right != null)
					minValue = Math.min(left.value(), right.value());
			}
		}
		
		void prop()
		{
			if(delta != 0)
			{
				minValue += delta;
				
				if(left != null)
					left.delta += delta;
				
				if(right != null)
					right.delta += delta;
				
				delta = 0;
			}
		}
		
		long query(int l, int r)
		{
			prop();
			
			//Found the range
			if(l == rl && r == rr)
			{
				return value();
			}
			else
			{
				long ret = Long.MAX_VALUE;
				int mid = (rr + rl)/2;
				if(l <= mid)
					ret = Math.min(ret, left.query(l, Math.min(mid, r)));
				if(r > mid)
					ret = Math.min(ret, right.query(Math.max(mid+1, l), r));
				
				return ret;
			}
		}
		
		long value ()
		{
			return delta + minValue;
		}
		
		void print()
		{
			prop();
			
			if(left == null && right == null)
				System.out.print(value() +" ");
			
			if(left != null)
				left.print();
			
			//System.out.print((minValue + delta)+"["+rl+","+rr +"]("+minValue+"){"+delta+"} ");
			
			if(right != null)
				right.print();
		}
	}
	
	int size;
	Node root;
	
	public TournamentTree(int n)
	{
		size = n;
		
		root = new Node(0, n-1);
	}
	
	void update(int left, int right, long delta)
	{
		root.update(left, right, delta);
	}
	
	long query(int left, int right)
	{
		return root.query(left, right);
	}
	
	void print()
	{
		root.print();
		System.out.println();
	}
	
	public static void main(String[] args) {
		
		//gen();
		
		FastScanner in = new FastScanner();
		
		int n = in.nextInt();
		
		long[] init = new long[n];
		for(int curr = 0; curr < n; ++curr)
		{
			init[curr] = in.nextInt();
		}
		
		int m = in.nextInt();
		
		String[] op = new String[m];
		
		for(int curr = 0; curr < m; ++curr)
		{
			op[curr] = in.nextLine();
		}
		
		solve(n, init, m, op, null);
	}
	
	static void gen()
	{
		int n = 200000;
		
		long[] init = new long[n];
		Random rand = new Random();
		
		for(int curr = 0; curr < n; ++curr)
		{
			init[curr] = rand.nextInt((int)(1E6));
			//System.out.print(init[curr] +" ");
		}
		//System.out.println();
		
		int m = 200000;
		
		String[] op = new String[m];
		
		for(int curr = 0; curr < m; ++curr)
		{
			op[curr] = (rand.nextInt(n)) +" " +(rand.nextInt(n));
			if(rand.nextBoolean())
			{
				op[curr] += " " + ((rand.nextBoolean()?1:-1) * rand.nextInt()); 
			}
			
			//System.out.println(op[curr]);
		}
		
		ArrayList<Long> itOut = new ArrayList<Long>();
		ArrayList<Long> bfOut = new ArrayList<Long>();
		
		System.out.println("Gen");
		solve(n, init, m, op, itOut);
		System.out.println("solved");
		bf(n, init, m, op, bfOut);
		System.out.println("bruteforced");
		
		boolean same = itOut.size() == bfOut.size();
		if(same)
		{
			int i;
			for(i = 0; i < itOut.size() && i < bfOut.size() && same; ++i)
			{
				same = (itOut.get(i).equals(bfOut.get(i)));
				//System.out.println(itOut.get(i) +" " +bfOut.get(i));
			}
			//System.out.println(i +" " + itOut.size());
		}
		else
			System.out.println(itOut.size() +" "+ bfOut.size());
		
		System.out.println(same);
	}
	
	static void solve(int n, long[] init, int numOp, String[] ops, ArrayList<Long> out)
	{
		StringBuilder s = new StringBuilder();
		
		TournamentTree tt = new TournamentTree(n);
		
		for(int curr = 0; curr < n; ++curr)
		{
			tt.update(curr, curr, init[curr]);
		}
		
		for(int currOp = 0; currOp < numOp; ++currOp)
		{
			//tt.print();
			String[] op = ops[currOp].split("\\s+");
			if(op.length == 3)
			{
				int l = Integer.parseInt(op[0]);
				int r = Integer.parseInt(op[1]);
				
				long delta = Long.parseLong(op[2]);
				
				if(l > r)
				{
					tt.update(0, r, delta);
					tt.update(l, n-1, delta);
				}
				else
				{
					tt.update(l, r, delta);
				}
			}
			else if(op.length == 2)
			{
				int l = Integer.parseInt(op[0]);
				int r = Integer.parseInt(op[1]);
				
				if(l > r)
				{
					long val = tt.query(0, r);
					val = Math.min(val, tt.query(l, n-1));
					
					if(out == null)
						//System.out.println(val);
						s.append(val +"\n");
					else
						out.add(val);
				}
				else
				{
					long val = tt.query(l, r);
					if(out == null)
						//System.out.println(val);
						s.append(val+"\n");
					else
						out.add(val);
				}
			}
		}
		if(out == null)
			System.out.print(s);
		//tt.print();
	}
	
	static class bruteforce
	{
		int n;
		long[] values;
		
		bruteforce(int n)
		{
			this.n = n;
			values = new long[n];
		}
		
		void update(int left, int right, long delta)
		{
			for(int curr = left; curr <= right; ++curr)
				values[curr] += delta;
		}
		
		long query(int left, int right)
		{
			long min = Long.MAX_VALUE;
			for(int curr = left; curr <= right; ++curr)
				min = Math.min(values[curr], min);
			return min;
		}
		
		void print()
		{
			for(int i = 0; i < n; ++i)
			{
				System.out.print(values[i] +" ");
			}
			System.out.println();
		}
	}
	
	static void bf(int n, long[] init, int numOp, String[] ops, ArrayList<Long> out)
	{
		bruteforce b = new bruteforce(n);
		
		for(int curr = 0; curr < n; ++curr)
		{
			b.update(curr, curr, init[curr]);
		}
		
		for(int currOp = 0; currOp < numOp; ++currOp)
		{
			String[] op = ops[currOp].split("\\s+");
			if(op.length == 3)
			{
				int l = Integer.parseInt(op[0]);
				int r = Integer.parseInt(op[1]);
				
				long delta = Long.parseLong(op[2]);
				
				if(l > r)
				{
					b.update(0, r, delta);
					b.update(l, n-1, delta);
				}
				else
				{
					b.update(l, r, delta);
				}
			}
			else if(op.length == 2)
			{
				int l = Integer.parseInt(op[0]);
				int r = Integer.parseInt(op[1]);
				
				if(l > r)
				{
					long val = b.query(0, r);
					val = Math.min(val, b.query(l, n-1));
					
					if(out == null)
						System.out.println(val);
					else
						out.add(val);
				}
				else
				{
					long val = b.query(l, r);
					if(out == null)
						System.out.println(val);
					else
						out.add(val);
				}
			}
		}
		//b.print();
	}

}

class FastScanner{
	   private InputStream stream;
	   private byte[] buf = new byte[1024];
	   private int curChar;
	   private int numChars;

	   public FastScanner()
	   {
	      stream = System.in;
	   }

	   int read()
	   {
	      if (numChars == -1)
	         throw new InputMismatchException();
	      if (curChar >= numChars){
	         curChar = 0;
	         try{
	            numChars = stream.read(buf);
	         } catch (IOException e) {
	            throw new InputMismatchException();
	         }
	         if (numChars <= 0)
	            return -1;
	      }
	      return buf[curChar++];
	   }

	   boolean isSpaceChar(int c)
	   {
	      return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
	   }
	   
	   boolean isEndline(int c)
	   {
	      return c=='\n'||c=='\r'||c==-1;
	   }

	   int nextInt()
	   {
	      return Integer.parseInt(next());
	   }
	   
	   long nextLong()
	   {
	      return Long.parseLong(next());
	   }

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

	   String next(){
	      int c = read();
	      while (isSpaceChar(c))
	         c = read();
	      StringBuilder res = new StringBuilder();
	      do{
	         res.appendCodePoint(c);
	         c = read();
	      }while(!isSpaceChar(c));
	      return res.toString();
	   }
	   
	   String nextLine(){
	      int c = read();
	      while (isEndline(c))
	         c = read();
	      StringBuilder res = new StringBuilder();
	      do{
	         res.appendCodePoint(c);
	         c = read();
	      }while(!isEndline(c));
	      return res.toString();
	   }
	}
