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>
template <typename NumType>
struct Lazy_Segment_Tree {
  struct segment {
    int start, end;
  };

 public:
  Lazy_Segment_Tree(std::vector<NumType> const& v) : leaves(v) {
    num_leaves = v.size();
    size_t m = size_t(1) << static_cast<size_t>(ceil(log2(num_leaves)));
    tree_size = 2 * m - 1;
    segtree.resize(tree_size, 0);
    laztree.resize(tree_size, 0);
    build(root_segment(), 0);
  }
  int64_t circular_rmq(int q_left, int q_right) {
    if (q_left > q_right)
      return std::min(circular_rmq(q_left, num_leaves - 1),
                      circular_rmq(0, q_right));
    return rmq(q_left, q_right, root_segment(), 0);
  }
  void circular_add(int q_left, int q_right, int64_t val) {
    if (q_left > q_right) {
      add(q_left, num_leaves - 1, root_segment(), 0, val);
      add(0, q_right, root_segment(), 0, val);
    } else
      add(q_left, q_right, root_segment(), 0, val);
  }
  void print_tree() {
    for (auto el : segtree) std::cout << el << " ";
    std::cout << std::endl;
  }

 private:
  std::vector<NumType> segtree;
  std::vector<NumType> laztree;
  std::vector<NumType> leaves;
  int num_leaves;
  int tree_size;
  void build(segment const& node_segment, int current) {
    int start = node_segment.start;
    int end = node_segment.end;
    if (start == end) {
      segtree[current] = leaves[start];
      return;
    }
    int mid = (start + end) / 2;
    build(segment{start, mid}, (2 * current + 1));
    build(segment{mid + 1, end}, (2 * current + 2));
    segtree[current] =
        std::min(segtree[(2 * current + 1)], segtree[(2 * current + 2)]);
  }
  segment root_segment() { return segment{0, (num_leaves - 1)}; }
  void manage_lazy_tree(segment node_range, int current) {
    if (laztree[current] != 0) {
      segtree[current] += laztree[current];
      if (node_range.start != node_range.end) {
        laztree[(2 * current + 1)] += laztree[current];
        laztree[(2 * current + 2)] += laztree[current];
      }
      laztree[current] = 0;
    }
  }
  int64_t rmq(int q_left, int q_right, segment const& node_range, int current) {
    manage_lazy_tree(node_range, current);
    if (node_range.start > q_right || node_range.end < q_left ||
        node_range.start > node_range.end)
      return INT64_MAX;
    if (node_range.start >= q_left && node_range.end <= q_right)
      return segtree[current];
    int mid = (node_range.start + node_range.end) / 2;
    return std::min(
        rmq(q_left, q_right, segment{node_range.start, mid}, (2 * current + 1)),
        rmq(q_left, q_right, segment{mid + 1, node_range.end},
            (2 * current + 2)));
  }
  void add(int q_left, int q_right, segment const& node_range, int current,
           int64_t val) {
    manage_lazy_tree(node_range, current);
    if (node_range.start > q_right || node_range.end < q_left) return;
    if (node_range.start >= q_left && node_range.end <= q_right) {
      segtree[current] += val;
      if (node_range.start != node_range.end) {
        laztree[(2 * current + 1)] += val;
        laztree[(2 * current + 2)] += val;
      }
    } else {
      int mid = (node_range.start + node_range.end) / 2;
      add(q_left, q_right, segment{node_range.start, mid}, (2 * current + 1),
          val);
      add(q_left, q_right, segment{mid + 1, node_range.end}, (2 * current + 2),
          val);
      segtree[current] =
          std::min(segtree[(2 * current + 1)], segtree[(2 * current + 2)]);
    }
  }
};
std::vector<std::string> split(std::string str, char delimiter) {
  std::vector<std::string> internal;
  std::stringstream ss(str);
  std::string token;
  while (getline(ss, token, delimiter)) {
    internal.push_back(token);
  }
  return internal;
}
int main() {
  std::ios_base::sync_with_stdio(false);
  size_t n, m;
  std::cin >> n;
  std::vector<int64_t> input(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> input[i];
  }
  Lazy_Segment_Tree<int64_t> rmq_segtree(input);
  std::cin >> m;
  std::string query;
  for (size_t i = 0; i <= m; ++i) {
    std::getline(std::cin, query);
    std::vector<std::string> splitted_query = split(query, ' ');
    if (splitted_query.size() == 2)
      std::cout << rmq_segtree.circular_rmq(std::stoi(splitted_query[0]),
                                            std::stoi(splitted_query[1]))
                << std::endl;
    else if (splitted_query.size() == 3)
      rmq_segtree.circular_add(std::stoi(splitted_query[0]),
                               std::stoi(splitted_query[1]),
                               std::stoi(splitted_query[2]));
  }
  return 0;
}
