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>
#pragma GCC optimize("Ofast")
using namespace std;
using i64 = long long;
using i32 = int;
using f64 = long double;
template <class Key>
using vec = vector<Key>;
template <class Key>
using hash_set = unordered_set<Key>;
template <class Key, class Value>
using hash_map = unordered_map<Key, Value>;
using str = string;
template <size_t Size1>
using a64 = array<i64, Size1>;
template <size_t Size1, size_t Size2>
using aa64 = array<a64<Size2>, Size1>;
using p64 = pair<i64, i64>;
using v64 = vec<i64>;
using vv64 = vec<v64>;
using s64 = set<i64>;
using m64 = map<i64, i64>;
mt19937 gen(998244353);
const i64 inf = numeric_limits<i64>::max() / 2;
template <class T>
inline i64 len(const T& a) {
  return (i64)(a.size());
}
inline void fast() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); }
template <class T, class S>
inline bool check_min(T& a, S b) {
  if (a > b) return a = b, 1;
  return 0;
}
template <class T, class S>
inline bool check_max(T& a, S b) {
  if (a < b) return a = b, 1;
  return 0;
}
void read() {}
void print() {}
void println() { cout << "\n"; }
template <class T, class... U>
void read(T& a, U&... b) {
  cin >> a;
  read(b...);
}
template <class T, class... U>
void print(const T& a, const U&... b) {
  cout << a << " ";
  print(b...);
}
template <class T, class... U>
void println(const T& a, const U&... b) {
  cout << a << " ";
  println(b...);
}
struct Problem {
  void files(str in, str out) {
    freopen(in.c_str(), "r", stdin), freopen(out.c_str(), "w", stdout);
  }
  void solve(), input();
  void many() {
    i64 t;
    read(t);
    while (t--) input(), solve();
  }
  void make(bool mt = 0) {
    if (mt)
      many();
    else
      input(), solve();
  }
} problem;
signed main() {
  fast();
  problem.make();
  return 0;
}
struct SegmentTree {
  struct Node {
    i64 min = inf;
    i64 push = 0;
  };
  i32 n;
  vec<Node> t;
  SegmentTree() {}
  SegmentTree(i32 n_) {
    i32 k = log2(n_) + 1;
    n = 1l << k;
    t.resize(2 * n);
  }
  void build(v64& a) {
    for (i32 i = 0; i < len(a); i++) {
      t[n + i].min = a[i];
    }
    for (i32 i = n - 1; i >= 0; i--) {
      t[i].min = min(t[2 * i].min, t[2 * i + 1].min);
    }
  }
  void push(i32 v) {
    if (!t[v].push) return;
    t[v].min += t[v].push;
    if (v < n) {
      t[2 * v].push += t[v].push;
      t[2 * v + 1].push += t[v].push;
    }
    t[v].push = 0;
  }
  void _upd(i32 v, i32 tl, i32 tr, i32 l, i32 r, i64 x) {
    push(v);
    if (tl > r || tr < l) {
      return;
    }
    if (l <= tl && tr <= r) {
      t[v].push += x;
      push(v);
      return;
    }
    i32 tm = (tl + tr) / 2;
    _upd(2 * v, tl, tm, l, r, x);
    _upd(2 * v + 1, tm + 1, tr, l, r, x);
    t[v].min = min(t[2 * v].min, t[2 * v + 1].min);
  }
  i64 _get(i32 v, i32 tl, i32 tr, i32 l, i32 r) {
    push(v);
    if (tl > r || tr < l) {
      return inf;
    }
    if (l <= tl && tr <= r) {
      return t[v].min;
    }
    i32 tm = (tl + tr) / 2;
    i64 g1 = _get(2 * v, tl, tm, l, r);
    i64 g2 = _get(2 * v + 1, tm + 1, tr, l, r);
    return min(g1, g2);
  }
  void upd(i32 l, i32 r, i32 x) { _upd(1, 0, n - 1, l, r, x); }
  i64 get(i32 l, i32 r) {
    i64 ans = _get(1, 0, n - 1, l, r);
    return ans;
  }
};
i64 n, m;
v64 a;
SegmentTree st;
void qu1(i64 l, i64 r, i64 x) {
  vec<p64> ps;
  if (l <= r) {
    ps.push_back({l, r});
  } else {
    ps.push_back({l, n - 1});
    ps.push_back({0, r});
  }
  for (p64 p : ps) {
    st.upd(p.first, p.second, x);
  }
}
i64 qu2(i64 l, i64 r) {
  vec<p64> ps;
  if (l <= r) {
    ps.push_back({l, r});
  } else {
    ps.push_back({l, n - 1});
    ps.push_back({0, r});
  }
  i64 ans = inf;
  for (p64 p : ps) {
    check_min(ans, st.get(p.first, p.second));
  }
  return ans;
}
void Problem::solve() {
  st = SegmentTree(n);
  st.build(a);
  for (i32(i) = 0; (i) < (m); (i)++) {
    i64 l, r;
    read(l, r);
    char c = cin.peek();
    if (c == ' ') {
      i64 x;
      read(x);
      qu1(l, r, x);
    } else {
      i64 ans = qu2(l, r);
      println(ans);
    }
  }
}
void Problem::input() {
  read(n);
  a.resize(n);
  for (i32(i) = 0; (i) < (n); (i)++) {
    read(a[i]);
  }
  read(m);
}
