#include <bits/stdc++.h>
const double Pi = 3.14159265;
const int N = 1e7 + 10;
const int M = 1e5 + 10;
const unsigned long long base = 163;
const int INF = 0x3f3f3f3f;
const int mod = 192600817;
const double eps = 1e-10;
const double pi = acos(-1);
using namespace std;
int n, k, cnt;
int b[M];
int rc[N], lc[N], MIN[N], lz[N];
int MM = INF;
struct RMQ {
  int st[M][32];
  inline void init_ST() {
    for (int i = 1; i <= n; ++i) st[i][0] = b[i];
    int k = 31 - __builtin_clz(n);
    for (int j = 1; j <= k; ++j) {
      for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
        st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  inline int rmq(int l, int r) {
    int k = 31 - __builtin_clz(r - l + 1);
    return min(st[l][k], st[r - (1 << k) + 1][k]);
  }
} rmq;
int cal(int l, int r) {
  if (r - l + 1 >= n) return MM;
  --l, --r;
  if (l / n == r / n)
    return rmq.rmq(l % n + 1, r % n + 1);
  else
    return min(rmq.rmq(l % n + 1, n), rmq.rmq(1, r % n + 1));
}
void pushup(int rt, int l, int r) {
  int L = lc[rt], R = rc[rt], mid = (r + l) / 2;
  MIN[rt] =
      min((L == 0 ? cal(l, mid) : MIN[L]), (R == 0 ? cal(mid + 1, r) : MIN[R]));
}
void pushdown(int rt, int l, int r) {
  if (!lz[rt]) return;
  int &L = lc[rt];
  int &R = rc[rt];
  if (!L) L = ++cnt;
  MIN[L] = lz[rt];
  if (!R) R = ++cnt;
  MIN[R] = lz[rt];
  lz[L] = lz[rt];
  lz[R] = lz[rt];
  lz[rt] = 0;
}
void update(int &rt, int l, int r, int L, int R, int x) {
  if (!rt) rt = ++cnt, MIN[rt] = cal(l, r);
  if (L <= l && R >= r) {
    MIN[rt] = x;
    lz[rt] = x;
    return;
  }
  pushdown(rt, l, r);
  int mid = (l + r) >> 1;
  if (L <= mid) update(lc[rt], l, mid, L, R, x);
  if (R > mid) update(rc[rt], mid + 1, r, L, R, x);
  pushup(rt, l, r);
}
int query(int &rt, int l, int r, int L, int R) {
  if (!rt) rt = ++cnt, MIN[rt] = cal(l, r);
  if (L <= l && R >= r) {
    return MIN[rt];
  }
  pushdown(rt, l, r);
  int ans = INF;
  int mid = (l + r) >> 1;
  if (L <= mid) ans = min(ans, query(lc[rt], l, mid, L, R));
  if (R > mid) ans = min(ans, query(rc[rt], mid + 1, r, L, R));
  pushup(rt, l, r);
  return ans;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &b[i]), MM = min(MM, b[i]);
  rmq.init_ST();
  int q;
  scanf("%d", &q);
  int rt = 0;
  while (q--) {
    int id, l, r, x;
    scanf("%d%d%d", &id, &l, &r);
    if (id == 1) {
      scanf("%d", &x);
      update(rt, 1, n * k, l, r, x);
    } else {
      printf("%d\n", query(rt, 1, n * k, 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>
const double Pi = 3.14159265;
const int N = 1e7 + 10;
const int M = 1e5 + 10;
const unsigned long long base = 163;
const int INF = 0x3f3f3f3f;
const int mod = 192600817;
const double eps = 1e-10;
const double pi = acos(-1);
using namespace std;
int n, k, cnt;
int b[M];
int rc[N], lc[N], MIN[N], lz[N];
int MM = INF;
struct RMQ {
  int st[M][32];
  inline void init_ST() {
    for (int i = 1; i <= n; ++i) st[i][0] = b[i];
    int k = 31 - __builtin_clz(n);
    for (int j = 1; j <= k; ++j) {
      for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
        st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  inline int rmq(int l, int r) {
    int k = 31 - __builtin_clz(r - l + 1);
    return min(st[l][k], st[r - (1 << k) + 1][k]);
  }
} rmq;
int cal(int l, int r) {
  if (r - l + 1 >= n) return MM;
  --l, --r;
  if (l / n == r / n)
    return rmq.rmq(l % n + 1, r % n + 1);
  else
    return min(rmq.rmq(l % n + 1, n), rmq.rmq(1, r % n + 1));
}
void pushup(int rt, int l, int r) {
  int L = lc[rt], R = rc[rt], mid = (r + l) / 2;
  MIN[rt] =
      min((L == 0 ? cal(l, mid) : MIN[L]), (R == 0 ? cal(mid + 1, r) : MIN[R]));
}
void pushdown(int rt, int l, int r) {
  if (!lz[rt]) return;
  int &L = lc[rt];
  int &R = rc[rt];
  if (!L) L = ++cnt;
  MIN[L] = lz[rt];
  if (!R) R = ++cnt;
  MIN[R] = lz[rt];
  lz[L] = lz[rt];
  lz[R] = lz[rt];
  lz[rt] = 0;
}
void update(int &rt, int l, int r, int L, int R, int x) {
  if (!rt) rt = ++cnt, MIN[rt] = cal(l, r);
  if (L <= l && R >= r) {
    MIN[rt] = x;
    lz[rt] = x;
    return;
  }
  pushdown(rt, l, r);
  int mid = (l + r) >> 1;
  if (L <= mid) update(lc[rt], l, mid, L, R, x);
  if (R > mid) update(rc[rt], mid + 1, r, L, R, x);
  pushup(rt, l, r);
}
int query(int &rt, int l, int r, int L, int R) {
  if (!rt) rt = ++cnt, MIN[rt] = cal(l, r);
  if (L <= l && R >= r) {
    return MIN[rt];
  }
  pushdown(rt, l, r);
  int ans = INF;
  int mid = (l + r) >> 1;
  if (L <= mid) ans = min(ans, query(lc[rt], l, mid, L, R));
  if (R > mid) ans = min(ans, query(rc[rt], mid + 1, r, L, R));
  pushup(rt, l, r);
  return ans;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &b[i]), MM = min(MM, b[i]);
  rmq.init_ST();
  int q;
  scanf("%d", &q);
  int rt = 0;
  while (q--) {
    int id, l, r, x;
    scanf("%d%d%d", &id, &l, &r);
    if (id == 1) {
      scanf("%d", &x);
      update(rt, 1, n * k, l, r, x);
    } else {
      printf("%d\n", query(rt, 1, n * k, l, r));
    }
  }
  return 0;
}

```