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>
const long long INF = 1e18 + 5;
const double PI = acos(-1.0);
const double EPS = 1e-9;
using namespace std;
template <typename F, typename S>
ostream &operator<<(ostream &os, const pair<F, S> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  typename vector<T>::const_iterator it;
  for (it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &v) {
  os << "[";
  typename set<T>::const_iterator it;
  for (it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}
template <typename F, typename S>
ostream &operator<<(ostream &os, const map<F, S> &v) {
  os << "[";
  typename map<F, S>::const_iterator it;
  for (it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << it->first << " = " << it->second;
  }
  return os << "]";
}
template <class T>
void deb_array(T *arr, int length) {
  for (int i = 0; i < length; i++) {
    cout << arr[i] << ' ';
  }
  cout << '\n';
}
const int maxn = 2e5 + 5;
int n, q;
long long a[maxn];
struct RMQ {
  long long a[maxn], lazy[4 * maxn], seg[4 * maxn];
  void build(int x, int st, int en) {
    if (st == en) {
      seg[x] = a[st];
      return;
    }
    int mid = (st + en) >> 1;
    build(2 * x, st, mid);
    build(2 * x + 1, mid + 1, en);
    seg[x] = min(seg[2 * x], seg[2 * x + 1]);
  }
  void push(int x, int st, int en) {
    if (lazy[x]) {
      seg[x] += lazy[x];
      if (st != en) {
        lazy[2 * x] += lazy[x];
        lazy[2 * x + 1] += lazy[x];
      }
      lazy[x] = 0;
    }
  }
  void update(int x, int st, int en, int l, int r, long long val) {
    push(x, st, en);
    if (r < st || en < l) {
      return;
    }
    if (l <= st && en <= r) {
      lazy[x] += val;
      push(x, st, en);
      return;
    }
    int mid = (st + en) >> 1;
    update(2 * x, st, mid, l, r, val);
    update(2 * x + 1, mid + 1, en, l, r, val);
    seg[x] = min(seg[2 * x], seg[2 * x + 1]);
  }
  long long query(int x, int st, int en, int l, int r) {
    push(x, st, en);
    if (r < st || en < l) {
      return INF;
    }
    if (l <= st && en <= r) {
      return seg[x];
    }
    int mid = (st + en) >> 1;
    return min(query(2 * x, st, mid, l, r),
               query(2 * x + 1, mid + 1, en, l, r));
  }
} rmq;
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%I64d", a + i);
    rmq.update(1, 0, n - 1, i, i, a[i]);
  }
  char s[1024];
  int l, r;
  long long val;
  scanf("%d ", &q);
  for (int i = 0; i < q; i++) {
    gets(s);
    if (sscanf(s, "%d %d %I64d", &l, &r, &val) == 3) {
      if (l <= r) {
        rmq.update(1, 0, n - 1, l, r, val);
      } else {
        rmq.update(1, 0, n - 1, l, n - 1, val);
        rmq.update(1, 0, n - 1, 0, r, val);
      }
    } else {
      if (l <= r) {
        printf("%I64d\n", rmq.query(1, 0, n - 1, l, r));
      } else {
        printf("%I64d\n", min(rmq.query(1, 0, n - 1, l, n - 1),
                              rmq.query(1, 0, n - 1, 0, r)));
      }
    }
  }
  return 0;
}
