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.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;

import static java.lang.Double.*;
import static java.math.BigInteger.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main implements Runnable {
	
	private void solve() throws IOException {
//      long start = System.currentTimeMillis();
        readData();
        processing();
	}

	private void processing() {
	        
	}
	
	private void readData() throws IOException {
			parser = new Parser(System.in);
	        tree = new TreeMaxInterval(true);
	        int m = parser.nextInt();
	        for (int i = 0; i < m; ++i) {
	                int l = parser.nextInt();
	                int r = parser.nextInt();
	                if (parser.c != 32) {
	                        if (l <= r) {
	                                println(tree.extractMinValue(l, r));
	                        }
	                        else {
	                                println(min(tree.extractMinValue(l, n-1), tree.extractMinValue(0, r)));
	                        }
	                }
	                else {
	                        if (l <= r) {
	                                tree.change(l, r, parser.nextInt());
	                        }
	                        else {
	                                long value = parser.nextInt();
	                                tree.change(l, n-1, value);
	                                tree.change(0, r, value);
	                        }
	                }
	        }
	}
	
	private Parser parser;
	private TreeMaxInterval tree;
	private int n;
	
	private class TreeMaxInterval {
	        
    public TreeMaxInterval(boolean fromInput) throws IOException {
            n = parser.nextInt();
            init(n, 1000000000000L);
            for (int i = 0; i < n; ++i) {
                    tree[start+i] = parser.nextInt();
            }
            for (int i = start-1; i > 0; --i) {
                    tree[i] = min(tree[i<<1], tree[i<<1|1]);
            }
    }
    
    public TreeMaxInterval(int n, long initValue) {
            init(n, initValue);
    }
    
    public void init(int n, long initValue) {
            start = 1;
            while (start < n) {
                    start <<= 1;
            }
            tree = new long[start<<1];
            change = new long[start<<1];
            fill(change, 0);
            fill(tree, initValue);
    }
    
    public void change(int l, int r, long value) {
            l += start;
            r += start;
            tree[l] += value;
            if (l != r) {
                    tree[r] += value;
            }
            if (l>>1 != r>>1) {
                    if ((l&1) == 0) {
                            tree[l+1] += value;
                    }
                    if ((r&1) == 1) {
                            tree[r-1] += value;
                    }
                    l >>= 1;
                    r >>= 1;
                    while (l>>1 != r>>1) {                          
                            tree[l] = min(tree[l<<1], tree[l<<1|1]) + change[l];
                            tree[r] = min(tree[r<<1], tree[r<<1|1]) + change[r];
                            if ((l&1) == 0) {
                                    tree[l+1] += value;
                                    change[l+1] += value;
                            }
                            if ((r&1) == 1) {
                                    tree[r-1] += value;
                                    change[r-1] += value;
                            }
                            l >>= 1;
                            r >>= 1;
                    }
                    if (l+1 == r) {
                            tree[l] = min(tree[l<<1], tree[l<<1|1]) + change[l];
                            tree[r] = min(tree[r<<1], tree[r<<1|1]) + change[r];
                            l >>= 1;
                    }
            }
            else {
                    l >>= 1;
            }
            while (l > 0) {
                    tree[l] = min(tree[l<<1], tree[l<<1|1]) + change[l];
                    l >>= 1;
            }
        }
        
        public long extractMinValue(int l, int r) {
                l += start; 
                r += start;
                long minLeft = tree[l];
                long minRight = tree[r];
                while (l>>1 != r>>1) {
                        minLeft += change[l];
                        if ((l&1) == 0) {
                                minLeft = min(minLeft, tree[l+1]);
                        }
                        minRight += change[r];
                        if ((r&1) == 1) {
                                minRight = min(minRight, tree[r-1]);
                        }
                        l >>= 1;
                        r >>= 1;
                }
                if (l+1 == r) {
                        minLeft += change[l];
                        minRight += change[r];
                        l >>= 1;
                }
                long correction = 0;
                while (l > 0) {
                        correction += change[l];
                        l >>= 1;
                }
                return correction + min(minLeft, minRight);
        }
        
        private int start;
        public long[] tree;
        private long[] change;
	}

	private class Parser {

	   public Parser(InputStream in) {
	      din = new DataInputStream(in);
	      buffer = new byte[BUFFER_SIZE];
	      bufferPointer = bytesRead = 0;
	   }

	   public byte c;
	   
	   public int nextInt() throws IOException {
	      int value = 0;
	      c = read();
	      while (c <= ' ') c = read();
	      boolean neg = c == '-';
	      if (neg) c = read();
	      do {
	         value = value*10 + c-48;
	         c = read();
	      } 
	      while (c > ' ');
	      if (neg) {
	    	  return -value;
	      }
	      else {
	    	  return value;
	      }
	   }

	   private void fillBuffer() throws IOException {
	      bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
	      if (bytesRead == -1) buffer[0] = -1;
	   }

	   public byte read() throws IOException {
	      if (bufferPointer == bytesRead) fillBuffer();
	      return buffer[bufferPointer++];
	   }

	   private DataInputStream din;
	   private byte[] buffer;
	   private int bufferPointer, bytesRead;
	   
	   final private int BUFFER_SIZE = 1 << 16;
	}

	
	private int divisible;
	
	public static void main(String[] args) throws InterruptedException {
		new Thread(null, new Runnable() {
			public void run() {
				new Main().run();
			}
		}, "1", 1 << 24).start();
	}

	// @Override
	public void run() {
		try {
			boolean onlineJudge = System.getProperty("ONLINE_JUDGE") != null;
//			reader = onlineJudge ? new BufferedReader(new InputStreamReader(
//					System.in)) : new BufferedReader(
//					new FileReader("input.txt"));
			writer = onlineJudge ? new PrintWriter(new BufferedWriter(
					new OutputStreamWriter(System.out))) : new PrintWriter(
					new BufferedWriter(new FileWriter("output.txt")));
			Locale.setDefault(Locale.US);
			tokenizer = null;
			solve();
			writer.flush();
		} catch (Exception error) {
			error.printStackTrace();
			System.exit(1);
		}
	}

	private BufferedReader reader;
	private PrintWriter writer;
	private StringTokenizer tokenizer;

	private void println() {
		writer.println();
	}
	
	private void print(Object obj) {
		writer.print(obj);
	}
	
	private void println(Object obj) {
		writer.println(obj);
	}
	
	private void printf(String f, Object... obj) {
		writer.printf(f, obj);
	}

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

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

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

	private String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}
}