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.IOException;
import java.io.PrintWriter;

public class Main {

    public static void main(String[] args) {
        Scanner3 in = new Scanner3(1000000,10);
        PrintWriter out = new PrintWriter(System.out);
        int n = in.intNext();
        long[] a = new long[n];
        for(int i = 0; i < n; ++i) a[i] = in.intNext();
        SegmentTree t = new SegmentTree(a);
        int m = in.intNext();
        for(int i = 0; i < m; ++i) {
            String[] line = in.lineNext().split(" ");
            int lf = Integer.parseInt(line[0]);
            int rg = Integer.parseInt(line[1]);
            if(line.length == 2) {
                if(lf <= rg) out.println(t.query(lf,rg));
                else out.println(Math.min(t.query(lf,a.length-1),t.query(0,rg)));
            } else {
                int v = Integer.parseInt(line[2]);
                if(lf <= rg)t.update(lf,rg,v);
                else {
                    t.update(lf,a.length-1,v);
                    t.update(0,rg,v);
                }
            }
        }
        out.flush();
    }

}














class SegmentTree {

    class Node {
        public final int b,e;
        public long m, delta = 0; // all values in (b,...,e) should have delta added to them
        public Node left,right;
        public Node(int b,int e){this.b=b;this.e=e;}
        public int length(){return e-b+1;}
        public long value(){return m+delta;} // minimum value in (b,...,e)
    }
    
    private final long[] a;
    private final Node root;
    
    // a contains the initial values. O(n)
    public SegmentTree(long[] a) {
        this.a = a;
        root = init(0, a.length-1);
    }
    private Node init(int b, int e) {
        Node n = new Node(b,e);
        if(b == e) n.m = a[b];
        else {
            n.left = init(b,(b+e)/2);
            n.right = init((b+e)/2+1,e);
            n.m = Math.min(n.left.m,n.right.m);
        }
        return n;
    }

    //RETURNS: Min value in (i,...,j). O(logn)
    public long query(int i, int j) {
        return query(root,i,j);
    }
    //RETURNS: Min value in (n.b,...,n.e) intersect (i,...,j) or Long.MAX_VALUE if intersection is empty.
    private long query(Node n, int i, int j) {
        if(i > n.e || j < n.b) return Long.MAX_VALUE;  // If (n.b,...,n.e) is disjoint from (i,...,j).
        if(n.b >= i && n.e <= j) return n.value();  // If (n.b,...,n.e) is a subinterval of (i,...,j).
        return n.delta+Math.min(query(n.left,i,j),query(n.right,i,j));
    }
    //RETURNS: Value of index. O(logn)
    public long query(int index) {
        return query(index,index);
    }
    
    //Increment (i,...,j) by delta. O(logn)
    public void update(int i, int j, long delta) {
        inc(root,i,j,delta);
    }
    //Increment (n.b,...,n.e) intersect (i,...,j) by delta.
    private void inc(Node n, int i, int j, long delta) {
        if(i > n.e || j < n.b) return;  // If (n.b,...,n.e) is disjoint from (i,...,j).
        if(n.b >= i && n.e <= j) {  // If (b,...,e) is a subinterval of (i,...,j).
            n.delta += delta;
            return;
        }
        inc(n.left,i,j,delta);
        inc(n.right,i,j,delta);
        n.m = Math.min(n.left.value(),n.right.value());
    }
    //Set the value of index. O(logn)
    public void update(int index, long value) {
        update(index,index,value-query(index));
    }
}


class Scanner3 {
    
    public final byte[] b;
    public int bytesRead;
    public int i = 0;
    public Scanner3(int maxNumElems, int maxCharsPerElem) {
        b = new byte[maxNumElems*(maxCharsPerElem+5)+1000]; // Allocate more memory to be safe.
        int currRead = 0;
        do {
            bytesRead += currRead;
            try {
                currRead = System.in.read(b,bytesRead,b.length-bytesRead);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        } while(currRead > 0);
    }
            
    public void whitespaceSkip() {
        while(b[i] == ' ' || b[i] == '\r' || b[i] == '\n') ++i;
    }
    
    public int intNext() {
        int res = 0;
        boolean negate = false;
        if(b[i] == '-') {
            negate = true;
            ++i;
        }
        while(true) {
            if(b[i] < '0' || b[i] > '9') break;
            res=res*10+(b[i++]-'0');
        }
        if(negate) res *= -1;
        whitespaceSkip();
        return res;
    }
    
    public String lineNext() {
        StringBuilder sb = new StringBuilder();
        while(true) {
            if(b[i] == '\r' || b[i] == '\n') break;
            sb.append((char)b[i++]);
        }
        whitespaceSkip();
        return sb.toString();
    }
}
