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 shift = 1 << 18;
int n, m;
long long t[2 * shift + 500];
long long add[2 * shift + 500];
long long pl(int l) {
  if (l == 1) return add[1];
  return add[l] + pl(l / 2);
}
void check(int q) {
  if (q > 0) {
    t[q] = min(t[2 * q] + add[2 * q], t[2 * q + 1] + add[2 * q + 1]);
    check(q / 2);
  }
}
long long minf(int l, int r) {
  if (l > r) return 1LL << 60;
  if (l % 2 == 1) return min(t[l] + pl(l), minf(l + 1, r));
  if (r % 2 == 0) return min(t[r] + pl(r), minf(l, r - 1));
  return minf(l / 2, r / 2);
}
void ad(int l, int r, long long sum) {
  if (l > r) return;
  if (l % 2 == 1) {
    add[l] += sum;
    check(l / 2);
    l++;
    ad(l, r, sum);
    return;
  }
  if (r % 2 == 0) {
    add[r] += sum;
    check(r / 2);
    r--;
    ad(l, r, sum);
    return;
  }
  ad(l / 2, r / 2, sum);
}
int main() {
  cin >> n;
  int i;
  for (i = shift; i < n + shift; i++) cin >> t[i];
  i = shift - 1;
  while (i > 0) {
    t[i] = min(t[2 * i], t[2 * i + 1]);
    i--;
  }
  cin >> m;
  for (i = 0; i < m; i++) {
    int q, w;
    long long e;
    cin >> q >> w;
    if (getchar() == ' ') {
      cin >> e;
      if (w >= q)
        ad(q + shift, w + shift, e);
      else {
        ad(q + shift, shift + n - 1, e);
        ad(shift, shift + w, e);
      }
    } else {
      if (q <= w)
        cout << minf(q + shift, w + shift) << endl;
      else
        cout << min(minf(q + shift, shift + n - 1), minf(shift, shift + w))
             << endl;
    }
  }
  return 0;
}
