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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1 << 18;
const long long INF = 12345678987654321LL;
struct SegTree {
  int n;
  long long a[MAXN << 1], m[MAXN << 1];
  void init(int c, long long e[MAXN]) {
    n = 1;
    while (n < c) {
      n <<= 1;
    }
    fill(a, a + n + n, 0);
    copy(e, e + c, m + n);
    fill(m + n + c, m + n + n, INF);
    for (int i = n - 1; i >= 1; --i) {
      m[i] = min(m[i * 2], m[i * 2 + 1]);
    }
  }
  void inc(int p, int pl, int pr, int l, int r, int v) {
    if (pl == l && pr == r) {
      a[p] += v;
      m[p] += v;
    } else {
      int pm = (pl + pr) / 2;
      if (r <= pm) {
        inc(p * 2, pl, pm, l, r, v);
      } else if (pm <= l) {
        inc(p * 2 + 1, pm, pr, l, r, v);
      } else {
        inc(p * 2, pl, pm, l, pm, v);
        inc(p * 2 + 1, pm, pr, pm, r, v);
      }
      m[p] = a[p] + min(m[p * 2], m[p * 2 + 1]);
    }
  }
  void inc(int l, int r, int v) {
    if (l <= r) {
      inc(1, 0, n, l, r + 1, v);
    } else {
      inc(1, 0, n, 0, r + 1, v);
      inc(1, 0, n, l, n, v);
    }
  }
  long long rmq(int p, int pl, int pr, int l, int r) {
    if (pl == l && pr == r) {
      return m[p];
    } else {
      int pm = (pl + pr) / 2;
      if (r <= pm) {
        return a[p] + rmq(p * 2, pl, pm, l, r);
      } else if (pm <= l) {
        return a[p] + rmq(p * 2 + 1, pm, pr, l, r);
      } else {
        return a[p] +
               min(rmq(p * 2, pl, pm, l, pm), rmq(p * 2 + 1, pm, pr, pm, r));
      }
    }
  }
  long long rmq(int l, int r) {
    if (l <= r) {
      return rmq(1, 0, n, l, r + 1);
    } else {
      return min(rmq(1, 0, n, 0, r + 1), rmq(1, 0, n, l, n));
    }
  }
} st;
long long e[MAXN];
int main() {
  int n, m, l, r, v;
  char buf[80];
  scanf("%d ", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%I64d", &e[i]);
  }
  st.init(n, e);
  scanf("%d ", &m);
  for (int i = 0; i < m; ++i) {
    fgets(buf, sizeof(buf), stdin);
    if (sscanf(buf, "%d%d%d", &l, &r, &v) == 3) {
      st.inc(l, r, v);
    } else {
      printf("%I64d\n", st.rmq(l, r));
    }
  }
  return 0;
}
