#include <bits/stdc++.h>
using namespace std;
struct RangeMinimumQuery {
  vector<int> v;
  vector<vector<int> > mn;
  vector<int> _lg;
  RangeMinimumQuery(const vector<int> &_v) {
    v = _v;
    int n = v.size();
    mn.resize(20);
    for (int i = 0; i < (int)(mn.size()); ++i) mn[i].resize(n);
    for (int i = 0; i < (int)(n); ++i) mn[0][i] = v[i];
    for (int j = 0; j < (int)(20 - 1); ++j)
      for (int i = 0; i < (int)(n - (1 << (j + 1)) + 1); ++i)
        mn[j + 1][i] = min(mn[j][i], mn[j][i + (1 << j)]);
    _lg.resize(n + 1);
    for (int i = 0; i < (int)(n + 1); ++i)
      if (i > 1) _lg[i] = _lg[i >> 1] + 1;
  }
  int qry(int l, int r) {
    if (l == r) return 1e9 + 7;
    int k = _lg[r - l];
    return min(mn[k][l], mn[k][r - (1 << k)]);
  }
  int per_qry(int l, int r) {
    if (l == r) return 1e9 + 7;
    if (r - l >= v.size()) return qry(0, v.size());
    int nl = l % v.size(), nr = r % v.size();
    if (nl < nr)
      return qry(nl, nr);
    else
      return min(qry(nl, v.size()), qry(0, nr));
  }
};
struct SegmentTreeLazy {
  int sz, _lg;
  vector<int> tag, mn;
  inline void push(int x, int v) { mn[x] = v, tag[x] = v; }
  inline void pushdown(int x) {
    if (tag[x] != -1)
      push(x << 1, tag[x]), push(x << 1 | 1, tag[x]), tag[x] = -1;
  }
  inline void pushup(int x) { mn[x] = min(mn[x << 1], mn[x << 1 | 1]); }
  SegmentTreeLazy(const vector<int> &v) {
    int n = v.size();
    for (sz = 1, _lg = 0; sz < n; sz <<= 1, ++_lg)
      ;
    tag.resize(sz << 1, -1);
    mn.resize(sz << 1, 1e9 + 7);
    for (int i = 0; i < (int)(n); ++i) mn[i + sz] = v[i];
    for (int i = sz - 1; i; --i) pushup(i);
  }
  void upd(int l, int r, int v) {
    l += sz, r += sz;
    for (int i = _lg; i; --i) {
      if (((l >> i) << i) != l) pushdown(l >> i);
      if (((r >> i) << i) != r) pushdown(r >> i);
    }
    int l0 = l, r0 = r;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) push(l++, v);
      if (r & 1) push(--r, v);
    }
    for (int i = 1; i <= _lg; ++i) {
      if (((l0 >> i) << i) != l0) pushup(l0 >> i);
      if (((r0 >> i) << i) != r0) pushup(r0 >> i);
    }
  }
  int qry(int l, int r) {
    l += sz, r += sz;
    for (int i = _lg; i; --i) {
      if (((l >> i) << i) != l) pushdown(l >> i);
      if (((r >> i) << i) != r) pushdown(r >> i);
    }
    int ans = 1e9 + 7;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ans = min(ans, mn[l++]);
      if (r & 1) ans = min(ans, mn[--r]);
    }
    return ans;
  }
};
int n, k, b[100005], mb, q;
struct Qry {
  int tp, l, r, x;
} qry[100005];
vector<int> sepr, ini;
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 0; i < (int)(n); ++i) scanf("%d", &b[i]);
  mb = b[0];
  for (int i = 0; i < (int)(n); ++i) mb = min(mb, b[i]);
  RangeMinimumQuery rmq(vector<int>(b, b + n));
  scanf("%d", &q);
  for (int i = 0; i < (int)(q); ++i) {
    scanf("%d %d %d", &qry[i].tp, &qry[i].l, &qry[i].r);
    --qry[i].l;
    sepr.push_back(qry[i].l), sepr.push_back(qry[i].r);
    if (qry[i].tp == 1) scanf("%d", &qry[i].x);
  }
  sepr.push_back(0);
  sepr.push_back(k * n);
  sort(sepr.begin(), sepr.end());
  sepr.erase(unique(sepr.begin(), sepr.end()), sepr.end());
  for (int i = 0; i < (int)(sepr.size() - 1); ++i)
    ini.push_back(rmq.per_qry(sepr[i], sepr[i + 1]));
  SegmentTreeLazy seg(ini);
  for (int i = 0; i < (int)(q); ++i) {
    int l = lower_bound(sepr.begin(), sepr.end(), qry[i].l) - sepr.begin();
    int r = lower_bound(sepr.begin(), sepr.end(), qry[i].r) - sepr.begin();
    if (qry[i].tp == 1)
      seg.upd(l, r, qry[i].x);
    else
      printf("%d\n", seg.qry(l, r));
  }
  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;
struct RangeMinimumQuery {
  vector<int> v;
  vector<vector<int> > mn;
  vector<int> _lg;
  RangeMinimumQuery(const vector<int> &_v) {
    v = _v;
    int n = v.size();
    mn.resize(20);
    for (int i = 0; i < (int)(mn.size()); ++i) mn[i].resize(n);
    for (int i = 0; i < (int)(n); ++i) mn[0][i] = v[i];
    for (int j = 0; j < (int)(20 - 1); ++j)
      for (int i = 0; i < (int)(n - (1 << (j + 1)) + 1); ++i)
        mn[j + 1][i] = min(mn[j][i], mn[j][i + (1 << j)]);
    _lg.resize(n + 1);
    for (int i = 0; i < (int)(n + 1); ++i)
      if (i > 1) _lg[i] = _lg[i >> 1] + 1;
  }
  int qry(int l, int r) {
    if (l == r) return 1e9 + 7;
    int k = _lg[r - l];
    return min(mn[k][l], mn[k][r - (1 << k)]);
  }
  int per_qry(int l, int r) {
    if (l == r) return 1e9 + 7;
    if (r - l >= v.size()) return qry(0, v.size());
    int nl = l % v.size(), nr = r % v.size();
    if (nl < nr)
      return qry(nl, nr);
    else
      return min(qry(nl, v.size()), qry(0, nr));
  }
};
struct SegmentTreeLazy {
  int sz, _lg;
  vector<int> tag, mn;
  inline void push(int x, int v) { mn[x] = v, tag[x] = v; }
  inline void pushdown(int x) {
    if (tag[x] != -1)
      push(x << 1, tag[x]), push(x << 1 | 1, tag[x]), tag[x] = -1;
  }
  inline void pushup(int x) { mn[x] = min(mn[x << 1], mn[x << 1 | 1]); }
  SegmentTreeLazy(const vector<int> &v) {
    int n = v.size();
    for (sz = 1, _lg = 0; sz < n; sz <<= 1, ++_lg)
      ;
    tag.resize(sz << 1, -1);
    mn.resize(sz << 1, 1e9 + 7);
    for (int i = 0; i < (int)(n); ++i) mn[i + sz] = v[i];
    for (int i = sz - 1; i; --i) pushup(i);
  }
  void upd(int l, int r, int v) {
    l += sz, r += sz;
    for (int i = _lg; i; --i) {
      if (((l >> i) << i) != l) pushdown(l >> i);
      if (((r >> i) << i) != r) pushdown(r >> i);
    }
    int l0 = l, r0 = r;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) push(l++, v);
      if (r & 1) push(--r, v);
    }
    for (int i = 1; i <= _lg; ++i) {
      if (((l0 >> i) << i) != l0) pushup(l0 >> i);
      if (((r0 >> i) << i) != r0) pushup(r0 >> i);
    }
  }
  int qry(int l, int r) {
    l += sz, r += sz;
    for (int i = _lg; i; --i) {
      if (((l >> i) << i) != l) pushdown(l >> i);
      if (((r >> i) << i) != r) pushdown(r >> i);
    }
    int ans = 1e9 + 7;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ans = min(ans, mn[l++]);
      if (r & 1) ans = min(ans, mn[--r]);
    }
    return ans;
  }
};
int n, k, b[100005], mb, q;
struct Qry {
  int tp, l, r, x;
} qry[100005];
vector<int> sepr, ini;
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 0; i < (int)(n); ++i) scanf("%d", &b[i]);
  mb = b[0];
  for (int i = 0; i < (int)(n); ++i) mb = min(mb, b[i]);
  RangeMinimumQuery rmq(vector<int>(b, b + n));
  scanf("%d", &q);
  for (int i = 0; i < (int)(q); ++i) {
    scanf("%d %d %d", &qry[i].tp, &qry[i].l, &qry[i].r);
    --qry[i].l;
    sepr.push_back(qry[i].l), sepr.push_back(qry[i].r);
    if (qry[i].tp == 1) scanf("%d", &qry[i].x);
  }
  sepr.push_back(0);
  sepr.push_back(k * n);
  sort(sepr.begin(), sepr.end());
  sepr.erase(unique(sepr.begin(), sepr.end()), sepr.end());
  for (int i = 0; i < (int)(sepr.size() - 1); ++i)
    ini.push_back(rmq.per_qry(sepr[i], sepr[i + 1]));
  SegmentTreeLazy seg(ini);
  for (int i = 0; i < (int)(q); ++i) {
    int l = lower_bound(sepr.begin(), sepr.end(), qry[i].l) - sepr.begin();
    int r = lower_bound(sepr.begin(), sepr.end(), qry[i].r) - sepr.begin();
    if (qry[i].tp == 1)
      seg.upd(l, r, qry[i].x);
    else
      printf("%d\n", seg.qry(l, r));
  }
  return 0;
}

```