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.util.*;
import java.io.*;

public class c {
	static int[] vals;
	static int[][] ops;
	static Node root;

	public static void main(String[] args) throws FileNotFoundException {
		FastScanner in = new FastScanner();
		String[] split;
		String temp;
		int numVals, numOps;
		int i, j;
		
		//Input
		numVals = in.nextInt();
		vals = new int[numVals];
		for(i = 0; i < numVals; i++)
			vals[i] = in.nextInt();
		
		numOps = in.nextInt(); //in.nextLine();
		
		ops = new int[numOps][];
		for(i = 0; i < numOps; i++){
			temp = in.nextLine();
			split = temp.split(" ");
			ops[i] = new int[split.length];
			for(j = 0; j < split.length; j++)
				ops[i][j] = Integer.parseInt(split[j]);
		}
		
		
		//Create tree
		if(numVals > 1){
			root = new Node(buildTree(0, (vals.length - 1) / 2), buildTree((vals.length - 1) / 2 + 1, vals.length - 1), 0, vals.length - 1);
			root.minVal = Math.min(root.childA.minVal, root.childB.minVal);
		}
		else{
			root = new Node(null, null, 0, 0);
			root.minVal = vals[0];
		}
		
		
		//Solve
		//System.out.println("Initial tree:");
		//print(root);
		//System.out.println();
		for(i = 0; i < numOps; i++){
			
			//Increment
			if(ops[i].length == 3 && ops[i][2] != 0){
				//System.out.printf("Operation: %d %d %d%n", ops[i].get(0), ops[i].get(1), ops[i].get(2));
				
				if(ops[i][0] > ops[i][1]){
					inc(root, 0, ops[i][1], ops[i][2]);
					inc(root, ops[i][0], root.interval[1], ops[i][2]);
				}
				else
					inc(root, ops[i][0], ops[i][1], ops[i][2]);
				
				//print(root);
				//System.out.println();
			}
			
			
			//Return minVal
			else if(ops[i].length == 2){
				//System.out.printf("Operation: %d %d%n", ops[i].get(0), ops[i].get(1));
				//System.out.print("Ans: ");
				
				if(ops[i][0] > ops[i][1]){
					System.out.println(Math.min(min(root, 0, ops[i][1]), min(root, ops[i][0], root.interval[1])));
				}
				else
					System.out.println(min(root, ops[i][0], ops[i][1]));
				
				//print(root);
				//System.out.println();
			}
		}
	}
	
	static void inc(Node curNode, int start, int end, int amount){
		
		//Reached the node that completely covers the interval
		if(curNode.interval[0] == start && curNode.interval[1] == end){
			curNode.minVal += amount;
			curNode.delta += amount;
			return;
		}
		
		
		//Update children
		curNode.childA.delta += curNode.delta;
		curNode.childB.delta += curNode.delta;
		curNode.childA.minVal += curNode.delta;
		curNode.childB.minVal += curNode.delta;
		curNode.delta = 0;
		
		
		//ChildA contains the start interval
		if(curNode.childA.interval[1] >= start)
			inc(curNode.childA, start, Math.min(end, curNode.childA.interval[1]), amount);
		
		
		//ChildB contains the end interval
		if(curNode.childB.interval[0] <= end)
			inc(curNode.childB, Math.max(start, curNode.childB.interval[0]), end, amount);
		
		curNode.minVal = Math.min(curNode.childA.minVal, curNode.childB.minVal);
	}
	
	static int min(Node curNode, int start, int end){
		int ans = Integer.MAX_VALUE;

		//Update children
		if(curNode.childA != null){
			curNode.childA.delta += curNode.delta;
			curNode.childB.delta += curNode.delta;
			curNode.childA.minVal += curNode.delta;
			curNode.childB.minVal += curNode.delta;
			curNode.delta = 0;
		}
		
		//Reached the node that completely covers the interval
		if(curNode.interval[0] == start && curNode.interval[1] == end)
			return curNode.minVal;
		
		
		//ChildA contains the start interval
		if(curNode.childA.interval[1] >= start)
			ans = min(curNode.childA, start, Math.min(end, curNode.childA.interval[1]));
		
		
		//ChildB contains the end interval
		if(curNode.childB.interval[0] <= end)
			ans = Math.min(ans, min(curNode.childB, Math.max(start, curNode.childB.interval[0]), end));
		
		
		return ans;
	}
	
	static Node buildTree(int start, int end){
			Node newNode;
			
			if(start == end){
				newNode = new Node(null, null, start, end);
				newNode.minVal = vals[start];
			}
			else{
				newNode = new Node(buildTree(start, (start + end) / 2), buildTree((start + end) / 2 + 1, end), start, end);
				newNode.minVal = Math.min(newNode.childA.minVal, newNode.childB.minVal);
			}
			
			return newNode;
		}
	
	static void print(Node curNode){
		System.out.println(curNode.minVal);
		
		if(curNode.childA == null)
			return;
		
		print(curNode.childA);
		print(curNode.childB);
	}
	
	static 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();
		   }
		}
	
	static class Node{
		Node childA, childB;
		int[] interval;
		
		int delta;
		int minVal;
		
		Node(Node a, Node b, int s, int e){
			childA = a;
			childB = b;
			interval = new int[2];
			
			interval[0] = s;
			interval[1] = e;
			
			delta = 0;
			minVal = Integer.MAX_VALUE;
		}
	}
}
