#include <bits/stdc++.h>
using namespace std;
struct node {
  int l, r, v;
} t[4000010];
struct ask {
  int op, l, r, x;
  void in() {
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1) {
      scanf("%d", &x);
    }
  }
} q[100010];
int n, m, k, Q, a[100010], b[1000010], bk, id[1000010];
int f[100010][25], bit[100010], mn;
int c[1000010], lazy[4000010];
void pushdown(int k) {
  if (!lazy[k]) {
    return;
  }
  t[k << 1].v = t[k << 1 | 1].v = lazy[k];
  lazy[k << 1] = lazy[k << 1 | 1] = lazy[k];
  lazy[k] = 0;
}
void pushup(int k) { t[k].v = min(t[k << 1].v, t[k << 1 | 1].v); }
void build(int k, int l, int r) {
  t[k].l = l;
  t[k].r = r;
  if (l == r) {
    t[k].v = c[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
  pushup(k);
}
void update(int k, int x, int y, int v) {
  int l = t[k].l;
  int r = t[k].r;
  if (l == x && r == y) {
    t[k].v = v;
    lazy[k] = v;
    return;
  }
  pushdown(k);
  int mid = (l + r) >> 1;
  if (x > mid) {
    update(k << 1 | 1, x, y, v);
  } else if (y <= mid) {
    update(k << 1, x, y, v);
  } else {
    update(k << 1, x, mid, v);
    update(k << 1 | 1, mid + 1, y, v);
  }
  pushup(k);
}
int query(int k, int x, int y) {
  int l = t[k].l;
  int r = t[k].r;
  if (l == x && r == y) {
    return t[k].v;
  }
  pushdown(k);
  int mid = (l + r) >> 1;
  if (x > mid) {
    return query(k << 1 | 1, x, y);
  } else if (y <= mid) {
    return query(k << 1, x, y);
  } else {
    return min(query(k << 1, x, mid), query(k << 1 | 1, mid + 1, y));
  }
}
void rmqinit() {
  for (int i = 1; i <= 20; i++) {
    for (int j = 1; j + (1 << i) - 1 <= n; j++) {
      f[j][i] = min(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
    }
  }
}
int rmqask(int l, int r) {
  int k = bit[r - l + 1];
  return min(f[l][k], f[r - (1 << k) + 1][k]);
}
int getmn(int l, int r) {
  if (r - l + 1 >= n) {
    return mn;
  }
  l = (l - 1) % n + 1;
  r = (r - 1) % n + 1;
  if (l <= r) {
    return rmqask(l, r);
  } else {
    return min(rmqask(1, r), rmqask(l, n));
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 2; i <= n; i++) {
    bit[i] = bit[i >> 1] + 1;
  }
  mn = 2e9;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    f[i][0] = a[i];
    mn = min(mn, a[i]);
  }
  rmqinit();
  scanf("%d", &Q);
  for (int i = 0; i < Q; i++) {
    q[i].in();
    b[++bk] = q[i].l;
    b[++bk] = q[i].r;
  }
  sort(b + 1, b + bk + 1);
  bk = unique(b + 1, b + bk + 1) - b - 1;
  for (int i = 0; i < Q; i++) {
    q[i].l = lower_bound(b + 1, b + bk + 1, q[i].l) - b;
    q[i].r = lower_bound(b + 1, b + bk + 1, q[i].r) - b;
  }
  b[0] = 0;
  for (int i = 1; i <= bk; i++) {
    if (b[i - 1] + 1 != b[i]) {
      c[++m] = getmn(b[i - 1] + 1, b[i] - 1);
    }
    c[++m] = a[(b[i] - 1) % n + 1];
    id[i] = m;
  }
  if (b[bk] != n * k) {
    c[++m] = getmn(b[bk] + 1, n * k);
  }
  build(1, 1, m);
  for (int i = 0; i < Q; i++) {
    int op, l, r, x;
    op = q[i].op;
    l = q[i].l;
    r = q[i].r;
    x = q[i].x;
    l = id[l];
    r = id[r];
    if (op == 1) {
      update(1, l, r, x);
    } else {
      printf("%d\n", query(1, l, r));
    }
  }
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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;
struct node {
  int l, r, v;
} t[4000010];
struct ask {
  int op, l, r, x;
  void in() {
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1) {
      scanf("%d", &x);
    }
  }
} q[100010];
int n, m, k, Q, a[100010], b[1000010], bk, id[1000010];
int f[100010][25], bit[100010], mn;
int c[1000010], lazy[4000010];
void pushdown(int k) {
  if (!lazy[k]) {
    return;
  }
  t[k << 1].v = t[k << 1 | 1].v = lazy[k];
  lazy[k << 1] = lazy[k << 1 | 1] = lazy[k];
  lazy[k] = 0;
}
void pushup(int k) { t[k].v = min(t[k << 1].v, t[k << 1 | 1].v); }
void build(int k, int l, int r) {
  t[k].l = l;
  t[k].r = r;
  if (l == r) {
    t[k].v = c[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
  pushup(k);
}
void update(int k, int x, int y, int v) {
  int l = t[k].l;
  int r = t[k].r;
  if (l == x && r == y) {
    t[k].v = v;
    lazy[k] = v;
    return;
  }
  pushdown(k);
  int mid = (l + r) >> 1;
  if (x > mid) {
    update(k << 1 | 1, x, y, v);
  } else if (y <= mid) {
    update(k << 1, x, y, v);
  } else {
    update(k << 1, x, mid, v);
    update(k << 1 | 1, mid + 1, y, v);
  }
  pushup(k);
}
int query(int k, int x, int y) {
  int l = t[k].l;
  int r = t[k].r;
  if (l == x && r == y) {
    return t[k].v;
  }
  pushdown(k);
  int mid = (l + r) >> 1;
  if (x > mid) {
    return query(k << 1 | 1, x, y);
  } else if (y <= mid) {
    return query(k << 1, x, y);
  } else {
    return min(query(k << 1, x, mid), query(k << 1 | 1, mid + 1, y));
  }
}
void rmqinit() {
  for (int i = 1; i <= 20; i++) {
    for (int j = 1; j + (1 << i) - 1 <= n; j++) {
      f[j][i] = min(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
    }
  }
}
int rmqask(int l, int r) {
  int k = bit[r - l + 1];
  return min(f[l][k], f[r - (1 << k) + 1][k]);
}
int getmn(int l, int r) {
  if (r - l + 1 >= n) {
    return mn;
  }
  l = (l - 1) % n + 1;
  r = (r - 1) % n + 1;
  if (l <= r) {
    return rmqask(l, r);
  } else {
    return min(rmqask(1, r), rmqask(l, n));
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 2; i <= n; i++) {
    bit[i] = bit[i >> 1] + 1;
  }
  mn = 2e9;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    f[i][0] = a[i];
    mn = min(mn, a[i]);
  }
  rmqinit();
  scanf("%d", &Q);
  for (int i = 0; i < Q; i++) {
    q[i].in();
    b[++bk] = q[i].l;
    b[++bk] = q[i].r;
  }
  sort(b + 1, b + bk + 1);
  bk = unique(b + 1, b + bk + 1) - b - 1;
  for (int i = 0; i < Q; i++) {
    q[i].l = lower_bound(b + 1, b + bk + 1, q[i].l) - b;
    q[i].r = lower_bound(b + 1, b + bk + 1, q[i].r) - b;
  }
  b[0] = 0;
  for (int i = 1; i <= bk; i++) {
    if (b[i - 1] + 1 != b[i]) {
      c[++m] = getmn(b[i - 1] + 1, b[i] - 1);
    }
    c[++m] = a[(b[i] - 1) % n + 1];
    id[i] = m;
  }
  if (b[bk] != n * k) {
    c[++m] = getmn(b[bk] + 1, n * k);
  }
  build(1, 1, m);
  for (int i = 0; i < Q; i++) {
    int op, l, r, x;
    op = q[i].op;
    l = q[i].l;
    r = q[i].r;
    x = q[i].x;
    l = id[l];
    r = id[r];
    if (op == 1) {
      update(1, l, r, x);
    } else {
      printf("%d\n", query(1, l, r));
    }
  }
  return 0;
}

```