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.*;
import java.util.StringTokenizer;

public class Main2 {
    PrintWriter out;
    BufferedReader input;

    Main2() {
        try {
            input = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter(new FileWriter("output.txt"), true);
            solver();
        } catch (Exception ex) {
            ex.printStackTrace();
            input = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out, true);
            solver();
        } finally {
            out.close();
            try {
                input.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    StringTokenizer st = new StringTokenizer("");

    private String nextToken() {
        while (!st.hasMoreElements()) {
            try {
                st = new StringTokenizer(input.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

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

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

    public void solver() {
        int n = nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        Tree tree = new Tree(n, a);
        tree.build(1, 0, n - 1);
        int m = nextInt();
        for (int i = 0; i < m; i++) {
            int lf = nextInt();
            int k = st.countTokens();
            if (k == 1) {
                int r = nextInt();
                if (lf > r) {
                    out.println(Math.min(tree.get(1, 0, n - 1, lf, n - 1), tree.get(1, 0, n - 1, 0, r)));
                } else {
                    out.println(tree.get(1, 0, n - 1, lf, r));
                }
            } else {
                int r = nextInt();
                int v = nextInt();
                if (lf > r) {
                    tree.update(1, 0, n - 1, lf, n - 1, v);
                    tree.update(1, 0, n - 1, 0, r, v);
                } else {
                    tree.update(1, 0, n - 1, lf, r, v);
                }
            }
        }
    }

    public static void main(String[] args) {
        new Main2();
    }
}

class Tree {
    private int size = 0;
    private long[] tree;
    private int[] a;
    private long[] add;

    Tree(int num, int[] a_) {
        size = num;
        tree = new long[size * 4];
        a = a_;
        add = new long[size * 4];
    }

    public void build(int i, int bg, int end) {
        if (bg == end) {
            tree[i] = a[bg];
            return;
        }
        build(2 * i, bg, (bg + end) >> 1);
        build(2 * i + 1, 1 + ((bg + end) >> 1), end);
        tree[i] = Math.min(tree[2 * i], tree[2 * i + 1]);
    }

    void update(int i, int bg, int end, int from, int to, int val) {
        if (from > end || to < bg) return;
        if (bg >= from && end <= to) {
            add[i] += val;
            tree[i] += val;
            return;
        }
        update(2 * i, bg, (bg + end) >> 1, from, to, val);
        update(2 * i + 1, 1 + ((bg + end) >> 1), end, from, to, val);
        tree[i] = Math.min(tree[2 * i], tree[2 * i + 1]) + add[i];
    }

    long get(int i, int st, int end, int from, int to) {
        if (from > end || to < st) return Integer.MAX_VALUE;
        if (st >= from && end <= to) return tree[i];
        long ans = Math.min(get(2 * i, st, (st + end) >> 1, from, to),get(2 * i + 1, 1 + ((st + end) >> 1), end, from, to));
        ans += add[i];
        return ans;
    }
}