#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-7;
const long long INFF = 1e18;
const int INF = 1e9;
const int mod = 1e9 + 7;
const int MAX = 1e5 + 7;
int a[MAX];
struct node2 {
  int v[MAX << 2];
  int ll[MAX << 2], rr[MAX << 2];
  void bd(int l, int r, int p) {
    ll[p] = l;
    rr[p] = r;
    if (l == r) {
      v[p] = a[l];
      return;
    }
    int mid = (l + r) >> 1;
    bd(l, mid, p << 1);
    bd(mid + 1, r, p << 1 | 1);
    v[p] = min(v[p << 1], v[p << 1 | 1]);
  }
  int qy(int l, int r, int p) {
    if (ll[p] == l && rr[p] == r) return v[p];
    int mid = (ll[p] + rr[p]) >> 1;
    if (r <= mid)
      return qy(l, r, p << 1);
    else if (l > mid)
      return qy(l, r, p << 1 | 1);
    else
      return min(qy(l, mid, p << 1), qy(mid + 1, r, p << 1 | 1));
  }
} seg;
struct node {
  static node ptr[MAX * 50], *cntp;
  int l, r;
  int mid() { return (l + r) >> 1; }
  int v;
  bool d;
  node *ls, *rs;
  node() { ls = rs = NULL; }
} node::ptr[MAX * 50], *node::cntp = node::ptr;
node *top = NULL;
int n, k, cntp = 0;
void down(node *rt) { return; }
void push(node *rt) {
  rt->d = 0;
  if (rt->ls == NULL) {
    rt->ls = new (node::cntp++) node();
    rt->ls->l = rt->l;
    rt->ls->r = rt->mid();
  }
  if (rt->rs == NULL) {
    rt->rs = new (node::cntp++) node();
    rt->rs->l = rt->mid() + 1;
    rt->rs->r = rt->r;
  }
  rt->ls->v = rt->v;
  rt->ls->d = 1;
  rt->rs->v = rt->v;
  rt->rs->d = 1;
  return;
}
inline int val(node *rt) { return rt ? rt->v : INF; }
int fd(int l, int r) {
  if (r - l + 1 >= n)
    return seg.qy(1, n, 1);
  else if ((l + n - 1) / n == (r + n - 1) / n)
    return seg.qy(l % n ? l % n : n, r % n ? r % n : n, 1);
  else
    return min(seg.qy(1, r % n ? r % n : n, 1),
               seg.qy(l % n ? l % n : n, n, 1));
}
void md(int l, int r, int v, node *rt) {
  if (rt == NULL) {
    puts("WTF");
    exit(0);
  }
  if (rt->l == l && rt->r == r) {
    rt->d = 1;
    rt->v = v;
    return;
  }
  int mid = rt->mid();
  if (rt->d) push(rt);
  if (r <= mid) {
    if (rt->ls == NULL) {
      rt->ls = new (node::cntp++) node();
      rt->ls->l = rt->l;
      rt->ls->r = rt->mid();
    }
    md(l, r, v, rt->ls);
  } else if (l > mid) {
    if (rt->rs == NULL) {
      rt->rs = new (node::cntp++) node();
      rt->rs->l = rt->mid() + 1;
      rt->rs->r = rt->r;
    }
    md(l, r, v, rt->rs);
  } else {
    if (rt->ls == NULL) {
      rt->ls = new (node::cntp++) node();
      rt->ls->l = rt->l;
      rt->ls->r = rt->mid();
    }
    if (rt->rs == NULL) {
      rt->rs = new (node::cntp++) node();
      rt->rs->l = rt->mid() + 1;
      rt->rs->r = rt->r;
    }
    md(l, mid, v, rt->ls);
    md(mid + 1, r, v, rt->rs);
  }
  if (rt->ls == NULL) {
    rt->ls = new (node::cntp++) node();
    rt->ls->l = rt->l;
    rt->ls->r = rt->mid();
    rt->ls->v = fd(rt->l, rt->mid());
  }
  if (rt->rs == NULL) {
    rt->rs = new (node::cntp++) node();
    rt->rs->l = rt->mid() + 1;
    rt->rs->r = rt->r;
    rt->rs->v = fd(rt->mid() + 1, rt->r);
  }
  rt->v = min(val(rt->ls), val(rt->rs));
  return;
}
int qy(int l, int r, node *rt) {
  if (rt == NULL) {
    return fd(l, r);
  }
  if (rt->l == l && rt->r == r) {
    if (l == r || (rt->ls && rt->rs) || rt->d) return rt->v;
  }
  if (rt->d) push(rt);
  int mid = rt->mid();
  if (r <= mid)
    return qy(l, r, rt->ls);
  else if (l > mid)
    return qy(l, r, rt->rs);
  else
    return min(qy(l, mid, rt->ls), qy(mid + 1, r, rt->rs));
}
int main(void) {
  scanf("%d %d", &n, &k);
  for (int i = (1); i < (n + 1); ++i) scanf("%d", a + i);
  seg.bd(1, n, 1);
  int q;
  scanf("%d", &q);
  ;
  while (q--) {
    int typ;
    scanf("%d", &typ);
    ;
    if (typ == 1) {
      int l, r, x;
      scanf("%d %d %d", &l, &r, &x);
      ;
      if (top == NULL) {
        top = new (node::cntp++) node();
        top->l = 1, top->r = n * k;
      }
      md(l, r, x, top);
    } else {
      int l, r;
      scanf("%d %d", &l, &r);
      ;
      int ans = qy(l, r, top);
      printf("%d\n", ans);
    }
  }
  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;
const double eps = 1e-7;
const long long INFF = 1e18;
const int INF = 1e9;
const int mod = 1e9 + 7;
const int MAX = 1e5 + 7;
int a[MAX];
struct node2 {
  int v[MAX << 2];
  int ll[MAX << 2], rr[MAX << 2];
  void bd(int l, int r, int p) {
    ll[p] = l;
    rr[p] = r;
    if (l == r) {
      v[p] = a[l];
      return;
    }
    int mid = (l + r) >> 1;
    bd(l, mid, p << 1);
    bd(mid + 1, r, p << 1 | 1);
    v[p] = min(v[p << 1], v[p << 1 | 1]);
  }
  int qy(int l, int r, int p) {
    if (ll[p] == l && rr[p] == r) return v[p];
    int mid = (ll[p] + rr[p]) >> 1;
    if (r <= mid)
      return qy(l, r, p << 1);
    else if (l > mid)
      return qy(l, r, p << 1 | 1);
    else
      return min(qy(l, mid, p << 1), qy(mid + 1, r, p << 1 | 1));
  }
} seg;
struct node {
  static node ptr[MAX * 50], *cntp;
  int l, r;
  int mid() { return (l + r) >> 1; }
  int v;
  bool d;
  node *ls, *rs;
  node() { ls = rs = NULL; }
} node::ptr[MAX * 50], *node::cntp = node::ptr;
node *top = NULL;
int n, k, cntp = 0;
void down(node *rt) { return; }
void push(node *rt) {
  rt->d = 0;
  if (rt->ls == NULL) {
    rt->ls = new (node::cntp++) node();
    rt->ls->l = rt->l;
    rt->ls->r = rt->mid();
  }
  if (rt->rs == NULL) {
    rt->rs = new (node::cntp++) node();
    rt->rs->l = rt->mid() + 1;
    rt->rs->r = rt->r;
  }
  rt->ls->v = rt->v;
  rt->ls->d = 1;
  rt->rs->v = rt->v;
  rt->rs->d = 1;
  return;
}
inline int val(node *rt) { return rt ? rt->v : INF; }
int fd(int l, int r) {
  if (r - l + 1 >= n)
    return seg.qy(1, n, 1);
  else if ((l + n - 1) / n == (r + n - 1) / n)
    return seg.qy(l % n ? l % n : n, r % n ? r % n : n, 1);
  else
    return min(seg.qy(1, r % n ? r % n : n, 1),
               seg.qy(l % n ? l % n : n, n, 1));
}
void md(int l, int r, int v, node *rt) {
  if (rt == NULL) {
    puts("WTF");
    exit(0);
  }
  if (rt->l == l && rt->r == r) {
    rt->d = 1;
    rt->v = v;
    return;
  }
  int mid = rt->mid();
  if (rt->d) push(rt);
  if (r <= mid) {
    if (rt->ls == NULL) {
      rt->ls = new (node::cntp++) node();
      rt->ls->l = rt->l;
      rt->ls->r = rt->mid();
    }
    md(l, r, v, rt->ls);
  } else if (l > mid) {
    if (rt->rs == NULL) {
      rt->rs = new (node::cntp++) node();
      rt->rs->l = rt->mid() + 1;
      rt->rs->r = rt->r;
    }
    md(l, r, v, rt->rs);
  } else {
    if (rt->ls == NULL) {
      rt->ls = new (node::cntp++) node();
      rt->ls->l = rt->l;
      rt->ls->r = rt->mid();
    }
    if (rt->rs == NULL) {
      rt->rs = new (node::cntp++) node();
      rt->rs->l = rt->mid() + 1;
      rt->rs->r = rt->r;
    }
    md(l, mid, v, rt->ls);
    md(mid + 1, r, v, rt->rs);
  }
  if (rt->ls == NULL) {
    rt->ls = new (node::cntp++) node();
    rt->ls->l = rt->l;
    rt->ls->r = rt->mid();
    rt->ls->v = fd(rt->l, rt->mid());
  }
  if (rt->rs == NULL) {
    rt->rs = new (node::cntp++) node();
    rt->rs->l = rt->mid() + 1;
    rt->rs->r = rt->r;
    rt->rs->v = fd(rt->mid() + 1, rt->r);
  }
  rt->v = min(val(rt->ls), val(rt->rs));
  return;
}
int qy(int l, int r, node *rt) {
  if (rt == NULL) {
    return fd(l, r);
  }
  if (rt->l == l && rt->r == r) {
    if (l == r || (rt->ls && rt->rs) || rt->d) return rt->v;
  }
  if (rt->d) push(rt);
  int mid = rt->mid();
  if (r <= mid)
    return qy(l, r, rt->ls);
  else if (l > mid)
    return qy(l, r, rt->rs);
  else
    return min(qy(l, mid, rt->ls), qy(mid + 1, r, rt->rs));
}
int main(void) {
  scanf("%d %d", &n, &k);
  for (int i = (1); i < (n + 1); ++i) scanf("%d", a + i);
  seg.bd(1, n, 1);
  int q;
  scanf("%d", &q);
  ;
  while (q--) {
    int typ;
    scanf("%d", &typ);
    ;
    if (typ == 1) {
      int l, r, x;
      scanf("%d %d %d", &l, &r, &x);
      ;
      if (top == NULL) {
        top = new (node::cntp++) node();
        top->l = 1, top->r = n * k;
      }
      md(l, r, x, top);
    } else {
      int l, r;
      scanf("%d %d", &l, &r);
      ;
      int ans = qy(l, r, top);
      printf("%d\n", ans);
    }
  }
  return 0;
}

```