#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1 << 18, MAXLG = 18;
const int INF = 2e9;
int N, K, Q;
int A[MAXN], table[MAXN][MAXLG], lg[MAXN];
int L[MAXN], R[MAXN], X[MAXN];
vector<int> vals;
int querytab(int x, int y) {
  int g = lg[y - x];
  return min(table[x][g], table[y - (1 << g)][g]);
}
int getmn(int x, int y) {
  if (y - x >= N) {
    return querytab(0, N);
  }
  int nmlt = x / N * N;
  x -= nmlt;
  y -= nmlt;
  return querytab(x, y);
}
int tree[2 * MAXN], lazy[2 * MAXN];
void put(int cur, int v) {
  tree[cur] = v;
  lazy[cur] = v;
}
void down(int cur) {
  if (lazy[cur] != INF) {
    put(2 * cur, lazy[cur]);
    put(2 * cur + 1, lazy[cur]);
    lazy[cur] = INF;
  }
}
void update(int a, int b, int v, int cur = 1, int lt = 0, int rt = MAXN) {
  if (rt <= a || b <= lt) {
    return;
  }
  if (a <= lt && rt <= b) {
    put(cur, v);
    return;
  }
  down(cur);
  int mid = (lt + rt) / 2;
  update(a, b, v, 2 * cur, lt, mid);
  update(a, b, v, 2 * cur + 1, mid, rt);
  tree[cur] = min(tree[2 * cur], tree[2 * cur + 1]);
}
int query(int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
  if (rt <= a || b <= lt) {
    return INF;
  }
  if (a <= lt && rt <= b) {
    return tree[cur];
  }
  down(cur);
  int mid = (lt + rt) / 2;
  return min(query(a, b, 2 * cur, lt, mid), query(a, b, 2 * cur + 1, mid, rt));
}
int main() {
  scanf("%d %d", &N, &K);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    A[i + N] = A[i];
  }
  for (int i = 0; i < 2 * N; i++) {
    table[i][0] = A[i];
  }
  for (int j = 1; j < MAXLG; j++) {
    for (int i = 0; i + (1 << j) <= 2 * N; i++) {
      table[i][j] = min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (int i = 2; i < MAXN; i++) {
    lg[i] = lg[i >> 1] + 1;
  }
  scanf("%d", &Q);
  for (int i = 0; i < Q; i++) {
    int qt;
    scanf("%d %d %d", &qt, &L[i], &R[i]);
    L[i]--;
    if (qt == 1) {
      scanf("%d", &X[i]);
    } else {
      X[i] = -1;
    }
    vals.push_back(L[i]);
    vals.push_back(R[i]);
  }
  vals.push_back(0);
  vals.push_back(N * K);
  sort((vals).begin(), (vals).end());
  vals.resize(unique((vals).begin(), (vals).end()) - vals.begin());
  fill_n(tree + MAXN, MAXN, INF);
  for (int i = 0; i + 1 < vals.size(); i++) {
    tree[i + MAXN] = getmn(vals[i], vals[i + 1]);
  }
  for (int i = MAXN - 1; i; i--) {
    tree[i] = min(tree[2 * i], tree[2 * i + 1]);
  }
  fill_n(lazy, 2 * MAXN, INF);
  for (int i = 0; i < Q; i++) {
    int lt = lower_bound((vals).begin(), (vals).end(), L[i]) - vals.begin();
    int rt = lower_bound((vals).begin(), (vals).end(), R[i]) - vals.begin();
    if (X[i] == -1) {
      printf("%d\n", query(lt, rt));
    } else {
      update(lt, rt, X[i]);
    }
  }
}

### 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 int MAXN = 1 << 18, MAXLG = 18;
const int INF = 2e9;
int N, K, Q;
int A[MAXN], table[MAXN][MAXLG], lg[MAXN];
int L[MAXN], R[MAXN], X[MAXN];
vector<int> vals;
int querytab(int x, int y) {
  int g = lg[y - x];
  return min(table[x][g], table[y - (1 << g)][g]);
}
int getmn(int x, int y) {
  if (y - x >= N) {
    return querytab(0, N);
  }
  int nmlt = x / N * N;
  x -= nmlt;
  y -= nmlt;
  return querytab(x, y);
}
int tree[2 * MAXN], lazy[2 * MAXN];
void put(int cur, int v) {
  tree[cur] = v;
  lazy[cur] = v;
}
void down(int cur) {
  if (lazy[cur] != INF) {
    put(2 * cur, lazy[cur]);
    put(2 * cur + 1, lazy[cur]);
    lazy[cur] = INF;
  }
}
void update(int a, int b, int v, int cur = 1, int lt = 0, int rt = MAXN) {
  if (rt <= a || b <= lt) {
    return;
  }
  if (a <= lt && rt <= b) {
    put(cur, v);
    return;
  }
  down(cur);
  int mid = (lt + rt) / 2;
  update(a, b, v, 2 * cur, lt, mid);
  update(a, b, v, 2 * cur + 1, mid, rt);
  tree[cur] = min(tree[2 * cur], tree[2 * cur + 1]);
}
int query(int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
  if (rt <= a || b <= lt) {
    return INF;
  }
  if (a <= lt && rt <= b) {
    return tree[cur];
  }
  down(cur);
  int mid = (lt + rt) / 2;
  return min(query(a, b, 2 * cur, lt, mid), query(a, b, 2 * cur + 1, mid, rt));
}
int main() {
  scanf("%d %d", &N, &K);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    A[i + N] = A[i];
  }
  for (int i = 0; i < 2 * N; i++) {
    table[i][0] = A[i];
  }
  for (int j = 1; j < MAXLG; j++) {
    for (int i = 0; i + (1 << j) <= 2 * N; i++) {
      table[i][j] = min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (int i = 2; i < MAXN; i++) {
    lg[i] = lg[i >> 1] + 1;
  }
  scanf("%d", &Q);
  for (int i = 0; i < Q; i++) {
    int qt;
    scanf("%d %d %d", &qt, &L[i], &R[i]);
    L[i]--;
    if (qt == 1) {
      scanf("%d", &X[i]);
    } else {
      X[i] = -1;
    }
    vals.push_back(L[i]);
    vals.push_back(R[i]);
  }
  vals.push_back(0);
  vals.push_back(N * K);
  sort((vals).begin(), (vals).end());
  vals.resize(unique((vals).begin(), (vals).end()) - vals.begin());
  fill_n(tree + MAXN, MAXN, INF);
  for (int i = 0; i + 1 < vals.size(); i++) {
    tree[i + MAXN] = getmn(vals[i], vals[i + 1]);
  }
  for (int i = MAXN - 1; i; i--) {
    tree[i] = min(tree[2 * i], tree[2 * i + 1]);
  }
  fill_n(lazy, 2 * MAXN, INF);
  for (int i = 0; i < Q; i++) {
    int lt = lower_bound((vals).begin(), (vals).end(), L[i]) - vals.begin();
    int rt = lower_bound((vals).begin(), (vals).end(), R[i]) - vals.begin();
    if (X[i] == -1) {
      printf("%d\n", query(lt, rt));
    } else {
      update(lt, rt, X[i]);
    }
  }
}

```