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 seg[200000 * 4];
long long lazy[200000 * 4];
int v[200001];
int n, q;
void B(int n, int s, int e) {
  if (s == e)
    seg[n] = v[s];
  else {
    int mid = s + e;
    mid /= 2;
    B(n * 2, s, mid);
    B(n * 2 + 1, mid + 1, e);
    seg[n] = min(seg[n * 2], seg[n * 2 + 1]);
  }
}
void update(int n, int s, int e, int l, int r, int v) {
  if (lazy[n] != 0) {
    seg[n] += lazy[n];
    if (s != e) lazy[n * 2] += lazy[n], lazy[n * 2 + 1] += lazy[n];
    lazy[n] = 0;
  }
  if (r < s || l > e) return;
  if (l <= s && e <= r) {
    seg[n] += (long long)v;
    if (s != e) lazy[n * 2] += (long long)v, lazy[n * 2 + 1] += (long long)v;
    return;
  }
  int mid = s + e;
  mid /= 2;
  update(n * 2, s, mid, l, r, v);
  update(n * 2 + 1, mid + 1, e, l, r, v);
  seg[n] = min(seg[n * 2], seg[n * 2 + 1]);
}
long long query(int n, int s, int e, int l, int r) {
  if (lazy[n] != 0) {
    seg[n] += lazy[n];
    if (s != e) lazy[n * 2] += lazy[n], lazy[n * 2 + 1] += lazy[n];
    lazy[n] = 0;
  }
  if (s > r || e < l) return 1e18;
  if (l <= s && r >= e) return seg[n];
  int mid = s + e;
  mid /= 2;
  return min(query(n * 2, s, mid, l, r), query(n * 2 + 1, mid + 1, e, l, r));
}
vector<int> get(string line) {
  string tmp;
  vector<int> v;
  for (int i = 0; i < line.size(); i++) {
    if (line[i] == ' ') {
      int d = 0;
      for (int i = 0; i < tmp.size(); ++i) d = d * 10 + (tmp[i] - '0');
      v.push_back(d);
      tmp = "";
    } else {
      tmp += line[i];
    }
  }
  int p = 1;
  int d = 0;
  for (int i = 0; i < tmp.size(); ++i)
    if (tmp[i] == '-')
      p = -1;
    else
      d = d * 10 + (tmp[i] - '0');
  v.push_back(p * d);
  return v;
}
int main() {
  scanf("%d", &n);
  memset(seg, 0, sizeof(seg));
  memset(lazy, 0, sizeof(lazy));
  for (int i = 0; i < n; ++i) scanf("%d", v + i);
  B(1, 0, n - 1);
  scanf("%d", &q);
  cin.ignore();
  while (q--) {
    string line;
    getline(cin, line);
    vector<int> v = get(line);
    int left = v[0];
    int right = v[1];
    if (v.size() == 3) {
      long long val = v[2];
      if (left <= right)
        update(1, 0, n - 1, left, right, val);
      else {
        update(1, 0, n - 1, 0, right, val);
        update(1, 0, n - 1, left, n - 1, val);
      }
    } else {
      long long ans;
      if (left <= right)
        ans = query(1, 0, n - 1, left, right);
      else
        ans =
            min(query(1, 0, n - 1, 0, right), query(1, 0, n - 1, left, n - 1));
      printf("%I64d\n", ans);
    }
  }
}
