#include <bits/stdc++.h>
using namespace std;
void ga(int N, int *A) {
  for (int i(0); i < N; i++) scanf("%d", A + i);
}
struct RMQ {
  int dp[(1 << (17))][(17) + 2], G[(1 << (17))], XX, O = -1;
  void ini(int *A, int n) {
    if (!XX++)
      for (int k(1); k < (1 << (17)); k++) G[k] = O += (!(k & (k - 1)));
    for (int i(0); i < n; i++) dp[i][0] = i;
    for (int k(1); k < k - (1 << k) + n + 1; k++)
      for (int i(0); i < n + 1 - (1 << k); i++)
        if (A[dp[i][k - 1]] < A[dp[i + (1 << (k - 1))][k - 1]])
          dp[i][k] = dp[i][k - 1];
        else
          dp[i][k] = dp[i + (1 << (k - 1))][k - 1];
  }
  int qy(int *A, int L, int R) {
    int j(G[R - L + 1]);
    if (A[dp[L][j]] <= A[dp[R - (1 << j) + 1][j]]) return A[dp[L][j]];
    return A[dp[R - (1 << j) + 1][j]];
  }
} R;
int N, A[(1 << (17))], K, a, b, c;
int GET(int b, int e) {
  if (e - b + 1 >= N) return R.qy(A, 0, N - 1);
  if (b / N == e / N) return R.qy(A, b % N, e % N);
  return min(R.qy(A, 0, e % N), R.qy(A, b % N, N - 1));
}
struct sX {
  int p[((1 << (17)) * 40)], P[((1 << (17)) * 40)], L[((1 << (17)) * 40)],
      R[((1 << (17)) * 40)];
  int N, l;
  int nw(int b, int e) {
    return L[l] = R[l] = P[l] = -1, p[l] = GET(b, e), l++;
  }
  void ini(int n) { N = 1 << (int(log2(n) - (1e-10)) + 1), nw(0, N - 1); }
  int VL(int u, int b, int e) { return ~u ? ~P[u] ? P[u] : p[u] : GET(b, e); }
  void st(int b, int e, int v) { st(b, e, v, 0, 0, N - 1); }
  int st(int b, int e, int v, int u, int B, int E) {
    if (B > e || E < b) return u;
    if (!~u) u = nw(B, E);
    if (b <= B && e >= E) return P[u] = v, u;
    if (~P[u])
      L[u] = st(B, E, P[u], L[u], B, (B + E) >> 1),
      R[u] = st(B, E, P[u], R[u], (B + E) / 2 + 1, E), P[u] = -1;
    L[u] = st(b, e, v, L[u], B, (B + E) >> 1),
    R[u] = st(b, e, v, R[u], (B + E) / 2 + 1, E);
    p[u] = min(VL(L[u], B, (B + E) >> 1), VL(R[u], (B + E) / 2 + 1, E));
    return u;
  }
  int gt(int b, int e) { return gt(b, e, 0, 0, N - 1); }
  int gt(int b, int e, int u, int B, int E) {
    if (B > e || E < b) return 2e9;
    if (!~u) return GET(max(b, B), min(e, E));
    if (b <= B && e >= E) return VL(u, B, E);
    if (~P[u]) return P[u];
    return min(gt(b, e, L[u], B, (B + E) >> 1),
               gt(b, e, R[u], (B + E) / 2 + 1, E));
  }
} T;
int main(void) {
  scanf("%d%d", &N, &K), ga(N, A), R.ini(A, N), T.ini(N * K);
  int Q;
  scanf("%d", &Q);
  for (int i(0); i < Q; i++) {
    scanf("%d%d%d", &a, &b, &c), --c, --b;
    if (a == 1)
      scanf("%d", &a), T.st(b, c, a);
    else
      printf("%d\n", T.gt(b, c));
    assert(T.l < ((1 << (17)) * 40));
  }
  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>
using namespace std;
void ga(int N, int *A) {
  for (int i(0); i < N; i++) scanf("%d", A + i);
}
struct RMQ {
  int dp[(1 << (17))][(17) + 2], G[(1 << (17))], XX, O = -1;
  void ini(int *A, int n) {
    if (!XX++)
      for (int k(1); k < (1 << (17)); k++) G[k] = O += (!(k & (k - 1)));
    for (int i(0); i < n; i++) dp[i][0] = i;
    for (int k(1); k < k - (1 << k) + n + 1; k++)
      for (int i(0); i < n + 1 - (1 << k); i++)
        if (A[dp[i][k - 1]] < A[dp[i + (1 << (k - 1))][k - 1]])
          dp[i][k] = dp[i][k - 1];
        else
          dp[i][k] = dp[i + (1 << (k - 1))][k - 1];
  }
  int qy(int *A, int L, int R) {
    int j(G[R - L + 1]);
    if (A[dp[L][j]] <= A[dp[R - (1 << j) + 1][j]]) return A[dp[L][j]];
    return A[dp[R - (1 << j) + 1][j]];
  }
} R;
int N, A[(1 << (17))], K, a, b, c;
int GET(int b, int e) {
  if (e - b + 1 >= N) return R.qy(A, 0, N - 1);
  if (b / N == e / N) return R.qy(A, b % N, e % N);
  return min(R.qy(A, 0, e % N), R.qy(A, b % N, N - 1));
}
struct sX {
  int p[((1 << (17)) * 40)], P[((1 << (17)) * 40)], L[((1 << (17)) * 40)],
      R[((1 << (17)) * 40)];
  int N, l;
  int nw(int b, int e) {
    return L[l] = R[l] = P[l] = -1, p[l] = GET(b, e), l++;
  }
  void ini(int n) { N = 1 << (int(log2(n) - (1e-10)) + 1), nw(0, N - 1); }
  int VL(int u, int b, int e) { return ~u ? ~P[u] ? P[u] : p[u] : GET(b, e); }
  void st(int b, int e, int v) { st(b, e, v, 0, 0, N - 1); }
  int st(int b, int e, int v, int u, int B, int E) {
    if (B > e || E < b) return u;
    if (!~u) u = nw(B, E);
    if (b <= B && e >= E) return P[u] = v, u;
    if (~P[u])
      L[u] = st(B, E, P[u], L[u], B, (B + E) >> 1),
      R[u] = st(B, E, P[u], R[u], (B + E) / 2 + 1, E), P[u] = -1;
    L[u] = st(b, e, v, L[u], B, (B + E) >> 1),
    R[u] = st(b, e, v, R[u], (B + E) / 2 + 1, E);
    p[u] = min(VL(L[u], B, (B + E) >> 1), VL(R[u], (B + E) / 2 + 1, E));
    return u;
  }
  int gt(int b, int e) { return gt(b, e, 0, 0, N - 1); }
  int gt(int b, int e, int u, int B, int E) {
    if (B > e || E < b) return 2e9;
    if (!~u) return GET(max(b, B), min(e, E));
    if (b <= B && e >= E) return VL(u, B, E);
    if (~P[u]) return P[u];
    return min(gt(b, e, L[u], B, (B + E) >> 1),
               gt(b, e, R[u], (B + E) / 2 + 1, E));
  }
} T;
int main(void) {
  scanf("%d%d", &N, &K), ga(N, A), R.ini(A, N), T.ini(N * K);
  int Q;
  scanf("%d", &Q);
  for (int i(0); i < Q; i++) {
    scanf("%d%d%d", &a, &b, &c), --c, --b;
    if (a == 1)
      scanf("%d", &a), T.st(b, c, a);
    else
      printf("%d\n", T.gt(b, c));
    assert(T.l < ((1 << (17)) * 40));
  }
  return 0;
}

```