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 CircularRMQ
{
	public static void main(String [] args)   
	{
		MyScanner sc = new MyScanner();
	    PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	    int n = sc.nextInt();
	    SegmentTree s = new SegmentTree(n);
	    for (int i = 0; i < n; i++)
	    {
	    	s.update(i, i, sc.nextInt());
	    }
	    int m = sc.nextInt();
	    for (int i = 0; i < m; i++)
	    {
	    	String st = sc.nextLine();
	    	int first = st.indexOf(" ", 0);
	    	if (st.indexOf(" ", first + 1) == -1)
	    	{
	    		int start = Integer.parseInt(st.substring(0, first));
	    		int end = Integer.parseInt(st.substring(first + 1));
	    		if (start <= end)
	    		{
	    			long ret = s.minQuery(start, end);
	    			out.println(ret);
	    		}
	    		else
	    		{
	    			long end_segment = s.minQuery(start, n-1);
	    			long start_segment = s.minQuery(0, end);
	    			out.println(Math.min(end_segment, start_segment));
	    		}
	    	}
	    	else
	    	{
	    		int second = st.indexOf(" ", first + 1);
	    		int start = Integer.parseInt(st.substring(0, first));
	    		int end = Integer.parseInt(st.substring(first+1, second));
	    		int inc = Integer.parseInt(st.substring(second+1));
	    		if (start <= end)
	    		{
	    			s.update(start, end, inc);
	    		}
	    		else
	    		{
	    			s.update(start, n-1, inc);
	    			s.update(0, end, inc);
	    		}
	    	}
	    }
	    out.close();
	}
	
	public static class SegmentTree {
		private long[] min;
		private long[] lazy;
		private long[] sum;
		private int size;
		public SegmentTree(int size) {
			this.size = size;
			min = new long[4*size];
			sum = new long[4*size];
			lazy = new long[4*size];
		}
		public void update(int l, int r, int inc) {
			update(1, 0, size-1, l, r, inc);
		}
		private void pushDown(int index, int l, int r) {
			min[index] += lazy[index];
			sum[index] += lazy[index] * (r-l+1);
			if(l != r) {
				lazy[2*index] += lazy[index];
				lazy[2*index+1] += lazy[index];
			}
			lazy[index] = 0;
		}
		private void pullUp(int index, int l, int r) {
			int m = (l+r)/2;
			min[index] = Math.min(evaluateMin(2*index, l, m), evaluateMin(2*index+1, m+1, r));
			sum[index] = evaluateSum(2*index, l, m) + evaluateSum(2*index+1, m+1, r);
		}
		private long evaluateSum(int index, int l, int r) {
			return sum[index] + (r-l+1)*lazy[index];
		}
		private long evaluateMin(int index, int l, int r) {
			return min[index] + lazy[index];
		}
		private void update(int index, int l, int r, int left, int right, int inc) {
			if(r < left || l > right) return;
			if(l >= left && r <= right) {
				lazy[index] += inc;
				return;
			}
			pushDown(index, l, r);
			int m = (l+r)/2;
			update(2*index, l, m, left, right, inc);
			update(2*index+1, m+1, r, left, right, inc);
			pullUp(index, l, r);
		}
		public long minQuery(int l, int r) {
			return minQuery(1, 0, size-1, l, r);
		}
		private long minQuery(int index, int l, int r, int left, int right) {
			if(r < left || l > right) return Long.MAX_VALUE;
			if(l >= left && r <= right) {
				return evaluateMin(index, l, r);
			}
			pushDown(index, l, r);
			int m = (l+r)/2;
			long ret = Long.MAX_VALUE;
			ret = Math.min(ret, minQuery(2*index, l, m, left, right));
			ret = Math.min(ret, minQuery(2*index+1, m+1, r, left, right));
			pullUp(index, l, r);
			return ret;
		}
		public long sumQuery(int l, int r) {
			return sumQuery(1, 0, size-1, l, r);
		}
		private long sumQuery(int index, int l, int r, int left, int right) {
			if(r < left || l > right) return 0;
			if(l >= left && r <= right) {
				return evaluateSum(index, l, r);
			}
			pushDown(index, l, r);
			int m = (l+r)/2;
			long ret = 0;
			ret += sumQuery(2*index, l, m, left, right);
			ret += sumQuery(2*index+1, m+1, r, left, right);
			pullUp(index, l, r);
			return ret;
		}
	}
	
	   //-----------MyScanner class for faster input----------
	   public static class MyScanner
	   {
	      BufferedReader br;
	      StringTokenizer st;
	 
	      public MyScanner() {
	         br = new BufferedReader(new InputStreamReader(System.in));
	      }
	 
	      String next() {
	          while (st == null || !st.hasMoreElements()) {
	              try {
	                  st = new StringTokenizer(br.readLine());
	              } catch (IOException e) {
	                  e.printStackTrace();
	              }
	          }
	          return st.nextToken();
	      }
	 
	      int nextInt() {
	          return Integer.parseInt(next());
	      }
	 
	      long nextLong() {
	          return Long.parseLong(next());
	      }
	 
	      double nextDouble() {
	          return Double.parseDouble(next());
	      }
	 
	      String nextLine(){
	          String str = "";
		  try {
		     str = br.readLine();
		  } catch (IOException e) {
		     e.printStackTrace();
		  }
		  return str;
	      }
	      
	      

	   }
	   

}
