#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int Log[100005];
int n, k, m, q, sx, b[100005], c[100005 << 1], v[100005 << 2];
int mi[19][100005];
int L, R, val, t[100005 << 4 | 3], f[100005 << 4 | 3];
struct node {
  int l, r, x;
} a[100005];
inline int rd() {
  int res = 0;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  while (c >= '0' && c <= '9') res = res * 10 + c - '0', c = getchar();
  return res;
}
inline int minh(int x, int y) { return b[x] < b[y] ? x : y; }
inline int Q(int l, int r) {
  int d = Log[r - l + 1];
  return minh(mi[d][l], mi[d][r - (1 << d) + 1]);
}
inline void build_ST() {
  int i, j, d, t;
  for (i = 1; i <= n; i++) mi[0][i] = i;
  for (j = 1; (d = 1 << j) <= n; j++)
    for (i = 1, t = d >> 1; i + d - 1 <= n; i++)
      mi[j][i] = minh(mi[j - 1][i], mi[j - 1][i + t]);
  j--;
  sx = minh(mi[j][1], mi[j][n - (1 << j) + 1]);
}
inline int minx(int l, int r) {
  int s = (l - 1) / n, t = (r - 1) / n, p;
  if (r - l + 1 >= n) {
    s = s * n + sx;
    if (s < l) s += n;
    return s;
  } else {
    if (s == t) {
      s *= n;
      return Q(l - s, r - s) + s;
    } else {
      p = minh(Q(l - s * n, n), Q(1, r - t * n)) + s * n;
      while (p < l) p += n;
      return p;
    }
  }
  return 0;
}
inline void build(int p, int l, int r) {
  if (l == r) {
    t[p] = b[(v[l] - 1) % n + 1];
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
  t[p] = min(t[p << 1], t[p << 1 | 1]);
}
inline void modify(int p, int l, int r) {
  if (L <= l && R >= r) {
    t[p] = f[p] = val;
    return;
  }
  int mid = (l + r) >> 1;
  if (f[p])
    t[p << 1] = t[p << 1 | 1] = f[p << 1] = f[p << 1 | 1] = f[p], f[p] = 0;
  if (L <= mid) modify(p << 1, l, mid);
  if (R > mid) modify(p << 1 | 1, mid + 1, r);
  t[p] = min(t[p << 1], t[p << 1 | 1]);
}
inline int query(int p, int l, int r) {
  if ((L <= l && R >= r) || f[p]) return t[p];
  int mid = (l + r) >> 1, res = inf;
  if (L <= mid) res = query(p << 1, l, mid);
  if (R > mid) res = min(res, query(p << 1 | 1, mid + 1, r));
  return res;
}
int main() {
  n = rd(), k = rd();
  int i, op;
  Log[0] = -1;
  for (i = 1; i <= n; i++) b[i] = rd(), Log[i] = Log[i >> 1] + 1;
  build_ST();
  q = rd();
  for (i = 1; i <= q; i++) {
    op = rd();
    c[++m] = a[i].l = rd(), c[++m] = a[i].r = rd();
    if (op == 1) a[i].x = rd();
  }
  sort(c + 1, c + 1 + m);
  op = 1;
  v[1] = c[1];
  for (i = 2; i <= m; i++) {
    if (c[i] == c[i - 1]) continue;
    if (c[i] != c[i - 1] + 1) v[++op] = minx(c[i - 1] + 1, c[i] - 1);
    v[++op] = c[i];
  }
  m = op;
  build(1, 1, m);
  for (i = 1; i <= q; i++) {
    L = lower_bound(v + 1, v + m + 1, a[i].l) - v,
    R = lower_bound(v + 1, v + m + 1, a[i].r) - v;
    if (a[i].x)
      val = a[i].x, modify(1, 1, m);
    else
      printf("%d\n", query(1, 1, m));
  }
  return 0;
}

### Prompt

Your challenge is to write 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 inf = 1e9;
int Log[100005];
int n, k, m, q, sx, b[100005], c[100005 << 1], v[100005 << 2];
int mi[19][100005];
int L, R, val, t[100005 << 4 | 3], f[100005 << 4 | 3];
struct node {
  int l, r, x;
} a[100005];
inline int rd() {
  int res = 0;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  while (c >= '0' && c <= '9') res = res * 10 + c - '0', c = getchar();
  return res;
}
inline int minh(int x, int y) { return b[x] < b[y] ? x : y; }
inline int Q(int l, int r) {
  int d = Log[r - l + 1];
  return minh(mi[d][l], mi[d][r - (1 << d) + 1]);
}
inline void build_ST() {
  int i, j, d, t;
  for (i = 1; i <= n; i++) mi[0][i] = i;
  for (j = 1; (d = 1 << j) <= n; j++)
    for (i = 1, t = d >> 1; i + d - 1 <= n; i++)
      mi[j][i] = minh(mi[j - 1][i], mi[j - 1][i + t]);
  j--;
  sx = minh(mi[j][1], mi[j][n - (1 << j) + 1]);
}
inline int minx(int l, int r) {
  int s = (l - 1) / n, t = (r - 1) / n, p;
  if (r - l + 1 >= n) {
    s = s * n + sx;
    if (s < l) s += n;
    return s;
  } else {
    if (s == t) {
      s *= n;
      return Q(l - s, r - s) + s;
    } else {
      p = minh(Q(l - s * n, n), Q(1, r - t * n)) + s * n;
      while (p < l) p += n;
      return p;
    }
  }
  return 0;
}
inline void build(int p, int l, int r) {
  if (l == r) {
    t[p] = b[(v[l] - 1) % n + 1];
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
  t[p] = min(t[p << 1], t[p << 1 | 1]);
}
inline void modify(int p, int l, int r) {
  if (L <= l && R >= r) {
    t[p] = f[p] = val;
    return;
  }
  int mid = (l + r) >> 1;
  if (f[p])
    t[p << 1] = t[p << 1 | 1] = f[p << 1] = f[p << 1 | 1] = f[p], f[p] = 0;
  if (L <= mid) modify(p << 1, l, mid);
  if (R > mid) modify(p << 1 | 1, mid + 1, r);
  t[p] = min(t[p << 1], t[p << 1 | 1]);
}
inline int query(int p, int l, int r) {
  if ((L <= l && R >= r) || f[p]) return t[p];
  int mid = (l + r) >> 1, res = inf;
  if (L <= mid) res = query(p << 1, l, mid);
  if (R > mid) res = min(res, query(p << 1 | 1, mid + 1, r));
  return res;
}
int main() {
  n = rd(), k = rd();
  int i, op;
  Log[0] = -1;
  for (i = 1; i <= n; i++) b[i] = rd(), Log[i] = Log[i >> 1] + 1;
  build_ST();
  q = rd();
  for (i = 1; i <= q; i++) {
    op = rd();
    c[++m] = a[i].l = rd(), c[++m] = a[i].r = rd();
    if (op == 1) a[i].x = rd();
  }
  sort(c + 1, c + 1 + m);
  op = 1;
  v[1] = c[1];
  for (i = 2; i <= m; i++) {
    if (c[i] == c[i - 1]) continue;
    if (c[i] != c[i - 1] + 1) v[++op] = minx(c[i - 1] + 1, c[i] - 1);
    v[++op] = c[i];
  }
  m = op;
  build(1, 1, m);
  for (i = 1; i <= q; i++) {
    L = lower_bound(v + 1, v + m + 1, a[i].l) - v,
    R = lower_bound(v + 1, v + m + 1, a[i].r) - v;
    if (a[i].x)
      val = a[i].x, modify(1, 1, m);
    else
      printf("%d\n", query(1, 1, m));
  }
  return 0;
}

```