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 static java.lang.Math.max;
import static java.lang.Math.min;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.function.BiFunction;

public class Main {

    static BiFunction<Integer, Integer, Integer> ADD = (x, y) -> (x + y);

    static long[] t;
    static long[] lazy;

    public static void main(String[] args) throws Exception {
        long startTime = System.nanoTime();
        int t = 1;
        while (t-- > 0) {
            solve();
        }
        long endTime = System.nanoTime();
        System.err.println("Execution Time : +" + (endTime - startTime) / 1000000 + " ms");
        System.exit(0);
    }

    static void solve() throws IOException {
        int n = Integer.parseInt(br.readLine());
        t = new long[n * 4];
        lazy = new long[n * 4];
        String[] temp = br.readLine().split(" ");
        long[] data = new long[n];
        int vvv = 0;
        for (String s : temp) {
            data[vvv++] = Long.parseLong(s);
        }
        build(data, 1, 0, data.length - 1);
        int m = Integer.parseInt(br.readLine());
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < m; i++) {
            String[] args = br.readLine().split(" ");
            int l = Integer.parseInt(args[0]);
            int r = Integer.parseInt(args[1]);
            int l1 = -1;
            int r1 = -1;
            if (r < l) {
                l1 = 0;
                r1 = r;
                r = data.length - 1;
            }
            if (args.length == 2) {
                long ans1 = query(1, 0, n - 1, l, r);
                if (l1 != -1 && r1 != -1) {
                    ans1 = min(ans1, query(1, 0, n - 1, l1, r1));
                }
                res.append(ans1);
                res.append("\n");
            } else if (args.length == 3) {
                update(1, 0, n - 1, l, r, Integer.parseInt(args[2]));
                if (l1 != -1 && r1 != -1) {
                    update(1, 0, n - 1, l1, r1, Integer.parseInt(args[2]));
                }
            }
        }
        System.out.println(res);
    }

    static void push(int v) {
        t[v * 2] += lazy[v];
        lazy[v * 2] += lazy[v];
        t[v * 2 + 1] += lazy[v];
        lazy[v * 2 + 1] += lazy[v];
        lazy[v] = 0;
    }

    static void build(long a[], int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = a[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(a, v * 2, tl, tm);
            build(a, v * 2 + 1, tm + 1, tr);
            t[v] = min(t[v * 2], t[v * 2 + 1]);
            ;
        }
    }

    static void update(int v, int tl, int tr, int l, int r, int addend) {
        if (l > r) {
            return;
        }
        if (l == tl && tr == r) {
            t[v] += addend;
            lazy[v] += addend;
        } else {
            push(v);
            int tm = (tl + tr) / 2;
            update(v * 2, tl, tm, l, min(r, tm), addend);
            update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, addend);
            t[v] = min(t[v * 2], t[v * 2 + 1]);
        }
    }

    static long query(int v, int tl, int tr, int l, int r) {
        if (l > r) {
            return 1000000000;
        }
        if (l <= tl && tr <= r) {
            return t[v];
        }
        push(v);
        int tm = (tl + tr) / 2;
        return min(query(v * 2, tl, tm, l, min(r, tm)), query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

}
