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;

public class CircularRMQ {
    public static long t[] = new long[4 * 200005];
    public static long update[] = new long[4 * 200005];
    public static int a[];

    public static int max=0;

    public static long build(int v, int tl, int tr) {
        if (tl == tr) {
            return t[v] = a[tl];
        }
        int tm = (tl + tr) / 2;
        long l = build(v * 2, tl, tm);
        long r = build(v * 2 + 1, tm + 1, tr);
        return t[v] = Math.min(l, r);
    }

    public static long query(int v, int l, int r, int tl, int tr) {
//System.out.println(l+" "+r+" "+v+" "+tl+" "+tr);
        if (l > r)
            return Integer.MAX_VALUE;
        if (update[v] != 0) {
            t[v] += update[v];
            if (2 * v < max) {
                update[2 * v] += update[v];
                update[2 * v + 1] += update[v];
            }
            update[v] = 0;
        }
        if (l == tl && r == tr)
            return t[v];
        int tm = (tl + tr) / 2;
        
        long nl = query(2 * v, l, Math.min(r, tm), tl, tm);
        long nr = query(2 * v + 1, Math.max(l, tm + 1), r, tm + 1, tr);
        return Math.min(nl, nr);
    }

    public static long update(int v, int l, int r, int tl, int tr, int value) {

        if (l > r)
            return query(v, tl, tr, tl, tr);
        if (update[v] != 0) {
            t[v] += update[v];
            if (2 * v < max) {
                update[2 * v] += update[v];
                update[2 * v + 1] += update[v];
            }
            update[v] = 0;
        }
        if (l == tl & r == tr) {
            t[v] += value;
            if (2 * v <max) {
                update[2 * v] += value;
                update[2 * v + 1] += value;
            }
            return t[v];
        }
        if (tl == tr) {
            return t[v];
        }
        int tm = (tr + tl) / 2;
        long nl = update(v * 2, l, Math.min(r, tm), tl, tm, value);
        long nr = update(v * 2 + 1, Math.max(l, tm + 1), r, tm + 1, tr, value);
        // System.out.println(l+" "+r+" "+tl+" "+tr+" "+nl+" "+nr+" "+Math.max(l,
        // tm+1)+" "+r);
        return t[v] = Math.min(nl, nr);
    }

    public static long query2(int v, int l, int r, int tl, int tr) {
        if (l > r) {
            int fs = l;
            int fe = a.length - 1;
            int ss = 0;
            int se = r;
            // System.out.println(fs+" "+fe+" "+ss+" "+se);
            return Math.min(query(v, fs, fe, tl, tr), query(v, ss, se, tl, tr));
        } else
            return query(v, l, r, tl, tr);
    }

    public static long update2(int v, int l, int r, int tl, int tr, int value) {
        if (l > r) {
            int fs = l;
            int fe = a.length - 1;
            int ss = 0;
            int se = r;
            // System.out.println(fs+" "+fe+" "+ss+" "+se);
            return Math.min(update(1, fs, fe, tl, tr, value),
                    update(1, ss, se, tl, tr, value));
        } else
            return update(1, l, r, tl, tr, value);
    }

    public static void main(String[] args) throws NumberFormatException,
            IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(
                System.in));
        int x = Integer.parseInt(reader.readLine());
        String st[] = reader.readLine().split(" ");
        a = new int[st.length];
        for (int i = 0; i < st.length; i++)
            a[i] = Integer.parseInt(st[i]);
        build(1, 0, a.length - 1);
        max=(a.length+5)*4;
        // System.out.println(query(1, 0, 3, 0, 3));
        // System.out.println(update(1, 0, 0, 0, 3, 4));
        // System.out.println(t[2]);
        int queres = Integer.parseInt(reader.readLine());
        for (int i = 0; i < queres; i++) {
            st = reader.readLine().split(" ");
            int l = Integer.parseInt(st[0]);
            int r = Integer.parseInt(st[1]);
            if (st.length == 3) {
                update2(1, l, r, 0, a.length - 1, Integer.parseInt(st[2]));
            } else {
                System.out.println(query2(1, l, r, 0, a.length - 1));
            }
        }

    }

}
