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;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
vector<long long int> v;
vector<long long int> w, ab, bc;
set<long long int> uo;
map<long long int, long long int> ww, cc, u;
vector<pair<long long int, long long int> > uu, su;
map<long long int, vector<long long int> > uuu;
map<pair<long long int, long long int>, long long int> vo;
map<pair<long long int, long long int>, long long int> vu;
map<long long int, pair<long long int, pair<long long int, long long int> > >
    vs;
priority_queue<long long int, vector<long long int>, greater<long long int> >
    moy;
long long int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
long long int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
long long int dxx[] = {2, 1, -1, -2, -2, -1, 1, 2};
long long int dyy[] = {1, 2, 2, 1, -1, -2, -2, -1};
long long int dp[101][10001];
long long int ar[10][10];
long long int seg[4 * 200005], laz[4 * 200005];
long long int answer(long long int a, long long int b) { return min(a, b); }
long long int make(long long int a, long long int b) { return a + b; }
long long int mndm = 4e18;
void prop(long long int n, long long int s, long long int e) {
  laz[n * 2] = make(laz[n * 2], laz[n]);
  laz[n * 2 + 1] = make(laz[n * 2 + 1], laz[n]);
  long long int mid = (s + e) / 2;
  seg[n * 2] = make(seg[n * 2], laz[n]);
  seg[n * 2 + 1] = make(seg[n * 2 + 1], laz[n]);
  laz[n] = 0;
  return;
}
void build(long long int n, long long int s, long long int e) {
  if (s == e) {
    seg[n] = v[s];
    return;
  }
  long long int mid = (s + e) / 2;
  build(n * 2, s, mid);
  build(n * 2 + 1, mid + 1, e);
  seg[n] = answer(seg[n * 2], seg[n * 2 + 1]);
  return;
}
void up(long long int n, long long int s, long long int e, long long int l,
        long long int r, long long int val) {
  if (s >= l && e <= r) {
    seg[n] = make(seg[n], val);
    laz[n] = make(laz[n], val);
    return;
  }
  if (s > r || e < l) return;
  long long int mid = (s + e) / 2;
  if (laz[n] != 0) prop(n, s, e);
  up(n * 2, s, mid, l, r, val);
  up(n * 2 + 1, mid + 1, e, l, r, val);
  seg[n] = answer(seg[n * 2], seg[n * 2 + 1]);
  return;
}
long long int query(long long int n, long long int s, long long int e,
                    long long int l, long long int r) {
  if (s >= l && e <= r) return seg[n];
  if (s > r || e < l) return mndm;
  long long int mid = (s + e) / 2;
  if (laz[n] != 0) prop(n, s, e);
  long long int p = query(n * 2, s, mid, l, r);
  long long int q = query(n * 2 + 1, mid + 1, e, l, r);
  return answer(p, q);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  char ch;
  string a, b, c;
  double x, y, d, e, f, g, h;
  long long int n, i, j, k, p, q, o, l, s, tt = 1, m, t, z, aa, r = 0;
  for (long long int mau = 1; mau <= tt; mau++) {
    v.clear();
    w.clear();
    ww.clear();
    uu.clear();
    uo.clear();
    vo.clear();
    vu.clear();
    ab.clear();
    bc.clear();
    cc.clear();
    uuu.clear();
    a.clear();
    b.clear();
    c.clear();
    u.clear();
    cin >> n;
    for (i = 0; i <= 4 * n; i++) {
      seg[i] = 0;
      laz[i] = 0;
    }
    v.push_back(-1);
    for (i = 0; i < n; i++) {
      cin >> o;
      v.push_back(o);
    }
    cin >> m;
    build(1, 1, n);
    cin.ignore();
    while (m--) {
      getline(cin, a);
      stringstream ss(a);
      w.clear();
      while (ss >> b) {
        stringstream ss1(b);
        ss1 >> o;
        w.push_back(o);
      }
      if (w.size() == 3) {
        if (w[0] > w[1]) {
          up(1, 1, n, w[0] + 1, n, w[2]);
          up(1, 1, n, 1, w[1] + 1, w[2]);
          continue;
        }
        up(1, 1, n, w[0] + 1, w[1] + 1, w[2]);
      } else {
        if (w[0] > w[1]) {
          cout << min(query(1, 1, n, w[0] + 1, n), query(1, 1, n, 1, w[1] + 1))
               << "\n";
          continue;
        }
        cout << query(1, 1, n, w[0] + 1, w[1] + 1) << "\n";
      }
    }
  }
  return 0;
}
