#include <bits/stdc++.h>
using namespace std;
struct Query {
  int l, r, x;
  Query(int l = 0, int r = 0, int x = 0) : l(l), r(r), x(x) {}
};
struct node {
  int pref, suff, val;
  node(int pref = 0, int suff = 0, int val = 0)
      : pref(pref), suff(suff), val(val) {}
};
int n, k;
map<int, int> ha;
int hacnt;
int a[100005];
node st[4000000];
int lazy[4000000];
Query queries[100005];
int ori[1000005];
bool changed[1000000];
set<int> vals;
int mn;
int st1[5000000];
void build1(int p = 1, int l = 0, int r = n - 1) {
  if (l == r) {
    st1[p] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build1(p * 2, l, mid);
  build1(p * 2 + 1, mid + 1, r);
  st1[p] = min(st1[p * 2], st1[p * 2 + 1]);
}
int query1(int i, int j, int p = 1, int l = 0, int r = n - 1) {
  if (i > r || j < l) return 1e9 + 3;
  if (i <= l && j >= r) return st1[p];
  int mid = (l + r) >> 1;
  int c1 = query1(i, j, p * 2, l, mid);
  int c2 = query1(i, j, p * 2 + 1, mid + 1, r);
  return min(c1, c2);
}
int get(int l, int r) {
  if (l > r) return 1000000008;
  if (r - l + 1 >= n) return mn;
  l %= n, r %= n;
  if (l > r) return min(query1(l, n - 1), query1(0, r));
  return query1(l, r);
}
void merge(node& ret, node& x, node& y) {
  ret.pref = x.pref;
  ret.suff = y.suff;
  ret.val = min(x.val, x.suff);
  ret.val = min(ret.val, min(y.val, y.pref));
}
void pushLazy(int p) {
  if (lazy[p]) {
    lazy[p * 2] = lazy[p * 2 + 1] = lazy[p];
    st[p] = node(1000000008, 1000000008, lazy[p]);
    lazy[p] = 0;
  }
}
void build(int p = 1, int l = 1, int r = hacnt - 1) {
  if (l == r) {
    if (l != 1)
      st[p].pref = get(ori[l - 1] + 1, ori[l] - 1);
    else
      st[p].pref = 1000000008;
    if (r != hacnt - 1)
      st[p].suff = get(ori[r] + 1, ori[r + 1] - 1);
    else
      st[p].suff = 1000000008;
    st[p].val = get(ori[l], ori[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(p * 2, l, mid);
  build(p * 2 + 1, mid + 1, r);
  merge(st[p], st[p * 2], st[p * 2 + 1]);
}
void update(int i, int j, int x, int p = 1, int l = 1, int r = hacnt - 1) {
  pushLazy(p);
  if (i > r || j < l) return;
  if (i <= l && j >= r) {
    lazy[p] = x;
    pushLazy(p);
    return;
  }
  int mid = (l + r) >> 1;
  update(i, j, x, p * 2, l, mid);
  update(i, j, x, p * 2 + 1, mid + 1, r);
  merge(st[p], st[p * 2], st[p * 2 + 1]);
}
int query(int i, int j, int p = 1, int l = 1, int r = hacnt - 1) {
  pushLazy(p);
  if (i > r || j < l) return 1000000008;
  if (i <= l && j >= r) {
    int ret = 1000000008;
    if (i != l) ret = min(ret, st[p].pref);
    if (j != r) ret = min(ret, st[p].suff);
    ret = min(ret, st[p].val);
    return ret;
  }
  int mid = (l + r) >> 1;
  int c1 = query(i, j, p * 2, l, mid);
  int c2 = query(i, j, p * 2 + 1, mid + 1, r);
  return min(c1, c2);
}
int main() {
  scanf("%d%d", &n, &k);
  mn = 1e9 + 1;
  for (int i = 0; i < n; i++) scanf("%d", &a[i]), mn = min(mn, a[i]);
  build1();
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int l, r, x;
      scanf("%d%d%d", &l, &r, &x);
      l--, r--;
      queries[i] = Query(l, r, x);
      ha[l];
      ha[r];
    } else {
      int l, r;
      scanf("%d%d", &l, &r);
      l--, r--;
      ha[l];
      ha[r];
      queries[i] = Query(l, r, -1);
    }
  }
  hacnt = 1;
  for (map<int, int>::iterator it = ha.begin(); it != ha.end(); it++) {
    it->second = hacnt;
    ori[hacnt] = it->first;
    vals.insert(hacnt);
    hacnt++;
  }
  build();
  for (int i = 0; i < q; i++) {
    int l = queries[i].l, r = queries[i].r, x = queries[i].x;
    if (x < 0) {
      int ans = query(ha[l], ha[r]);
      printf("%d\n", ans);
    } else {
      update(ha[l], ha[r], x);
      int from = ha[l];
      int to = ha[r];
      while (1) {
        set<int>::iterator it = vals.lower_bound(from);
        if (it == vals.end() || *it > to) break;
        changed[*it] = 1;
        vals.erase(it);
      }
    }
  }
  return 0;
}

### Prompt

Develop a solution in cpp 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 Query {
  int l, r, x;
  Query(int l = 0, int r = 0, int x = 0) : l(l), r(r), x(x) {}
};
struct node {
  int pref, suff, val;
  node(int pref = 0, int suff = 0, int val = 0)
      : pref(pref), suff(suff), val(val) {}
};
int n, k;
map<int, int> ha;
int hacnt;
int a[100005];
node st[4000000];
int lazy[4000000];
Query queries[100005];
int ori[1000005];
bool changed[1000000];
set<int> vals;
int mn;
int st1[5000000];
void build1(int p = 1, int l = 0, int r = n - 1) {
  if (l == r) {
    st1[p] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build1(p * 2, l, mid);
  build1(p * 2 + 1, mid + 1, r);
  st1[p] = min(st1[p * 2], st1[p * 2 + 1]);
}
int query1(int i, int j, int p = 1, int l = 0, int r = n - 1) {
  if (i > r || j < l) return 1e9 + 3;
  if (i <= l && j >= r) return st1[p];
  int mid = (l + r) >> 1;
  int c1 = query1(i, j, p * 2, l, mid);
  int c2 = query1(i, j, p * 2 + 1, mid + 1, r);
  return min(c1, c2);
}
int get(int l, int r) {
  if (l > r) return 1000000008;
  if (r - l + 1 >= n) return mn;
  l %= n, r %= n;
  if (l > r) return min(query1(l, n - 1), query1(0, r));
  return query1(l, r);
}
void merge(node& ret, node& x, node& y) {
  ret.pref = x.pref;
  ret.suff = y.suff;
  ret.val = min(x.val, x.suff);
  ret.val = min(ret.val, min(y.val, y.pref));
}
void pushLazy(int p) {
  if (lazy[p]) {
    lazy[p * 2] = lazy[p * 2 + 1] = lazy[p];
    st[p] = node(1000000008, 1000000008, lazy[p]);
    lazy[p] = 0;
  }
}
void build(int p = 1, int l = 1, int r = hacnt - 1) {
  if (l == r) {
    if (l != 1)
      st[p].pref = get(ori[l - 1] + 1, ori[l] - 1);
    else
      st[p].pref = 1000000008;
    if (r != hacnt - 1)
      st[p].suff = get(ori[r] + 1, ori[r + 1] - 1);
    else
      st[p].suff = 1000000008;
    st[p].val = get(ori[l], ori[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(p * 2, l, mid);
  build(p * 2 + 1, mid + 1, r);
  merge(st[p], st[p * 2], st[p * 2 + 1]);
}
void update(int i, int j, int x, int p = 1, int l = 1, int r = hacnt - 1) {
  pushLazy(p);
  if (i > r || j < l) return;
  if (i <= l && j >= r) {
    lazy[p] = x;
    pushLazy(p);
    return;
  }
  int mid = (l + r) >> 1;
  update(i, j, x, p * 2, l, mid);
  update(i, j, x, p * 2 + 1, mid + 1, r);
  merge(st[p], st[p * 2], st[p * 2 + 1]);
}
int query(int i, int j, int p = 1, int l = 1, int r = hacnt - 1) {
  pushLazy(p);
  if (i > r || j < l) return 1000000008;
  if (i <= l && j >= r) {
    int ret = 1000000008;
    if (i != l) ret = min(ret, st[p].pref);
    if (j != r) ret = min(ret, st[p].suff);
    ret = min(ret, st[p].val);
    return ret;
  }
  int mid = (l + r) >> 1;
  int c1 = query(i, j, p * 2, l, mid);
  int c2 = query(i, j, p * 2 + 1, mid + 1, r);
  return min(c1, c2);
}
int main() {
  scanf("%d%d", &n, &k);
  mn = 1e9 + 1;
  for (int i = 0; i < n; i++) scanf("%d", &a[i]), mn = min(mn, a[i]);
  build1();
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int l, r, x;
      scanf("%d%d%d", &l, &r, &x);
      l--, r--;
      queries[i] = Query(l, r, x);
      ha[l];
      ha[r];
    } else {
      int l, r;
      scanf("%d%d", &l, &r);
      l--, r--;
      ha[l];
      ha[r];
      queries[i] = Query(l, r, -1);
    }
  }
  hacnt = 1;
  for (map<int, int>::iterator it = ha.begin(); it != ha.end(); it++) {
    it->second = hacnt;
    ori[hacnt] = it->first;
    vals.insert(hacnt);
    hacnt++;
  }
  build();
  for (int i = 0; i < q; i++) {
    int l = queries[i].l, r = queries[i].r, x = queries[i].x;
    if (x < 0) {
      int ans = query(ha[l], ha[r]);
      printf("%d\n", ans);
    } else {
      update(ha[l], ha[r], x);
      int from = ha[l];
      int to = ha[r];
      while (1) {
        set<int>::iterator it = vals.lower_bound(from);
        if (it == vals.end() || *it > to) break;
        changed[*it] = 1;
        vals.erase(it);
      }
    }
  }
  return 0;
}

```