#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, k, in[N], a[N << 2], stpos[N << 1], ttop, tot, cnt, m, op[N], inx[N],
    l0[N], r0[N], tmp[N];
struct node {
  int l, r, mn, lz;
  node *ls, *rs;
} pool[N << 4], *root0, *root;
void pdn(node *t) {
  if (t->ls && t->lz) t->ls->lz = t->rs->lz = 1, t->ls->mn = t->rs->mn = t->mn;
  t->lz = 0;
}
node *build(int l, int r, int tp) {
  node *t = &pool[++cnt];
  t->l = l;
  t->r = r;
  if (l == r) {
    t->mn = tp ? a[l] : in[l];
    return t;
  }
  int mid = l + r >> 1;
  t->ls = build(l, mid, tp);
  t->rs = build(mid + 1, r, tp);
  t->mn = min(t->ls->mn, t->rs->mn);
  return t;
}
int qrymn(node *t, int l, int r) {
  pdn(t);
  if (l <= t->l && r >= t->r) return t->mn;
  int mid = t->l + t->r >> 1, ret = 2147483600;
  if (r > mid) ret = min(ret, qrymn(t->rs, l, r));
  if (l <= mid) ret = min(ret, qrymn(t->ls, l, r));
  return ret;
}
int cal1(int l, int r) {
  int ret = 2020;
  for (int i = l; i <= r; i++) ret = min(ret, in[(i - 1) % n + 1]);
  return ret;
}
int cal(int l, int r) {
  if (r - l >= n - 1) return root0->mn;
  l = (l - 1) % n + 1;
  r = (r - 1) % n + 1;
  if (r >= l) return qrymn(root0, l, r);
  return min(qrymn(root0, l, n), qrymn(root0, 1, r));
}
map<int, int> mp;
void chg(node *t, int l, int r, int val) {
  pdn(t);
  if (l <= t->l && r >= t->r) {
    t->mn = val, t->lz = 1;
    return;
  }
  int mid = t->l + t->r >> 1;
  if (l <= mid) chg(t->ls, l, r, val);
  if (r > mid) chg(t->rs, l, r, val);
  t->mn = min(t->ls->mn, t->rs->mn);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", in + i);
  root0 = build(1, n, 0);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", op + i, l0 + i, r0 + i);
    if (op[i] == 1) scanf("%d", inx + i);
    stpos[++ttop] = l0[i];
    stpos[++ttop] = r0[i];
  }
  sort(stpos + 1, stpos + 1 + ttop);
  for (int i = 1; i <= ttop; i++)
    if (i == 1 || stpos[i] == stpos[i - 1] + 1)
      a[mp[stpos[i]] = ++tot] = in[(stpos[i] - 1) % n + 1];
    else if (stpos[i] != stpos[i - 1]) {
      a[++tot] = cal(stpos[i - 1] + 1, stpos[i] - 1);
      a[mp[stpos[i]] = ++tot] = in[(stpos[i] - 1) % n + 1];
    }
  root = build(1, tot, 1);
  for (int i = 1; i <= m; i++) {
    if (op[i] == 1)
      chg(root, mp[l0[i]], mp[r0[i]], inx[i]);
    else
      printf("%d\n", qrymn(root, mp[l0[i]], mp[r0[i]]));
  }
}

### 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;
const int N = 100010;
int n, k, in[N], a[N << 2], stpos[N << 1], ttop, tot, cnt, m, op[N], inx[N],
    l0[N], r0[N], tmp[N];
struct node {
  int l, r, mn, lz;
  node *ls, *rs;
} pool[N << 4], *root0, *root;
void pdn(node *t) {
  if (t->ls && t->lz) t->ls->lz = t->rs->lz = 1, t->ls->mn = t->rs->mn = t->mn;
  t->lz = 0;
}
node *build(int l, int r, int tp) {
  node *t = &pool[++cnt];
  t->l = l;
  t->r = r;
  if (l == r) {
    t->mn = tp ? a[l] : in[l];
    return t;
  }
  int mid = l + r >> 1;
  t->ls = build(l, mid, tp);
  t->rs = build(mid + 1, r, tp);
  t->mn = min(t->ls->mn, t->rs->mn);
  return t;
}
int qrymn(node *t, int l, int r) {
  pdn(t);
  if (l <= t->l && r >= t->r) return t->mn;
  int mid = t->l + t->r >> 1, ret = 2147483600;
  if (r > mid) ret = min(ret, qrymn(t->rs, l, r));
  if (l <= mid) ret = min(ret, qrymn(t->ls, l, r));
  return ret;
}
int cal1(int l, int r) {
  int ret = 2020;
  for (int i = l; i <= r; i++) ret = min(ret, in[(i - 1) % n + 1]);
  return ret;
}
int cal(int l, int r) {
  if (r - l >= n - 1) return root0->mn;
  l = (l - 1) % n + 1;
  r = (r - 1) % n + 1;
  if (r >= l) return qrymn(root0, l, r);
  return min(qrymn(root0, l, n), qrymn(root0, 1, r));
}
map<int, int> mp;
void chg(node *t, int l, int r, int val) {
  pdn(t);
  if (l <= t->l && r >= t->r) {
    t->mn = val, t->lz = 1;
    return;
  }
  int mid = t->l + t->r >> 1;
  if (l <= mid) chg(t->ls, l, r, val);
  if (r > mid) chg(t->rs, l, r, val);
  t->mn = min(t->ls->mn, t->rs->mn);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", in + i);
  root0 = build(1, n, 0);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", op + i, l0 + i, r0 + i);
    if (op[i] == 1) scanf("%d", inx + i);
    stpos[++ttop] = l0[i];
    stpos[++ttop] = r0[i];
  }
  sort(stpos + 1, stpos + 1 + ttop);
  for (int i = 1; i <= ttop; i++)
    if (i == 1 || stpos[i] == stpos[i - 1] + 1)
      a[mp[stpos[i]] = ++tot] = in[(stpos[i] - 1) % n + 1];
    else if (stpos[i] != stpos[i - 1]) {
      a[++tot] = cal(stpos[i - 1] + 1, stpos[i] - 1);
      a[mp[stpos[i]] = ++tot] = in[(stpos[i] - 1) % n + 1];
    }
  root = build(1, tot, 1);
  for (int i = 1; i <= m; i++) {
    if (op[i] == 1)
      chg(root, mp[l0[i]], mp[r0[i]], inx[i]);
    else
      printf("%d\n", qrymn(root, mp[l0[i]], mp[r0[i]]));
  }
}

```