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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CCircularRMQ solver = new CCircularRMQ();
        solver.solve(1, in, out);
        out.close();
    }

    static class CCircularRMQ {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }
            int qs = in.nextInt();
            RMQ rmq = new RMQ(arr);
            for (int i = 0; i < qs; i++) {
                String args = in.nextLine();
                while (args.isEmpty())
                    args = in.nextLine();
                String[] parts = args.split(" ");
                int a = Integer.parseInt(parts[0]);
                int b = Integer.parseInt(parts[1]);
                if (parts.length > 2) {
                    int c = Integer.parseInt(parts[2]);
                    if (a > b) {
                        rmq.increment(a, n - 1, c);
                        rmq.increment(0, b, c);
                    } else {
                        rmq.increment(a, b, c);
                    }
                } else {
                    long res;
                    if (a > b) {
                        long left = rmq.query(a, n - 1);
                        long right = rmq.query(0, b);
                        res = Math.min(left, right);
                    } else {
                        res = rmq.query(a, b);
                    }
                    out.println(res);
                }
            }
        }

    }

    static class RMQ {
        private long[] min;
        private long[] delta;
        private int n;

        RMQ(int[] arr) {
            this.n = arr.length;
            this.min = new long[this.n * 4 + 1];
            this.delta = new long[this.n * 4 + 1];

            init(1, 0, this.n - 1, arr);
        }

        public void increment(int l, int r, int val) {
            increment(1, 0, this.n - 1, l, r, val);
        }

        public long query(int l, int r) {
            return query(1, 0, this.n - 1, l, r);
        }

        private long query(int p, int from, int to, int l, int r) {
            if (from > r || to < l || from > to)
                return Long.MAX_VALUE;
            if (from >= l && to <= r) {
                return this.min[p] + delta[p];
            }
            int mid = mid(from, to);
            prop(p);
            long left = query(left(p), from, mid, l, r);
            long right = query(right(p), mid + 1, to, l, r);
            update(p);
            return Math.min(left, right);
        }

        private void init(int p, int l, int r, int[] arr) {
            if (l == r) {
                this.min[p] = arr[l];
                return;
            }
            int mid = mid(l, r);
            init(left(p), l, mid, arr);
            init(right(p), mid + 1, r, arr);
            update(p);
        }

        private void increment(int p, int from, int to, int l, int r, int val) {
            if (from > to)
                return;
            if (from > r || to < l) {
                return;
            }
            if (from >= l && r >= to) {
                delta[p] += val;
                return;
            }

            prop(p);
            int mid = mid(from, to);
            increment(left(p), from, mid, l, r, val);
            increment(right(p), mid + 1, to, l, r, val);

            update(p);
        }

        private void update(int p) {
            this.min[p] = Math.min(this.min[left(p)] + delta[left(p)], this.min[right(p)] + this.delta[right(p)]);
        }

        private void prop(int p) {
            this.delta[left(p)] += this.delta[p];
            this.delta[right(p)] += this.delta[p];
            this.delta[p] = 0;
        }

        private int mid(int l, int r) {
            return l + (r - l) / 2;
        }

        private int right(int p) {
            return 2 * p + 1;
        }

        private int left(int p) {
            return 2 * p;
        }

    }
}

