#include <bits/stdc++.h>
using namespace std;
vector<int> pri;
const int INF = 1e9 + 1;
int n, q, k, a[100010], ori[400010], op[100010], opl[100010], opr[100010],
    opx[100010], nodes[1000010], tag[2000010], s;
void buildori(int l, int r, int x) {
  if (l ^ r) {
    int mid = (l + r) >> 1;
    buildori(l, mid, x << 1);
    buildori(mid + 1, r, x << 1 | 1);
    ori[x] = min(ori[x << 1], ori[x << 1 | 1]);
  } else
    ori[x] = a[l];
}
int findori(int l, int r, int x, int fr, int ba) {
  if (l > ba || r < fr) return INF;
  if (l >= fr && r <= ba)
    return ori[x];
  else {
    int mid = (l + r) >> 1;
    return min(findori(l, mid, x << 1, fr, ba),
               findori(mid + 1, r, x << 1 | 1, fr, ba));
  }
}
void build(int l, int r, int x) {
  if (l ^ r) {
    int mid = (l + r) >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    nodes[x] = min(nodes[x << 1], nodes[x << 1 | 1]);
  } else {
    if (pri[l] - pri[l - 1] >= n)
      nodes[x] = ori[1];
    else {
      int one = (pri[l - 1] + 1) % n;
      if (one == 0) one = n;
      int two = pri[l] % n;
      if (two == 0) two = n;
      if (one > two)
        nodes[x] = min(findori(1, n, 1, one, n), findori(1, n, 1, 1, two));
      else
        nodes[x] = findori(1, n, 1, one, two);
    }
  }
}
void pushdown(int x) {
  if (tag[x]) {
    nodes[x] = tag[x];
    tag[x << 1] = tag[x << 1 | 1] = tag[x];
    tag[x] = 0;
  }
}
void update(int l, int r, int x, int fr, int ba, int val) {
  if (l > ba || r < fr) return;
  if (l >= fr && r <= ba)
    tag[x] = val;
  else {
    int mid = (l + r) >> 1;
    pushdown(x);
    update(l, mid, x << 1, fr, ba, val);
    update(mid + 1, r, x << 1 | 1, fr, ba, val);
    pushdown(x << 1);
    pushdown(x << 1 | 1);
    nodes[x] = min(nodes[x << 1], nodes[x << 1 | 1]);
  }
}
int find(int l, int r, int x, int fr, int ba) {
  if (l > ba || r < fr) return INF;
  pushdown(x);
  if (l >= fr && r <= ba)
    return nodes[x];
  else {
    int mid = (l + r) >> 1;
    return min(find(l, mid, x << 1, fr, ba),
               find(mid + 1, r, x << 1 | 1, fr, ba));
  }
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  buildori(1, n, 1);
  scanf("%d", &q);
  pri.push_back(0);
  pri.push_back(n * k);
  for (int i = 1; i <= q; ++i) {
    scanf("%d %d %d", &op[i], &opl[i], &opr[i]);
    if (op[i] == 1) scanf("%d", &opx[i]);
    pri.push_back(opl[i] - 1);
    pri.push_back(opr[i]);
  }
  sort(pri.begin(), pri.end());
  pri.erase(unique(pri.begin(), pri.end()), pri.end());
  s = pri.size();
  build(1, s, 1);
  for (int i = 1; i <= q; ++i) {
    if (op[i] == 1)
      update(1, s, 1, lower_bound(pri.begin(), pri.end(), opl[i]) - pri.begin(),
             lower_bound(pri.begin(), pri.end(), opr[i]) - pri.begin(), opx[i]);
    else
      printf("%d\n",
             find(1, s, 1,
                  lower_bound(pri.begin(), pri.end(), opl[i]) - pri.begin(),
                  lower_bound(pri.begin(), pri.end(), opr[i]) - pri.begin()));
  }
  return 0;
}

### Prompt

Create a solution in CPP for 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;
vector<int> pri;
const int INF = 1e9 + 1;
int n, q, k, a[100010], ori[400010], op[100010], opl[100010], opr[100010],
    opx[100010], nodes[1000010], tag[2000010], s;
void buildori(int l, int r, int x) {
  if (l ^ r) {
    int mid = (l + r) >> 1;
    buildori(l, mid, x << 1);
    buildori(mid + 1, r, x << 1 | 1);
    ori[x] = min(ori[x << 1], ori[x << 1 | 1]);
  } else
    ori[x] = a[l];
}
int findori(int l, int r, int x, int fr, int ba) {
  if (l > ba || r < fr) return INF;
  if (l >= fr && r <= ba)
    return ori[x];
  else {
    int mid = (l + r) >> 1;
    return min(findori(l, mid, x << 1, fr, ba),
               findori(mid + 1, r, x << 1 | 1, fr, ba));
  }
}
void build(int l, int r, int x) {
  if (l ^ r) {
    int mid = (l + r) >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    nodes[x] = min(nodes[x << 1], nodes[x << 1 | 1]);
  } else {
    if (pri[l] - pri[l - 1] >= n)
      nodes[x] = ori[1];
    else {
      int one = (pri[l - 1] + 1) % n;
      if (one == 0) one = n;
      int two = pri[l] % n;
      if (two == 0) two = n;
      if (one > two)
        nodes[x] = min(findori(1, n, 1, one, n), findori(1, n, 1, 1, two));
      else
        nodes[x] = findori(1, n, 1, one, two);
    }
  }
}
void pushdown(int x) {
  if (tag[x]) {
    nodes[x] = tag[x];
    tag[x << 1] = tag[x << 1 | 1] = tag[x];
    tag[x] = 0;
  }
}
void update(int l, int r, int x, int fr, int ba, int val) {
  if (l > ba || r < fr) return;
  if (l >= fr && r <= ba)
    tag[x] = val;
  else {
    int mid = (l + r) >> 1;
    pushdown(x);
    update(l, mid, x << 1, fr, ba, val);
    update(mid + 1, r, x << 1 | 1, fr, ba, val);
    pushdown(x << 1);
    pushdown(x << 1 | 1);
    nodes[x] = min(nodes[x << 1], nodes[x << 1 | 1]);
  }
}
int find(int l, int r, int x, int fr, int ba) {
  if (l > ba || r < fr) return INF;
  pushdown(x);
  if (l >= fr && r <= ba)
    return nodes[x];
  else {
    int mid = (l + r) >> 1;
    return min(find(l, mid, x << 1, fr, ba),
               find(mid + 1, r, x << 1 | 1, fr, ba));
  }
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  buildori(1, n, 1);
  scanf("%d", &q);
  pri.push_back(0);
  pri.push_back(n * k);
  for (int i = 1; i <= q; ++i) {
    scanf("%d %d %d", &op[i], &opl[i], &opr[i]);
    if (op[i] == 1) scanf("%d", &opx[i]);
    pri.push_back(opl[i] - 1);
    pri.push_back(opr[i]);
  }
  sort(pri.begin(), pri.end());
  pri.erase(unique(pri.begin(), pri.end()), pri.end());
  s = pri.size();
  build(1, s, 1);
  for (int i = 1; i <= q; ++i) {
    if (op[i] == 1)
      update(1, s, 1, lower_bound(pri.begin(), pri.end(), opl[i]) - pri.begin(),
             lower_bound(pri.begin(), pri.end(), opr[i]) - pri.begin(), opx[i]);
    else
      printf("%d\n",
             find(1, s, 1,
                  lower_bound(pri.begin(), pri.end(), opl[i]) - pri.begin(),
                  lower_bound(pri.begin(), pri.end(), opr[i]) - pri.begin()));
  }
  return 0;
}

```