#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 239 + 1329;
struct segment_tree {
  int size;
  vector<int> t;
  vector<int> mod;
  void pull(int v) { t[v] = min(t[2 * v + 1], t[2 * v + 2]); }
  void update(int v, int val) {
    t[v] = val;
    mod[v] = val;
  }
  void push(int v) {
    if (mod[v] != 0) {
      update(2 * v + 1, mod[v]);
      update(2 * v + 2, mod[v]);
      mod[v] = 0;
    }
  }
  void build(int v, int l, int r, const vector<int> &a) {
    if (l + 1 == r) {
      t[v] = a[l];
    } else {
      int m = (r + l) >> 1;
      build(2 * v + 1, l, m, a);
      build(2 * v + 2, m, r, a);
      pull(v);
    }
  }
  segment_tree(const vector<int> &a) {
    size = (int)a.size();
    t.resize(4 * size);
    mod.resize(4 * size, 0);
    build(0, 0, size, a);
  }
  int query(int v, int l, int r, int ql, int qr) {
    if (ql >= r || qr <= l) {
      return inf;
    }
    if (ql <= l && r <= qr) {
      return t[v];
    } else {
      push(v);
      int m = (r + l) >> 1;
      auto f = query(2 * v + 1, l, m, ql, qr);
      auto s = query(2 * v + 2, m, r, ql, qr);
      return min(f, s);
    }
  }
  int query(int l, int r) { return query(0, 0, size, l, r); }
  void modify(int v, int l, int r, int ql, int qr, int val) {
    if (qr <= l || ql >= r) {
      return;
    }
    if (ql <= l && r <= qr) {
      update(v, val);
    } else {
      push(v);
      int m = (r + l) >> 1;
      modify(2 * v + 1, l, m, ql, qr, val);
      modify(2 * v + 2, m, r, ql, qr, val);
      pull(v);
    }
  }
  void modify(int l, int r, int val) { modify(0, 0, size, l, r, val); }
};
int n, k;
vector<tuple<int, int, int, int>> query_all;
vector<tuple<int, int, int>> query_mod;
vector<pair<int, int>> query_min;
vector<int> seen_ind;
map<int, int> new_ind;
vector<int> b;
vector<int> c;
void zip_ind() {
  sort(seen_ind.begin(), seen_ind.end());
  seen_ind.resize(unique(seen_ind.begin(), seen_ind.end()) - seen_ind.begin());
  int cur = 0;
  for (auto t : seen_ind) {
    new_ind[t] = cur;
    cur++;
  }
}
void zip() {
  zip_ind();
  segment_tree cur(b);
  c.resize(seen_ind.size());
  for (int i = 1; i < (int)seen_ind.size(); i++) {
    if (seen_ind[i] - seen_ind[i - 1] + 1 >= n) {
      c[i - 1] = cur.query(0, n);
    } else {
      int nl = (seen_ind[i - 1] - 1) % n;
      int nr = (seen_ind[i] - 1) % n;
      if (nr >= nl) {
        c[i - 1] = cur.query(nl, nr);
      } else {
        auto f = cur.query(nl, n);
        auto s = cur.query(0, nr);
        c[i - 1] = min(f, s);
      }
    }
  }
  c.back() = inf;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  b.resize(n);
  for (auto &t : b) {
    cin >> t;
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int tp, l, r;
    int x = -1;
    cin >> tp;
    if (tp == 1) {
      cin >> l >> r >> x;
      r++;
      query_mod.push_back(make_tuple(l, r, x));
    } else {
      cin >> l >> r;
      r++;
      query_min.push_back({l, r});
    }
    query_all.push_back(make_tuple(tp, l, r, x));
    seen_ind.push_back(l);
    seen_ind.push_back(r);
  }
  zip();
  segment_tree cur(c);
  for (auto t : query_all) {
    if (get<0>(t) == 1) {
      int l = get<1>(t);
      int r = get<2>(t);
      int x = get<3>(t);
      int nl = new_ind[l];
      int nr = new_ind[r];
      cur.modify(nl, nr, x);
    } else {
      int l = get<1>(t);
      int r = get<2>(t);
      int nl = new_ind[l];
      int nr = new_ind[r];
      cout << cur.query(nl, nr) << '\n';
    }
  }
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

You are given an array a consisting of positive integers and q queries to this array. There are two types of queries: 

  * 1 l r x — for each index i such that l ≤ i ≤ r set ai = x. 
  * 2 l r — find the minimum among such ai that l ≤ i ≤ r. 



We decided that this problem is too easy. So the array a is given in a compressed form: there is an array b consisting of n elements and a number k in the input, and before all queries a is equal to the concatenation of k arrays b (so the size of a is n·k).

Input

The first line contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 104).

The second line contains n integers — elements of the array b (1 ≤ bi ≤ 109).

The third line contains one integer q (1 ≤ q ≤ 105).

Then q lines follow, each representing a query. Each query is given either as 1 l r x — set all elements in the segment from l till r (including borders) to x (1 ≤ l ≤ r ≤ n·k, 1 ≤ x ≤ 109) or as 2 l r — find the minimum among all elements in the segment from l till r (1 ≤ l ≤ r ≤ n·k).

Output

For each query of type 2 print the answer to this query — the minimum on the corresponding segment.

Examples

Input

3 1
1 2 3
3
2 1 3
1 1 2 4
2 1 3


Output

1
3


Input

3 2
1 2 3
5
2 4 4
1 4 4 5
2 4 4
1 1 6 1
2 6 6


Output

1
5
1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 239 + 1329;
struct segment_tree {
  int size;
  vector<int> t;
  vector<int> mod;
  void pull(int v) { t[v] = min(t[2 * v + 1], t[2 * v + 2]); }
  void update(int v, int val) {
    t[v] = val;
    mod[v] = val;
  }
  void push(int v) {
    if (mod[v] != 0) {
      update(2 * v + 1, mod[v]);
      update(2 * v + 2, mod[v]);
      mod[v] = 0;
    }
  }
  void build(int v, int l, int r, const vector<int> &a) {
    if (l + 1 == r) {
      t[v] = a[l];
    } else {
      int m = (r + l) >> 1;
      build(2 * v + 1, l, m, a);
      build(2 * v + 2, m, r, a);
      pull(v);
    }
  }
  segment_tree(const vector<int> &a) {
    size = (int)a.size();
    t.resize(4 * size);
    mod.resize(4 * size, 0);
    build(0, 0, size, a);
  }
  int query(int v, int l, int r, int ql, int qr) {
    if (ql >= r || qr <= l) {
      return inf;
    }
    if (ql <= l && r <= qr) {
      return t[v];
    } else {
      push(v);
      int m = (r + l) >> 1;
      auto f = query(2 * v + 1, l, m, ql, qr);
      auto s = query(2 * v + 2, m, r, ql, qr);
      return min(f, s);
    }
  }
  int query(int l, int r) { return query(0, 0, size, l, r); }
  void modify(int v, int l, int r, int ql, int qr, int val) {
    if (qr <= l || ql >= r) {
      return;
    }
    if (ql <= l && r <= qr) {
      update(v, val);
    } else {
      push(v);
      int m = (r + l) >> 1;
      modify(2 * v + 1, l, m, ql, qr, val);
      modify(2 * v + 2, m, r, ql, qr, val);
      pull(v);
    }
  }
  void modify(int l, int r, int val) { modify(0, 0, size, l, r, val); }
};
int n, k;
vector<tuple<int, int, int, int>> query_all;
vector<tuple<int, int, int>> query_mod;
vector<pair<int, int>> query_min;
vector<int> seen_ind;
map<int, int> new_ind;
vector<int> b;
vector<int> c;
void zip_ind() {
  sort(seen_ind.begin(), seen_ind.end());
  seen_ind.resize(unique(seen_ind.begin(), seen_ind.end()) - seen_ind.begin());
  int cur = 0;
  for (auto t : seen_ind) {
    new_ind[t] = cur;
    cur++;
  }
}
void zip() {
  zip_ind();
  segment_tree cur(b);
  c.resize(seen_ind.size());
  for (int i = 1; i < (int)seen_ind.size(); i++) {
    if (seen_ind[i] - seen_ind[i - 1] + 1 >= n) {
      c[i - 1] = cur.query(0, n);
    } else {
      int nl = (seen_ind[i - 1] - 1) % n;
      int nr = (seen_ind[i] - 1) % n;
      if (nr >= nl) {
        c[i - 1] = cur.query(nl, nr);
      } else {
        auto f = cur.query(nl, n);
        auto s = cur.query(0, nr);
        c[i - 1] = min(f, s);
      }
    }
  }
  c.back() = inf;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  b.resize(n);
  for (auto &t : b) {
    cin >> t;
  }
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int tp, l, r;
    int x = -1;
    cin >> tp;
    if (tp == 1) {
      cin >> l >> r >> x;
      r++;
      query_mod.push_back(make_tuple(l, r, x));
    } else {
      cin >> l >> r;
      r++;
      query_min.push_back({l, r});
    }
    query_all.push_back(make_tuple(tp, l, r, x));
    seen_ind.push_back(l);
    seen_ind.push_back(r);
  }
  zip();
  segment_tree cur(c);
  for (auto t : query_all) {
    if (get<0>(t) == 1) {
      int l = get<1>(t);
      int r = get<2>(t);
      int x = get<3>(t);
      int nl = new_ind[l];
      int nr = new_ind[r];
      cur.modify(nl, nr, x);
    } else {
      int l = get<1>(t);
      int r = get<2>(t);
      int nl = new_ind[l];
      int nr = new_ind[r];
      cout << cur.query(nl, nr) << '\n';
    }
  }
}

```