#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
class ST {
 public:
  int size;
  vector<int> t;
  vector<int> add;
  ST(int n = 0) : t(n * 4, INF), add(n * 4, 0), size(n) {}
  void push(int i) {
    if (!add[i]) return;
    t[i] = add[i];
    if (2 * i + 2 < (int)t.size()) {
      add[2 * i + 1] = add[i];
      add[2 * i + 2] = add[i];
    }
    add[i] = 0;
  }
  void upd(int i, int a, int b, int l, int r, int x) {
    push(i);
    if (a == l && b == r) {
      add[i] = x;
      return;
    }
    int m = (l + r) / 2;
    if (a <= m) upd(2 * i + 1, a, min(m, b), l, m, x);
    if (m + 1 <= b) upd(2 * i + 2, max(a, m + 1), b, m + 1, r, x);
    push(2 * i + 1);
    push(2 * i + 2);
    t[i] = min(t[2 * i + 1], t[2 * i + 2]);
  }
  void upd(int a, int b, int x) { upd(0, a, b - 1, 0, size - 1, x); }
  int get(int i, int a, int b, int l, int r) {
    push(i);
    if (a == l && b == r) return t[i];
    int minl = INF;
    int minr = INF;
    int m = (l + r) / 2;
    if (a <= m) minl = get(2 * i + 1, a, min(m, b), l, m);
    if (m + 1 <= b) minr = get(2 * i + 2, max(a, m + 1), b, m + 1, r);
    return min(minl, minr);
  }
  int get(int a, int b) {
    if (a == b)
      return INF;
    else
      return get(0, a, b - 1, 0, size - 1);
  }
};
typedef struct {
  int t;
  int l;
  int r;
  int x;
} node;
node c[100006];
int w[100006], n, k, q, cnt;
vector<int> mark;
map<int, int> ss;
ST origin;
int originrangemin(int a, int b) {
  if (a - b >= n) return origin.get(0, n);
  a %= n;
  b = (b - 1) % n + 1;
  if (a < b)
    return origin.get(a, b);
  else if (a > b)
    return min(origin.get(a, n), origin.get(0, b));
  return 0;
}
int main() {
  cin >> n >> k;
  origin = ST(n);
  for (int i = 0; i < n; i++) {
    cin >> w[i];
    origin.upd(i, i + 1, w[i]);
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> c[i].t;
    if (c[i].t == 1)
      cin >> c[i].l >> c[i].r >> c[i].x;
    else
      cin >> c[i].l >> c[i].r;
    mark.push_back(c[i].l - 1);
    mark.push_back(c[i].r - 1);
  }
  sort(mark.begin(), mark.end());
  cnt = unique(mark.begin(), mark.end()) - mark.begin();
  mark.resize(cnt);
  ST work(mark.size() * 2);
  int last = -1, s_cnt = 0;
  for (int i = 0; i < cnt; i++) {
    int tmp;
    if (mark[i] - last > 1) {
      tmp = originrangemin(last + 1, mark[i]);
      work.upd(s_cnt, s_cnt + 1, tmp);
      s_cnt++;
    }
    tmp = originrangemin(mark[i], mark[i] + 1);
    work.upd(s_cnt, s_cnt + 1, tmp);
    ss[mark[i]] = s_cnt;
    s_cnt++;
    last = mark[i];
  }
  for (int i = 0; i < q; i++)
    if (c[i].t == 1)
      work.upd(ss[c[i].l - 1], ss[c[i].r - 1] + 1, c[i].x);
    else
      cout << work.get(ss[c[i].l - 1], ss[c[i].r - 1] + 1) << endl;
  return 0;
}

### Prompt

Please create a solution in CPP 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 = 0x3f3f3f3f;
class ST {
 public:
  int size;
  vector<int> t;
  vector<int> add;
  ST(int n = 0) : t(n * 4, INF), add(n * 4, 0), size(n) {}
  void push(int i) {
    if (!add[i]) return;
    t[i] = add[i];
    if (2 * i + 2 < (int)t.size()) {
      add[2 * i + 1] = add[i];
      add[2 * i + 2] = add[i];
    }
    add[i] = 0;
  }
  void upd(int i, int a, int b, int l, int r, int x) {
    push(i);
    if (a == l && b == r) {
      add[i] = x;
      return;
    }
    int m = (l + r) / 2;
    if (a <= m) upd(2 * i + 1, a, min(m, b), l, m, x);
    if (m + 1 <= b) upd(2 * i + 2, max(a, m + 1), b, m + 1, r, x);
    push(2 * i + 1);
    push(2 * i + 2);
    t[i] = min(t[2 * i + 1], t[2 * i + 2]);
  }
  void upd(int a, int b, int x) { upd(0, a, b - 1, 0, size - 1, x); }
  int get(int i, int a, int b, int l, int r) {
    push(i);
    if (a == l && b == r) return t[i];
    int minl = INF;
    int minr = INF;
    int m = (l + r) / 2;
    if (a <= m) minl = get(2 * i + 1, a, min(m, b), l, m);
    if (m + 1 <= b) minr = get(2 * i + 2, max(a, m + 1), b, m + 1, r);
    return min(minl, minr);
  }
  int get(int a, int b) {
    if (a == b)
      return INF;
    else
      return get(0, a, b - 1, 0, size - 1);
  }
};
typedef struct {
  int t;
  int l;
  int r;
  int x;
} node;
node c[100006];
int w[100006], n, k, q, cnt;
vector<int> mark;
map<int, int> ss;
ST origin;
int originrangemin(int a, int b) {
  if (a - b >= n) return origin.get(0, n);
  a %= n;
  b = (b - 1) % n + 1;
  if (a < b)
    return origin.get(a, b);
  else if (a > b)
    return min(origin.get(a, n), origin.get(0, b));
  return 0;
}
int main() {
  cin >> n >> k;
  origin = ST(n);
  for (int i = 0; i < n; i++) {
    cin >> w[i];
    origin.upd(i, i + 1, w[i]);
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> c[i].t;
    if (c[i].t == 1)
      cin >> c[i].l >> c[i].r >> c[i].x;
    else
      cin >> c[i].l >> c[i].r;
    mark.push_back(c[i].l - 1);
    mark.push_back(c[i].r - 1);
  }
  sort(mark.begin(), mark.end());
  cnt = unique(mark.begin(), mark.end()) - mark.begin();
  mark.resize(cnt);
  ST work(mark.size() * 2);
  int last = -1, s_cnt = 0;
  for (int i = 0; i < cnt; i++) {
    int tmp;
    if (mark[i] - last > 1) {
      tmp = originrangemin(last + 1, mark[i]);
      work.upd(s_cnt, s_cnt + 1, tmp);
      s_cnt++;
    }
    tmp = originrangemin(mark[i], mark[i] + 1);
    work.upd(s_cnt, s_cnt + 1, tmp);
    ss[mark[i]] = s_cnt;
    s_cnt++;
    last = mark[i];
  }
  for (int i = 0; i < q; i++)
    if (c[i].t == 1)
      work.upd(ss[c[i].l - 1], ss[c[i].r - 1] + 1, c[i].x);
    else
      cout << work.get(ss[c[i].l - 1], ss[c[i].r - 1] + 1) << endl;
  return 0;
}

```