#include <bits/stdc++.h>
using namespace std;
function<void(void)> ____ = []() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
};
const int MAXN = 6e5 + 7;
const int INF = 0x3f3f3f3f;
int n, k, A[MAXN][20];
struct Qs {
  int type, l, r, x;
} Q[MAXN];
struct SegTree {
  int minn[MAXN << 2], l[MAXN << 2], r[MAXN << 2], lazy[MAXN << 2];
  void build(int L, int R, vector<pair<int, int> > &vcc, int rt = 1) {
    l[rt] = L, r[rt] = R;
    if (L + 1 == R) {
      minn[rt] = vcc[L].second;
      return;
    }
    int mid = (L + R) >> 1;
    build(L, mid, vcc, rt << 1);
    build(mid, R, vcc, rt << 1 | 1);
    minn[rt] = min(minn[rt << 1], minn[rt << 1 | 1]);
  }
  void pushdown(int rt) {
    if (!lazy[rt]) return;
    lazy[rt << 1] = lazy[rt << 1 | 1] = minn[rt << 1] = minn[rt << 1 | 1] =
        lazy[rt];
    lazy[rt] = 0;
  }
  void modify(int L, int R, int x, int rt = 1) {
    if (L >= r[rt] or l[rt] >= R) return;
    if (L <= l[rt] and r[rt] <= R) {
      lazy[rt] = minn[rt] = x;
      return;
    }
    pushdown(rt);
    modify(L, R, x, rt << 1);
    modify(L, R, x, rt << 1 | 1);
    minn[rt] = min(minn[rt << 1], minn[rt << 1 | 1]);
  }
  int query(int L, int R, int rt = 1) {
    if (L >= r[rt] or l[rt] >= R) return INF;
    if (L <= l[rt] and r[rt] <= R) return minn[rt];
    pushdown(rt);
    return min(query(L, R, rt << 1), query(L, R, rt << 1 | 1));
  }
} ST;
void solve() {
  ____();
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> A[i][0], A[i + n][0] = A[i][0];
  for (int j = 1; (1 << j) <= (n << 1); j++)
    for (int i = 0; i + (1 << j) - 1 < (n << 1); i++)
      A[i][j] = min(A[i][j - 1], A[i + (1 << (j - 1))][j - 1]);
  auto query = [&](int l, int r) {
    int d = (int)log2(r - l + 1);
    return min(A[l][d], A[r - (1 << d) + 1][d]);
  };
  int q;
  cin >> q;
  vector<int> vec;
  for (int i = 0; i < q; i++) {
    cin >> Q[i].type >> Q[i].l >> Q[i].r;
    Q[i].l--;
    Q[i].r--;
    if (Q[i].type == 1) cin >> Q[i].x;
    vec.push_back(Q[i].l);
    vec.push_back(Q[i].r);
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  vector<pair<int, int> > vcc;
  for (int i = 1, lim = vec.size(); i < lim; i++) {
    if (vec[i] == vec[i - 1] + 1) continue;
    if (vec[i] - vec[i - 1] + 1 >= n)
      vcc.push_back({vec[i - 1] + 1, query(0, n - 1)});
    else {
      int l = vec[i - 1] % n, r = vec[i] % n;
      if (l > r) r += n;
      vcc.push_back({vec[i - 1] + 1, query(l + 1, r - 1)});
    }
  }
  for (int i = 0; i < (int)vec.size(); i++)
    vcc.push_back({vec[i], A[vec[i] % n][0]});
  sort(vcc.begin(), vcc.end());
  ST.build(0, vcc.size(), vcc);
  for (int i = 0; i < q; i++) {
    int l = Q[i].l, r = Q[i].r;
    l = lower_bound(vcc.begin(), vcc.end(), make_pair(l, 0)) - vcc.begin();
    r = lower_bound(vcc.begin(), vcc.end(), make_pair(r, 0)) - vcc.begin();
    if (Q[i].type == 1)
      ST.modify(l, r + 1, Q[i].x);
    else
      printf("%d\n", ST.query(l, r + 1));
  }
}
int main() {
  solve();
  return 0;
}

### Prompt

Generate a CPP solution 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;
function<void(void)> ____ = []() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
};
const int MAXN = 6e5 + 7;
const int INF = 0x3f3f3f3f;
int n, k, A[MAXN][20];
struct Qs {
  int type, l, r, x;
} Q[MAXN];
struct SegTree {
  int minn[MAXN << 2], l[MAXN << 2], r[MAXN << 2], lazy[MAXN << 2];
  void build(int L, int R, vector<pair<int, int> > &vcc, int rt = 1) {
    l[rt] = L, r[rt] = R;
    if (L + 1 == R) {
      minn[rt] = vcc[L].second;
      return;
    }
    int mid = (L + R) >> 1;
    build(L, mid, vcc, rt << 1);
    build(mid, R, vcc, rt << 1 | 1);
    minn[rt] = min(minn[rt << 1], minn[rt << 1 | 1]);
  }
  void pushdown(int rt) {
    if (!lazy[rt]) return;
    lazy[rt << 1] = lazy[rt << 1 | 1] = minn[rt << 1] = minn[rt << 1 | 1] =
        lazy[rt];
    lazy[rt] = 0;
  }
  void modify(int L, int R, int x, int rt = 1) {
    if (L >= r[rt] or l[rt] >= R) return;
    if (L <= l[rt] and r[rt] <= R) {
      lazy[rt] = minn[rt] = x;
      return;
    }
    pushdown(rt);
    modify(L, R, x, rt << 1);
    modify(L, R, x, rt << 1 | 1);
    minn[rt] = min(minn[rt << 1], minn[rt << 1 | 1]);
  }
  int query(int L, int R, int rt = 1) {
    if (L >= r[rt] or l[rt] >= R) return INF;
    if (L <= l[rt] and r[rt] <= R) return minn[rt];
    pushdown(rt);
    return min(query(L, R, rt << 1), query(L, R, rt << 1 | 1));
  }
} ST;
void solve() {
  ____();
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> A[i][0], A[i + n][0] = A[i][0];
  for (int j = 1; (1 << j) <= (n << 1); j++)
    for (int i = 0; i + (1 << j) - 1 < (n << 1); i++)
      A[i][j] = min(A[i][j - 1], A[i + (1 << (j - 1))][j - 1]);
  auto query = [&](int l, int r) {
    int d = (int)log2(r - l + 1);
    return min(A[l][d], A[r - (1 << d) + 1][d]);
  };
  int q;
  cin >> q;
  vector<int> vec;
  for (int i = 0; i < q; i++) {
    cin >> Q[i].type >> Q[i].l >> Q[i].r;
    Q[i].l--;
    Q[i].r--;
    if (Q[i].type == 1) cin >> Q[i].x;
    vec.push_back(Q[i].l);
    vec.push_back(Q[i].r);
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  vector<pair<int, int> > vcc;
  for (int i = 1, lim = vec.size(); i < lim; i++) {
    if (vec[i] == vec[i - 1] + 1) continue;
    if (vec[i] - vec[i - 1] + 1 >= n)
      vcc.push_back({vec[i - 1] + 1, query(0, n - 1)});
    else {
      int l = vec[i - 1] % n, r = vec[i] % n;
      if (l > r) r += n;
      vcc.push_back({vec[i - 1] + 1, query(l + 1, r - 1)});
    }
  }
  for (int i = 0; i < (int)vec.size(); i++)
    vcc.push_back({vec[i], A[vec[i] % n][0]});
  sort(vcc.begin(), vcc.end());
  ST.build(0, vcc.size(), vcc);
  for (int i = 0; i < q; i++) {
    int l = Q[i].l, r = Q[i].r;
    l = lower_bound(vcc.begin(), vcc.end(), make_pair(l, 0)) - vcc.begin();
    r = lower_bound(vcc.begin(), vcc.end(), make_pair(r, 0)) - vcc.begin();
    if (Q[i].type == 1)
      ST.modify(l, r + 1, Q[i].x);
    else
      printf("%d\n", ST.query(l, r + 1));
  }
}
int main() {
  solve();
  return 0;
}

```