#include <bits/stdc++.h>
using namespace std;
const int oo = 1e9 + 7;
const int N = 1e5 + 1;
int n, k, q, a[N * 3], b[N], t[N], l[N], r[N], u[N];
vector<int> v;
struct RMQ {
  int size = 0, *seg, *lazy;
  void build(int *arr, int id, int l, int r) {
    if (l == r) {
      seg[id] = arr[l];
      return;
    }
    int mid = l + r >> 1;
    build(arr, id << 1, l, mid);
    build(arr, id << 1 | 1, mid + 1, r);
    seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
  }
  void update(int id, int x) { seg[id] = lazy[id] = x; }
  void shift(int id) {
    if (!lazy[id]) return;
    update(id << 1, lazy[id]);
    update(id << 1 | 1, lazy[id]);
    lazy[id] = 0;
  }
  int get(int L, int R, int id, int l, int r) {
    if (R < l || r < L) return oo;
    if (L <= l && r <= R) return seg[id];
    shift(id);
    int mid = l + r >> 1;
    return min(get(L, R, id << 1, l, mid), get(L, R, id << 1 | 1, mid + 1, r));
  }
  int get(int l, int r) { return get(l, r, 1, 0, size - 1); }
  void paint(int L, int R, int x, int id, int l, int r) {
    if (R < l || r < L) return;
    if (L <= l && r <= R) {
      update(id, x);
      return;
    }
    shift(id);
    int mid = l + r >> 1;
    paint(L, R, x, id << 1, l, mid);
    paint(L, R, x, id << 1 | 1, mid + 1, r);
    seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
  }
  void paint(int l, int r, int x) { paint(l, r, x, 1, 0, size - 1); }
  RMQ(int *arr, int n) {
    seg = new int[n << 2];
    lazy = new int[n << 2];
    fill(lazy, lazy + n * 4, 0);
    size = n;
    build(arr, 1, 0, n - 1);
  }
};
void input() {
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", b + i);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d %d %d", t + i, l + i, r + i);
    if (t[i] == 1) scanf("%d", u + i);
    --l[i], --r[i];
    v.push_back(l[i]);
    v.push_back(r[i]);
    v.push_back(r[i] + 1);
  }
}
void solve() {
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  int all = v.size();
  v.push_back(v.back() + 1);
  RMQ B(b, n);
  for (int i = 0; i < all; i++) {
    int nl = v[i] % n, nr = (v[i + 1] - 1) % n;
    if (v[i + 1] - v[i] + 1 >= n)
      a[i] = B.get(0, n - 1);
    else if (nl <= nr)
      a[i] = B.get(nl, nr);
    else
      a[i] = min(B.get(nl, n - 1), B.get(0, nr));
  }
  RMQ A(a, all);
  for (int i = 0; i < q; i++) {
    l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin();
    r[i] = lower_bound(v.begin(), v.end(), r[i]) - v.begin();
    if (t[i] == 1)
      A.paint(l[i], r[i], u[i]);
    else
      printf("%d\n", A.get(l[i], r[i]));
  }
}
int main() {
  input();
  solve();
}

### 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 oo = 1e9 + 7;
const int N = 1e5 + 1;
int n, k, q, a[N * 3], b[N], t[N], l[N], r[N], u[N];
vector<int> v;
struct RMQ {
  int size = 0, *seg, *lazy;
  void build(int *arr, int id, int l, int r) {
    if (l == r) {
      seg[id] = arr[l];
      return;
    }
    int mid = l + r >> 1;
    build(arr, id << 1, l, mid);
    build(arr, id << 1 | 1, mid + 1, r);
    seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
  }
  void update(int id, int x) { seg[id] = lazy[id] = x; }
  void shift(int id) {
    if (!lazy[id]) return;
    update(id << 1, lazy[id]);
    update(id << 1 | 1, lazy[id]);
    lazy[id] = 0;
  }
  int get(int L, int R, int id, int l, int r) {
    if (R < l || r < L) return oo;
    if (L <= l && r <= R) return seg[id];
    shift(id);
    int mid = l + r >> 1;
    return min(get(L, R, id << 1, l, mid), get(L, R, id << 1 | 1, mid + 1, r));
  }
  int get(int l, int r) { return get(l, r, 1, 0, size - 1); }
  void paint(int L, int R, int x, int id, int l, int r) {
    if (R < l || r < L) return;
    if (L <= l && r <= R) {
      update(id, x);
      return;
    }
    shift(id);
    int mid = l + r >> 1;
    paint(L, R, x, id << 1, l, mid);
    paint(L, R, x, id << 1 | 1, mid + 1, r);
    seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
  }
  void paint(int l, int r, int x) { paint(l, r, x, 1, 0, size - 1); }
  RMQ(int *arr, int n) {
    seg = new int[n << 2];
    lazy = new int[n << 2];
    fill(lazy, lazy + n * 4, 0);
    size = n;
    build(arr, 1, 0, n - 1);
  }
};
void input() {
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", b + i);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d %d %d", t + i, l + i, r + i);
    if (t[i] == 1) scanf("%d", u + i);
    --l[i], --r[i];
    v.push_back(l[i]);
    v.push_back(r[i]);
    v.push_back(r[i] + 1);
  }
}
void solve() {
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  int all = v.size();
  v.push_back(v.back() + 1);
  RMQ B(b, n);
  for (int i = 0; i < all; i++) {
    int nl = v[i] % n, nr = (v[i + 1] - 1) % n;
    if (v[i + 1] - v[i] + 1 >= n)
      a[i] = B.get(0, n - 1);
    else if (nl <= nr)
      a[i] = B.get(nl, nr);
    else
      a[i] = min(B.get(nl, n - 1), B.get(0, nr));
  }
  RMQ A(a, all);
  for (int i = 0; i < q; i++) {
    l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin();
    r[i] = lower_bound(v.begin(), v.end(), r[i]) - v.begin();
    if (t[i] == 1)
      A.paint(l[i], r[i], u[i]);
    else
      printf("%d\n", A.get(l[i], r[i]));
  }
}
int main() {
  input();
  solve();
}

```