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 long long LINF = (long long)1e18;
const int INF = (int)1e9 + 7;
const int N = (int)5e5 + 5;
const double EPS = (double)1e-9;
const double PI = (double)3.14159265359;
const int MODULO[6] = {INF,        1000019677, 1000019393,
                       1000007521, 1000024073, 1000009667};
const int PF[5] = {77, 31, 98, 45, 67};
const int nx[4] = {0, 0, 1, -1};
const int ny[4] = {1, -1, 0, 0};
inline bool eq(const long double &a, const long double &b) {
  return fabs(a - b) < EPS;
}
int n, q;
int a[N];
long long t[N * 5], add[N * 5];
void push(int v) {
  t[v] += add[v];
  add[v + v] += add[v];
  add[v + v + 1] += add[v];
  add[v] = 0;
}
void update(int v, int l, int r, int L, int R, int x) {
  push(v);
  if (L > r || R < l) return;
  if (L <= l && r <= R) {
    add[v] += x;
    push(v);
    return;
  }
  int m = (l + r) / 2;
  update(v + v, l, m, L, R, x);
  update(v + v + 1, m + 1, r, L, R, x);
  t[v] = min(t[v + v], t[v + v + 1]);
}
void build(int v, int l, int r) {
  if (l == r) {
    t[v] = a[l];
    return;
  }
  int m = (l + r) / 2;
  build(v + v, l, m);
  build(v + v + 1, m + 1, r);
  t[v] = min(t[v + v], t[v + v + 1]);
}
long long get(int v, int l, int r, int L, int R) {
  push(v);
  if (L > r || R < l) return LINF;
  if (L <= l && r <= R) return t[v];
  int m = (l + r) / 2;
  return min(get(v + v, l, m, L, R), get(v + v + 1, m + 1, r, L, R));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  scanf("%d", &q);
  build(1, 1, n);
  while (q--) {
    vector<int> arr;
    int x = 0;
    bool neg = 0;
    scanf("\n");
    while (true) {
      char nxt = getchar();
      if (nxt == '\n') break;
      if (!isdigit(nxt) && nxt != '-') {
        arr.push_back(neg ? -x : x);
        x = 0, neg = 0;
      } else {
        if (isdigit(nxt))
          x = x * 10 + (nxt - '0');
        else
          neg = 1;
      }
    }
    arr.push_back(neg ? -x : x);
    arr[0]++, arr[1]++;
    if (arr.size() == 2) {
      if (arr[0] <= arr[1])
        printf("%I64d\n", get(1, 1, n, arr[0], arr[1]));
      else
        printf("%I64d\n",
               min(get(1, 1, n, arr[0], n), get(1, 1, n, 1, arr[1])));
    } else {
      if (arr[0] <= arr[1])
        update(1, 1, n, arr[0], arr[1], arr[2]);
      else {
        update(1, 1, n, arr[0], n, arr[2]);
        update(1, 1, n, 1, arr[1], arr[2]);
      }
    }
  }
  return 0;
}
