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

public class Contest52C {
    public static PrintWriter out = new PrintWriter(System.out);
    public static FastScanner enter=new FastScanner(System.in);
    public static void main(String[] args) throws IOException {
        solve();
        out.close();
    }

    private static void solve() throws IOException {
        int n = enter.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = enter.nextLong();
        }
        SegmentTree tree = new SegmentTree(arr.length, arr);
        tree.build(1, 0, arr.length - 1);
        int m = enter.nextInt();
        String[] cast;
        for (int i = 0; i < m; i++) {
            String tmp = enter.nextLine();
            cast = tmp.split(" ");
            if (cast.length == 2) {
                int first = Integer.valueOf(cast[0]);
                int second = Integer.valueOf(cast[1]);
                if (first > second) {
                    out.print(Math.min(tree.min(1, 0, n - 1, first, n - 1), tree.min(1, 0, n - 1, 0, second)) + " ");
                } else {
                    out.print(tree.min(1, 0, n - 1, first, second) + " ");
                }
            } else {
                int first = Integer.valueOf(cast[0]);
                int second = Integer.valueOf(cast[1]);
                int third = Integer.valueOf(cast[2]);
                if (first > second) {
                    tree.update(1, 0, n - 1, first, n - 1, third);
                    tree.update(1, 0, n - 1, 0, second, third);
                } else tree.update(1, 0, n - 1, first, second, third);
            }
        }
    }

    //package ... ctrl+alt+l //выравнять код


        static class FastScanner
        {
            BufferedReader br;
            StringTokenizer stok;

            FastScanner (InputStream is)
            {
                br = new BufferedReader(new InputStreamReader(is));
            }

            String next() throws IOException {
                while (stok == null || !stok.hasMoreTokens()) {
                    String s = br.readLine();
                    if (s == null) {
                        return null;
                    }
                    stok = new StringTokenizer(s);
                }
                return stok.nextToken();
            }

            int nextInt() throws IOException {
                return Integer.parseInt(next());
            }

            long nextLong() throws IOException {
                return Long.parseLong(next());
            }

            double nextDouble() throws IOException {
                return Double.parseDouble(next());
            }

            char nextChar() throws IOException {
                return (char) (br.read());
            }

            String nextLine() throws IOException {
                return br.readLine();
            }
        }


    static class SegmentTree {
        long[] t;
        long[] summ;
        long[] arr;

        public SegmentTree(int maxlen, long[] arr) {
            t = new long[maxlen * 4 + 1];
            summ = new long[maxlen * 4 + 1];
            this.arr = arr;
        }

        public long min(int v, int vl, int vr, int l, int r) {
            if (l > r) return Integer.MAX_VALUE;
            if (vl == l && vr == r) {
                return t[v];
            }
            int tmp = (vl + vr) / 2;
            return Math.min(min(2 * v, vl, tmp, l, Math.min(tmp, r)), min(2 * v + 1, tmp + 1, vr, Math.max(l, tmp + 1), r))+summ[v];
        }

        public void update(int v, int vl, int vr, int l, int r, long val) {
            if (l > r) return;

            if (vl == l && vr == r) {
                summ[v] += val;
                t[v]+=val;
                return;
            }
            int tmp = (vl + vr) / 2;
            update(2 * v, vl, tmp, l, Math.min(tmp, r), val);
            update(2 * v + 1, tmp + 1, vr, Math.max(tmp + 1, l), r, val);
            t[v] = Math.min(t[2 * v], t[2 * v + 1])+summ[v];
        }


        public void build(int v, int vl, int vr) {
            if (vl == vr) {
                t[v] = arr[vl];
                return;
            }
            int tmp = (vl + vr) / 2;
            build(2 * v, vl, tmp);
            build(2 * v + 1, tmp + 1, vr);
            t[v] = Math.min(t[2 * v], t[2 * v + 1]);
        }
    }

}
