#include <bits/stdc++.h>
using namespace std;
struct segt {
  int l, r;
  int lz, value;
  bool isleaf;
};
int orig[2097252 >> 3];
segt tree[2097252];
vector<pair<int, int> > interval;
int a[2097252 >> 4];
int pt[2097252 >> 1];
vector<int> disc;
int oper[2097252 >> 4][4];
int k, q, n;
segt pullup(segt t1, segt t2) {
  segt t;
  t.lz = 0;
  t.value = min(t1.value, t2.value);
  t.l = t1.l;
  t.r = t2.r;
  t.isleaf = false;
  return t;
}
void pushdown(int index) {
  if (tree[index].lz) {
    if (!tree[index].isleaf) {
      tree[index * 2].value = tree[index].lz;
      tree[index * 2 + 1].value = tree[index].lz;
      tree[index * 2].lz = tree[index].lz;
      tree[index * 2 + 1].lz = tree[index].lz;
    }
    tree[index].lz = 0;
  }
}
int rmq(int start, int end, int l, int r, int index) {
  if (start > end || l > r || start > r || l > end) return 1000000000 + 7;
  if (start <= l && r <= end) return orig[index];
  int mid = l + (r - l) / 2;
  return min(rmq(start, end, l, mid, index * 2),
             rmq(start, end, mid + 1, r, index * 2 + 1));
}
void build(int l, int r, int index) {
  if (l > r) return;
  if (l == r) {
    tree[index].l = interval[l].first;
    tree[index].r = interval[l].second;
    tree[index].isleaf = true;
    if (tree[index].r - tree[index].l + 1 >= n) {
      tree[index].value = rmq(1, n, 1, n, 1);
    } else {
      int left = (tree[index].l % n != 0 ? tree[index].l % n : n);
      int right = (tree[index].r % n != 0 ? tree[index].r % n : n);
      if (left > right) {
        tree[index].value = min(rmq(left, n, 1, n, 1), rmq(1, right, 1, n, 1));
      } else {
        tree[index].value = rmq(left, right, 1, n, 1);
      }
    }
    return;
  }
  int mid = l + (r - l) / 2;
  build(l, mid, index * 2);
  build(mid + 1, r, index * 2 + 1);
  tree[index] = pullup(tree[index * 2], tree[index * 2 + 1]);
}
void update(int start, int end, int index, int val) {
  if (start > end) return;
  pushdown(index);
  if (start > tree[index].r || tree[index].l > end) return;
  if (start <= tree[index].l && tree[index].r <= end) {
    tree[index].value = val;
    tree[index].lz = val;
    return;
  }
  update(start, end, index * 2, val);
  update(start, end, index * 2 + 1, val);
  tree[index] = pullup(tree[index * 2], tree[index * 2 + 1]);
}
int query(int start, int end, int index) {
  if (start > end) {
    return 1000000000 + 7;
  }
  pushdown(index);
  if (start > tree[index].r || tree[index].l > end) return 1000000000 + 7;
  if (start <= tree[index].l && tree[index].r <= end) return tree[index].value;
  return min(query(start, end, index * 2), query(start, end, index * 2 + 1));
}
void buildint(int l, int r, int index) {
  if (l > r) return;
  if (l == r) {
    orig[index] = a[l];
    return;
  }
  int mid = l + (r - l) / 2;
  buildint(l, mid, index * 2);
  buildint(mid + 1, r, index * 2 + 1);
  orig[index] = min(orig[index * 2], orig[index * 2 + 1]);
}
int main() {
  int i, cnt = 0;
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    pt[cnt++] = i;
  }
  pt[cnt++] = n * k;
  scanf("%d", &q);
  for (i = 0; i < q; i++) {
    scanf("%d%d%d", &oper[i][0], &oper[i][1], &oper[i][2]);
    if (oper[i][0] == 1) {
      scanf("%d", &oper[i][3]);
    }
    pt[cnt++] = oper[i][1];
    pt[cnt++] = oper[i][2];
  }
  sort(pt, pt + cnt);
  for (i = 0; i < cnt; i++) {
    if (i == 0 || pt[i] != pt[i - 1]) {
      disc.push_back(pt[i]);
    }
  }
  for (i = 0; i < (int)disc.size(); i++) {
    if (i == 0) {
      interval.emplace_back(disc[0], disc[0]);
    } else {
      if (disc[i] - disc[i - 1] > 1) {
        interval.emplace_back(disc[i - 1] + 1, disc[i] - 1);
      }
      interval.emplace_back(disc[i], disc[i]);
    }
  }
  int m = (int)interval.size();
  buildint(1, n, 1);
  build(0, m - 1, 1);
  for (i = 0; i < q; i++) {
    if (oper[i][0] == 1) {
      update(oper[i][1], oper[i][2], 1, oper[i][3]);
    } else {
      printf("%d\n", query(oper[i][1], oper[i][2], 1));
    }
  }
  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;
struct segt {
  int l, r;
  int lz, value;
  bool isleaf;
};
int orig[2097252 >> 3];
segt tree[2097252];
vector<pair<int, int> > interval;
int a[2097252 >> 4];
int pt[2097252 >> 1];
vector<int> disc;
int oper[2097252 >> 4][4];
int k, q, n;
segt pullup(segt t1, segt t2) {
  segt t;
  t.lz = 0;
  t.value = min(t1.value, t2.value);
  t.l = t1.l;
  t.r = t2.r;
  t.isleaf = false;
  return t;
}
void pushdown(int index) {
  if (tree[index].lz) {
    if (!tree[index].isleaf) {
      tree[index * 2].value = tree[index].lz;
      tree[index * 2 + 1].value = tree[index].lz;
      tree[index * 2].lz = tree[index].lz;
      tree[index * 2 + 1].lz = tree[index].lz;
    }
    tree[index].lz = 0;
  }
}
int rmq(int start, int end, int l, int r, int index) {
  if (start > end || l > r || start > r || l > end) return 1000000000 + 7;
  if (start <= l && r <= end) return orig[index];
  int mid = l + (r - l) / 2;
  return min(rmq(start, end, l, mid, index * 2),
             rmq(start, end, mid + 1, r, index * 2 + 1));
}
void build(int l, int r, int index) {
  if (l > r) return;
  if (l == r) {
    tree[index].l = interval[l].first;
    tree[index].r = interval[l].second;
    tree[index].isleaf = true;
    if (tree[index].r - tree[index].l + 1 >= n) {
      tree[index].value = rmq(1, n, 1, n, 1);
    } else {
      int left = (tree[index].l % n != 0 ? tree[index].l % n : n);
      int right = (tree[index].r % n != 0 ? tree[index].r % n : n);
      if (left > right) {
        tree[index].value = min(rmq(left, n, 1, n, 1), rmq(1, right, 1, n, 1));
      } else {
        tree[index].value = rmq(left, right, 1, n, 1);
      }
    }
    return;
  }
  int mid = l + (r - l) / 2;
  build(l, mid, index * 2);
  build(mid + 1, r, index * 2 + 1);
  tree[index] = pullup(tree[index * 2], tree[index * 2 + 1]);
}
void update(int start, int end, int index, int val) {
  if (start > end) return;
  pushdown(index);
  if (start > tree[index].r || tree[index].l > end) return;
  if (start <= tree[index].l && tree[index].r <= end) {
    tree[index].value = val;
    tree[index].lz = val;
    return;
  }
  update(start, end, index * 2, val);
  update(start, end, index * 2 + 1, val);
  tree[index] = pullup(tree[index * 2], tree[index * 2 + 1]);
}
int query(int start, int end, int index) {
  if (start > end) {
    return 1000000000 + 7;
  }
  pushdown(index);
  if (start > tree[index].r || tree[index].l > end) return 1000000000 + 7;
  if (start <= tree[index].l && tree[index].r <= end) return tree[index].value;
  return min(query(start, end, index * 2), query(start, end, index * 2 + 1));
}
void buildint(int l, int r, int index) {
  if (l > r) return;
  if (l == r) {
    orig[index] = a[l];
    return;
  }
  int mid = l + (r - l) / 2;
  buildint(l, mid, index * 2);
  buildint(mid + 1, r, index * 2 + 1);
  orig[index] = min(orig[index * 2], orig[index * 2 + 1]);
}
int main() {
  int i, cnt = 0;
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    pt[cnt++] = i;
  }
  pt[cnt++] = n * k;
  scanf("%d", &q);
  for (i = 0; i < q; i++) {
    scanf("%d%d%d", &oper[i][0], &oper[i][1], &oper[i][2]);
    if (oper[i][0] == 1) {
      scanf("%d", &oper[i][3]);
    }
    pt[cnt++] = oper[i][1];
    pt[cnt++] = oper[i][2];
  }
  sort(pt, pt + cnt);
  for (i = 0; i < cnt; i++) {
    if (i == 0 || pt[i] != pt[i - 1]) {
      disc.push_back(pt[i]);
    }
  }
  for (i = 0; i < (int)disc.size(); i++) {
    if (i == 0) {
      interval.emplace_back(disc[0], disc[0]);
    } else {
      if (disc[i] - disc[i - 1] > 1) {
        interval.emplace_back(disc[i - 1] + 1, disc[i] - 1);
      }
      interval.emplace_back(disc[i], disc[i]);
    }
  }
  int m = (int)interval.size();
  buildint(1, n, 1);
  build(0, m - 1, 1);
  for (i = 0; i < q; i++) {
    if (oper[i][0] == 1) {
      update(oper[i][1], oper[i][2], 1, oper[i][3]);
    } else {
      printf("%d\n", query(oper[i][1], oper[i][2], 1));
    }
  }
  return 0;
}

```