#include <bits/stdc++.h>
using namespace std;
const int P = 1e8 + 1;
int add(int a, int b) {
  if ((a += b) >= P) a -= P;
  return a;
}
int sub(int a, int b) {
  if ((a -= b) < 0) a += P;
  return a;
}
int mul(int a, int b) { return 1ll * a * b % P; }
int kpow(int a, int b) {
  int r = 1;
  for (; b; b >>= 1, a = mul(a, a)) {
    if (b & 1) r = mul(r, a);
  }
  return r;
}
const int N = 200005;
int data[N];
vector<int> V;
int co[N], L[N], R[N], x[N];
int tree[N << 2], lazy[N << 2], st[20][N];
int n, mmin = 0x3f3f3f3f;
int Min(int l, int r) {
  if (r - l + 1 >= n)
    return mmin;
  else if ((l - 1) / n < (r - 1) / n)
    return min(Min((l - 1) % n + 1, n), Min(1, (r - 1) % n + 1));
  l = (l - 1) % n + 1, r = (r - 1) % n + 1;
  int ans = 0x3f3f3f3f;
  for (int i = (20) - 1; i >= (0); i--)
    if (r - l + 1 >= (1 << i)) {
      ans = min(ans, st[i][r]);
      r -= 1 << i;
    }
  return ans;
}
void buildtree(int l, int r, int node) {
  if (l == r)
    tree[node] = Min(V[l - 1], V[l] - 1);
  else {
    int mid = (l + r) >> 1;
    buildtree(l, mid, node << 1);
    buildtree(mid + 1, r, node << 1 | 1);
    tree[node] = min(tree[node << 1], tree[node << 1 | 1]);
  }
}
void pushdown(int l, int r, int node) {
  if (lazy[node]) {
    lazy[node << 1] = lazy[node];
    lazy[node << 1 | 1] = lazy[node];
    int mid = (l + r) >> 1;
    tree[node << 1] = lazy[node];
    tree[node << 1 | 1] = lazy[node];
    lazy[node] = 0;
  }
}
void update(int l, int r, int node, int _l, int _r, int num) {
  if (_l == l && _r == r) {
    lazy[node] = num;
    tree[node] = num;
    return;
  } else if (l == r)
    return;
  int mid = (l + r) >> 1;
  pushdown(l, r, node);
  if (_r <= mid)
    update(l, mid, node << 1, _l, _r, num);
  else if (_l > mid)
    update(mid + 1, r, node << 1 | 1, _l, _r, num);
  else {
    update(l, mid, node << 1, _l, mid, num);
    update(mid + 1, r, node << 1 | 1, mid + 1, _r, num);
  }
  tree[node] = min(tree[node << 1], tree[node << 1 | 1]);
}
int query(int l, int r, int node, int _l, int _r) {
  if (l != r) pushdown(l, r, node);
  int mid = (l + r) >> 1;
  if (_l > r || _r < l)
    return 0x3f3f3f3f;
  else if (_l <= l && _r >= r)
    return tree[node];
  else
    return min(query(l, mid, node << 1, _l, _r),
               query(mid + 1, r, node << 1 | 1, _l, _r));
}
int main() {
  int k, q;
  scanf("%d%d", &n, &k);
  for (int i = (1); i < (n + 1); i++)
    scanf("%d", &data[i]), st[0][i] = data[i], mmin = min(data[i], mmin);
  for (int i = (1); i < (20); i++)
    for (int j = 1 << i; j <= n; j++)
      st[i][j] = min(st[i - 1][j], st[i - 1][j - (1 << (i - 1))]);
  scanf("%d", &q);
  for (int i = (0); i < (q); i++) {
    scanf("%d%d%d", &co[i], &L[i], &R[i]);
    if (co[i] == 1) scanf("%d", &x[i]);
    V.push_back(L[i]);
    V.push_back(++R[i]);
  }
  sort(V.begin(), V.end());
  V.erase(unique(V.begin(), V.end()), V.end());
  int s = (int)V.size() - 1;
  buildtree(1, s, 1);
  for (int i = (0); i < (q); i++) {
    L[i] = lower_bound(V.begin(), V.end(), L[i]) - V.begin() + 1;
    R[i] = lower_bound(V.begin(), V.end(), R[i]) - V.begin();
    if (co[i] == 2)
      printf("%d\n", query(1, s, 1, L[i], R[i]));
    else
      update(1, s, 1, L[i], R[i], x[i]);
  }
  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;
const int P = 1e8 + 1;
int add(int a, int b) {
  if ((a += b) >= P) a -= P;
  return a;
}
int sub(int a, int b) {
  if ((a -= b) < 0) a += P;
  return a;
}
int mul(int a, int b) { return 1ll * a * b % P; }
int kpow(int a, int b) {
  int r = 1;
  for (; b; b >>= 1, a = mul(a, a)) {
    if (b & 1) r = mul(r, a);
  }
  return r;
}
const int N = 200005;
int data[N];
vector<int> V;
int co[N], L[N], R[N], x[N];
int tree[N << 2], lazy[N << 2], st[20][N];
int n, mmin = 0x3f3f3f3f;
int Min(int l, int r) {
  if (r - l + 1 >= n)
    return mmin;
  else if ((l - 1) / n < (r - 1) / n)
    return min(Min((l - 1) % n + 1, n), Min(1, (r - 1) % n + 1));
  l = (l - 1) % n + 1, r = (r - 1) % n + 1;
  int ans = 0x3f3f3f3f;
  for (int i = (20) - 1; i >= (0); i--)
    if (r - l + 1 >= (1 << i)) {
      ans = min(ans, st[i][r]);
      r -= 1 << i;
    }
  return ans;
}
void buildtree(int l, int r, int node) {
  if (l == r)
    tree[node] = Min(V[l - 1], V[l] - 1);
  else {
    int mid = (l + r) >> 1;
    buildtree(l, mid, node << 1);
    buildtree(mid + 1, r, node << 1 | 1);
    tree[node] = min(tree[node << 1], tree[node << 1 | 1]);
  }
}
void pushdown(int l, int r, int node) {
  if (lazy[node]) {
    lazy[node << 1] = lazy[node];
    lazy[node << 1 | 1] = lazy[node];
    int mid = (l + r) >> 1;
    tree[node << 1] = lazy[node];
    tree[node << 1 | 1] = lazy[node];
    lazy[node] = 0;
  }
}
void update(int l, int r, int node, int _l, int _r, int num) {
  if (_l == l && _r == r) {
    lazy[node] = num;
    tree[node] = num;
    return;
  } else if (l == r)
    return;
  int mid = (l + r) >> 1;
  pushdown(l, r, node);
  if (_r <= mid)
    update(l, mid, node << 1, _l, _r, num);
  else if (_l > mid)
    update(mid + 1, r, node << 1 | 1, _l, _r, num);
  else {
    update(l, mid, node << 1, _l, mid, num);
    update(mid + 1, r, node << 1 | 1, mid + 1, _r, num);
  }
  tree[node] = min(tree[node << 1], tree[node << 1 | 1]);
}
int query(int l, int r, int node, int _l, int _r) {
  if (l != r) pushdown(l, r, node);
  int mid = (l + r) >> 1;
  if (_l > r || _r < l)
    return 0x3f3f3f3f;
  else if (_l <= l && _r >= r)
    return tree[node];
  else
    return min(query(l, mid, node << 1, _l, _r),
               query(mid + 1, r, node << 1 | 1, _l, _r));
}
int main() {
  int k, q;
  scanf("%d%d", &n, &k);
  for (int i = (1); i < (n + 1); i++)
    scanf("%d", &data[i]), st[0][i] = data[i], mmin = min(data[i], mmin);
  for (int i = (1); i < (20); i++)
    for (int j = 1 << i; j <= n; j++)
      st[i][j] = min(st[i - 1][j], st[i - 1][j - (1 << (i - 1))]);
  scanf("%d", &q);
  for (int i = (0); i < (q); i++) {
    scanf("%d%d%d", &co[i], &L[i], &R[i]);
    if (co[i] == 1) scanf("%d", &x[i]);
    V.push_back(L[i]);
    V.push_back(++R[i]);
  }
  sort(V.begin(), V.end());
  V.erase(unique(V.begin(), V.end()), V.end());
  int s = (int)V.size() - 1;
  buildtree(1, s, 1);
  for (int i = (0); i < (q); i++) {
    L[i] = lower_bound(V.begin(), V.end(), L[i]) - V.begin() + 1;
    R[i] = lower_bound(V.begin(), V.end(), R[i]) - V.begin();
    if (co[i] == 2)
      printf("%d\n", query(1, s, 1, L[i], R[i]));
    else
      update(1, s, 1, L[i], R[i], x[i]);
  }
  return 0;
}

```