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.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class trialNerror {
//  #define N 20
//  #define MAX (1+(1<<6)) // Why? :D
//  #define inf 0x7fffffff
     
    static int arr[];//N
    static int tree[];//Max
    static int lazy[];//max
     
    /**
     * Build and init tree
     */
    static void build_tree(int node, int a, int b) {
        if(a > b) return; // Out of range
        
        if(a == b) { // Leaf node
                tree[node] = arr[a]; // Init value
            return;
        }
        int x = node<<1;
        int mid = (a+b)>>1;
        build_tree(x, a, mid); // Init left child
        build_tree(x+1, 1+mid, b); // Init right child
        
        tree[node] = Math.min(tree[node*2], tree[node*2+1]); // Init root value
    }
     
    /**
     * Increment elements within range [i, j] with value value
     */
    static void update_tree(int node, int a, int b, int i, int j, int value) {
      
        if(lazy[node] != 0) { // This node needs to be updated
            tree[node] += lazy[node]; // Update it
     
            if(a != b) {
                int x = node<<1;
                lazy[x] += lazy[node]; // Mark child as lazy
                    lazy[x+1] += lazy[node]; // Mark child as lazy
            }
     
            lazy[node] = 0; // Reset it
        }
      
        if(a > b || a > j || b < i) // Current segment is not within range [i, j]
            return;
        
        if(a >= i && b <= j) { // Segment is fully within range
                tree[node] += value;
     
            if(a != b) { // Not leaf node
                int x = node<<1;
                lazy[x] += value;
                lazy[x+1] += value;
            }
     
                return;
        }
        int x = node<<1;
        int mid = (a+b)>>1;
        update_tree(x, a, mid, i, j, value); // Updating left child
        update_tree(1+x, 1+mid, b, i, j, value); // Updating right child
     
        tree[node] = Math.min(tree[x], tree[x+1]); // Updating root with max value
    }
     
    /**
     * Query tree to get max element value within range [i, j]
     */
    static int query_tree(int node, int a, int b, int i, int j) {
        
        if(a > b || a > j || b < i) return Integer.MAX_VALUE; // Out of range
     
        if(lazy[node] != 0) { // This node needs to be updated
            tree[node] += lazy[node]; // Update it
     
            if(a != b) {
                int x = node<<1;
                lazy[x] += lazy[node]; // Mark child as lazy
                lazy[x+1] += lazy[node]; // Mark child as lazy
            }
     
            lazy[node] = 0; // Reset it
        }
     
        if(a >= i && b <= j) // Current segment is totally within range [i, j]
            return tree[node];
        int x = node<<1;
        int mid = (a+b)>>1;
        int q1 = query_tree(x, a, mid, i, j); // Query left child
        int q2 = query_tree(1+x, 1+mid, b, i, j); // Query right child
     
        int res = Math.min(q1, q2); // Return final result
        
        return res;
    }
     
//  int main() {
//      for(int i = 0; i < N; i++) arr[i] = 1;
//   
//      build_tree(1, 0, N-1);
//   
//      memset(lazy, 0, sizeof lazy);
//   
//      update_tree(1, 0, N-1, 0, 6, 5); // Increment range [0, 6] by 5. here 0, N-1 represent the current range.
//      update_tree(1, 0, N-1, 7, 10, 12); // Incremenet range [7, 10] by 12. here 0, N-1 represent the current range.
//      update_tree(1, 0, N-1, 10, N-1, 100); // Increment range [10, N-1] by 100. here 0, N-1 represent the current range.
//   
//      cout << query_tree(1, 0, N-1, 0, N-1) << endl; // Get max element in range [0, N-1]
//  }
    public static void main(String[]args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int length = Integer.parseInt(st.nextToken());
        StringBuilder res = new StringBuilder();
        st = new StringTokenizer(br.readLine());
         arr = new int[length];
         tree = new int[length<<2];
         lazy = new int[length<<2];

//      init(length);
        //  for(int i = 0; i < length; i++) arr[i] = 1;
        for(int i = 0;i<length;i++)
            arr[i] = Integer.parseInt(st.nextToken()); 
        build_tree(1, 0, length-1);
//          System.out.println(Arrays.toString(tree));
//          System.out.println(Arrays.toString(helper));
//          System.out.println(Arrays.toString(lazy));
        st = new StringTokenizer(br.readLine());
        int numOfQueries = Integer.parseInt(st.nextToken());
        for(int i = 0;i<numOfQueries;i++){
            st = new StringTokenizer(br.readLine());
            int lf = Integer.parseInt(st.nextToken());
            int rg = Integer.parseInt(st.nextToken());
            if(st.hasMoreTokens()){
                int val = Integer.parseInt(st.nextToken());
                if(lf<=rg){
                    update_tree(1,0,length-1,lf, rg, val);
                }
                else
                {
                    update_tree(1,0,length-1,lf,length-1, val);
                    update_tree(1,0,length-1,0,rg, val);
                }
//                          System.out.println(Arrays.toString(tree));
//                          System.out.println(Arrays.toString(helper));
//                          System.out.println(Arrays.toString(lazy));


            }
            else{
                if(lf<=rg){
                    res.append(query_tree(1,0,length-1,lf, rg));
                    //              System.out.print("\n");

                }
                else
                {

                    res.append(Math.min(query_tree(1,0,length-1,lf, length-1),query_tree(1,0,length-1,0, rg)));
                    //              System.out.print("\n");

                }   
                res.append("\n");
                //                          System.out.println(Arrays.toString(arr));
                //                          System.out.println(Arrays.toString(tree));
                //                          System.out.println(Arrays.toString(lazy));
            }

        }
        System.out.println(res.toString());
    }
}
