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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class CircularRMQ {
	static int mod;
	static int[] arr;
	static long[] st,lazy;
	static int n;
	public static void build() {
		st=new long[n<<2];
		lazy=new long[n<<2];
		build(1,1,n);
	}
	public static void build(int v , int b, int e) {
		if(b==e) {
			st[v]=arr[b-1];
		}else {
			int mid=b+e>>1;
			build(v<<1, b, mid);
			build(v<<1|1, mid+1, e);
			st[v]=Math.min(st[v<<1],st[v<<1|1]);
			
		
		}
	}
	public static long query(int l, int r) {
	return query(1,1,n,l,r);
	}
	static long INF=2l*(int)1e5*(long)1e6;
	public static long query(int v, int b, int e ,int l ,int r) {
		if(l>e||r<b)return INF;
		if(l<=b&&e<=r)return st[v];
		propagate(v);
		int mid=b+e>>1;
		return Math.min(query(v<<1, b,mid,l,r), query(v<<1|1, mid+1,e,l,r));
		
	}
	public static void update(int l ,int r,int val) {
		update(1,1,n,l,r,val);
	}
	public static void update(int v, int b, int e, int l ,int r ,int val) {
		if(l>e||r<b)return;
		if(l<=b&&e<=r) {
			st[v]+=val;
			lazy[v]+=val;
		}else {
			int mid=b+e>>1;
			propagate(v);
			update(v<<1, b, mid,l,r,val);
			update(v<<1|1,mid+1,e,l,r,val);
			st[v]=Math.min(st[v<<1],st[v<<1|1]);
			
		}
	}
	public static void propagate(int v) {
		lazy[v<<1]+=lazy[v];
		lazy[v<<1|1]+=lazy[v];
		st[v<<1]+=lazy[v];
		st[v<<1|1]+=lazy[v];
		lazy[v]=0;
	}
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		n=sc.nextInt();
		arr=sc.nextIntArr(n);
		int m=sc.nextInt();
		build();
		for(int i=0;i<m;i++) {
			StringTokenizer st=new StringTokenizer(sc.nextLine());
			int l =Integer.parseInt(st.nextToken())+1;
			int r =Integer.parseInt(st.nextToken())+1;
			if(st.hasMoreElements()) {
				int val=Integer.parseInt(st.nextToken());
				if(l<=r) {
					update(l, r, val);
				}else {
					update(l, n, val);
					update(1, r, val);
				}
			}else {
				if(l<=r) {
					pw.println(query(l, r));
				}else {
					pw.println(Math.min(query(l, n), query(1, r)));
				}
			}
		}
		pw.flush();
	}

	static long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static long lcm(long a, long b) {
		return a / gcd(a, b) * b;
	}

	public static int log(int n, int base) {
		int ans = 0;
		while (n + 1 > base) {
			ans++;
			n /= base;
		}
		return ans;
	}

	static int pow(int b, long e) {
		int ans = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				ans = (int) ((ans * 1l * b));
			e >>= 1;
			{

			}
			b = (int) ((b * 1l * b));
		}
		return ans;
	}

	static long powmod(long b, long e, int mod) {
		long ans = 1;
		b %= mod;
		while (e > 0) {
			if ((e & 1) == 1)
				ans = (int) ((ans * 1l * b) % mod);
			e >>= 1;
			b = (int) ((b * 1l * b) % mod);
		}
		return ans;
	}

	public static long add(long a, long b) {
		return (a + b) % mod;
	}

	public static long sub(long a, long b) {
		return (a - b + mod) % mod;
	}

	public static long mul(long a, long b) {
		return ((a % mod) * (b % mod)) % mod;
	}

	static class longPair implements Comparable<longPair> {
		long x, y;

		public longPair(long a, long b) {
			x = a;
			y = b;
		}

		public int compareTo(longPair p) {
			return (p.x == x) ? ((p.y == y) ? 0 : (y > p.y) ? 1 : -1) : (x > p.x) ? 1 : -1;
		}
	}

	static class Pair implements Comparable<Pair> {
		int x;
		int y;

		public Pair(int a, int b) {
			this.x = a;
			y = b;
		}

		public int compareTo(Pair o) {
			return (x == o.x) ? ((y > o.y) ? 1 : (y == o.y) ? 0 : -1) : ((x > o.x) ? 1 : -1);
		}

		@Override

		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}

		@Override

		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pair other = (Pair) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}

	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(s));
		}

		public long[] nextLongArr(int n) throws IOException {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++)
				arr[i] = nextLong();
			return arr;
		}

		public int[] nextIntArr(int n) throws IOException {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++)
				arr[i] = nextInt();
			return arr;
		}

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

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

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

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

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++) {
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
				if (sb.length() == 18) {
					res += Long.parseLong(sb.toString()) / f;
					sb = new StringBuilder("0");
				}
			}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

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

	}

	public static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}
}
