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;
long long st[2 * 200050], lazy[2 * 200050];
long long a[200050];
long long left(long long idx) { return idx + 1; }
long long right(long long idx, long long l, long long r) {
  long long mid = (l + r) / 2;
  return (idx + 2 * (mid - l + 1));
}
void push_down(long long i, long long l, long long r, long long value) {
  if (l != r) {
    lazy[left(i)] += value;
    lazy[right(i, l, r)] += value;
  }
}
long long query(long long i, long long l, long long r, long long ql,
                long long qr) {
  if (l > r || ql > r || qr < l) {
    return 99999999999999999LL;
  }
  if (lazy[i] != 0) {
    st[i] += lazy[i];
    push_down(i, l, r, lazy[i]);
    lazy[i] = 0;
  }
  if (ql <= l && qr >= r) {
    return st[i];
  }
  long long mid = (l + r) / 2;
  return min(query(left(i), l, mid, ql, qr),
             query(right(i, l, r), mid + 1, r, ql, qr));
}
void lazy_update(long long i, long long l, long long r, long long ul,
                 long long ur, long long value) {
  if (l > r) {
    return;
  }
  if (lazy[i] != 0) {
    st[i] += lazy[i];
    push_down(i, l, r, lazy[i]);
    lazy[i] = 0;
  }
  if (ul > r || ur < l) {
    return;
  }
  if (ul <= l && ur >= r) {
    st[i] += value;
    push_down(i, l, r, value);
    return;
  }
  long long mid = (l + r) / 2;
  lazy_update(left(i), l, mid, ul, ur, value);
  lazy_update(right(i, l, r), mid + 1, r, ul, ur, value);
  st[i] = min(st[left(i)], st[right(i, l, r)]);
}
void build(long long idx, long long l, long long r) {
  if (l > r) {
    return;
  }
  if (l == r) {
    st[idx] = a[l];
    return;
  }
  long long mid = (l + r) / 2;
  build(left(idx), l, mid);
  build(right(idx, l, r), mid + 1, r);
  st[idx] = min(st[left(idx)], st[right(idx, l, r)]);
}
vector<long long> take_input() {
  string input;
  getline(cin, input);
  long long word;
  stringstream s(input);
  vector<long long> vv;
  while (s >> word) {
    vv.push_back(word);
  }
  return vv;
}
long long format(long long l, long long r, long long n) {
  if (l > r) {
    return r + n;
  }
  return r;
}
void solve() {
  long long n;
  string input;
  getline(cin, input);
  n = stoi(input);
  getline(cin, input);
  stringstream s(input);
  int i = 0;
  while (s >> a[i]) {
    i++;
  }
  for (i = 0; i < 2 * n; i++) {
    lazy[i] = 0;
  }
  long long m;
  getline(cin, input);
  m = stoi(input);
  build(0, 0, n - 1);
  for (i = 0; i < m; i++) {
    vector<long long> vec = take_input();
    if ((int)vec.size() == 3) {
      if (vec[0] > vec[1]) {
        lazy_update(0, 0, n - 1, vec[0], n - 1, vec[2]);
        lazy_update(0, 0, n - 1, 0, vec[1], vec[2]);
      } else {
        lazy_update(0, 0, n - 1, vec[0], vec[1], vec[2]);
      }
    } else {
      if (vec[0] > vec[1]) {
        cout << min(query(0, 0, n - 1, vec[0], n - 1),
                    query(0, 0, n - 1, 0, vec[1]))
             << endl;
      } else {
        cout << query(0, 0, n - 1, vec[0], vec[1]) << endl;
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
