#include <bits/stdc++.h>
using namespace std;
const int INF = 1000 * 1000 * 1000 + 1;
const int N = 100 * 1000 + 10, Np = 1000 * 1000 * 10 + 10;
int arr[N], cl[Np], cr[Np], seg[Np], lz[Np];
bool mark[Np];
int cnt = 2;
int mn[N][20];
int n;
void pre() {
  for (int j = 0; j < 20; j++)
    for (int i = 0; i < n; i++) {
      if (j == 0)
        mn[i][j] = arr[i];
      else
        mn[i][j] = min(mn[i][j - 1], ((i + (1 << (j - 1))) < n)
                                         ? mn[i + (1 << (j - 1))][j - 1]
                                         : INF);
    }
}
int gett(int l, int r) {
  int mnn = INF;
  for (int i = 19; i >= 0; i--)
    if ((l + (1 << i)) <= r) {
      mnn = min(mnn, mn[l][i]);
      l += (1 << i);
      if (l == r) break;
    }
  return mnn;
}
int get(int l, int r) {
  int mnn = INF;
  if (r / n - l / n >= 2)
    mnn = gett(0, n);
  else if (l / n != r / n)
    mnn = min(gett(l % n, n), gett(0, r % n));
  else
    mnn = gett(l % n, r % n);
  return mnn;
}
void relax(int v) {
  if (lz[v] == 0) return;
  lz[cl[v]] = lz[v];
  seg[cl[v]] = lz[v];
  lz[cr[v]] = lz[v];
  seg[cr[v]] = lz[v];
  lz[v] = 0;
}
void upd(int l, int r, int x, int v, int s, int e) {
  if (r <= s || e <= l) return;
  if (l <= s && e <= r) {
    seg[v] = x;
    lz[v] = x;
    return;
  }
  int mid = (s + e) / 2;
  if (!mark[v]) {
    seg[cnt] = get(s, mid);
    cl[v] = cnt++;
    seg[cnt] = get(mid, e);
    cr[v] = cnt++;
    mark[v] = true;
  }
  relax(v);
  upd(l, r, x, cl[v], s, mid);
  upd(l, r, x, cr[v], mid, e);
  seg[v] = min(seg[cl[v]], seg[cr[v]]);
}
int get(int l, int r, int v, int s, int e) {
  if (r <= s || e <= l) return INF;
  if ((l <= s && e <= r) || lz[v] != 0) return seg[v];
  if (!mark[v]) return get(max(l, s), min(r, e));
  int mid = (s + e) / 2;
  return min(get(l, r, cl[v], s, mid), get(l, r, cr[v], mid, e));
}
int main() {
  int k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> arr[i];
  pre();
  seg[1] = get(0, n);
  long long m = n * k;
  int q;
  cin >> q;
  while (q--) {
    int ty, l, r;
    cin >> ty >> l >> r;
    l--;
    if (ty == 1) {
      int x;
      cin >> x;
      upd(l, r, x, 1, 0, m);
    } else {
      cout << get(l, r, 1, 0, m) << endl;
    }
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 = 1000 * 1000 * 1000 + 1;
const int N = 100 * 1000 + 10, Np = 1000 * 1000 * 10 + 10;
int arr[N], cl[Np], cr[Np], seg[Np], lz[Np];
bool mark[Np];
int cnt = 2;
int mn[N][20];
int n;
void pre() {
  for (int j = 0; j < 20; j++)
    for (int i = 0; i < n; i++) {
      if (j == 0)
        mn[i][j] = arr[i];
      else
        mn[i][j] = min(mn[i][j - 1], ((i + (1 << (j - 1))) < n)
                                         ? mn[i + (1 << (j - 1))][j - 1]
                                         : INF);
    }
}
int gett(int l, int r) {
  int mnn = INF;
  for (int i = 19; i >= 0; i--)
    if ((l + (1 << i)) <= r) {
      mnn = min(mnn, mn[l][i]);
      l += (1 << i);
      if (l == r) break;
    }
  return mnn;
}
int get(int l, int r) {
  int mnn = INF;
  if (r / n - l / n >= 2)
    mnn = gett(0, n);
  else if (l / n != r / n)
    mnn = min(gett(l % n, n), gett(0, r % n));
  else
    mnn = gett(l % n, r % n);
  return mnn;
}
void relax(int v) {
  if (lz[v] == 0) return;
  lz[cl[v]] = lz[v];
  seg[cl[v]] = lz[v];
  lz[cr[v]] = lz[v];
  seg[cr[v]] = lz[v];
  lz[v] = 0;
}
void upd(int l, int r, int x, int v, int s, int e) {
  if (r <= s || e <= l) return;
  if (l <= s && e <= r) {
    seg[v] = x;
    lz[v] = x;
    return;
  }
  int mid = (s + e) / 2;
  if (!mark[v]) {
    seg[cnt] = get(s, mid);
    cl[v] = cnt++;
    seg[cnt] = get(mid, e);
    cr[v] = cnt++;
    mark[v] = true;
  }
  relax(v);
  upd(l, r, x, cl[v], s, mid);
  upd(l, r, x, cr[v], mid, e);
  seg[v] = min(seg[cl[v]], seg[cr[v]]);
}
int get(int l, int r, int v, int s, int e) {
  if (r <= s || e <= l) return INF;
  if ((l <= s && e <= r) || lz[v] != 0) return seg[v];
  if (!mark[v]) return get(max(l, s), min(r, e));
  int mid = (s + e) / 2;
  return min(get(l, r, cl[v], s, mid), get(l, r, cr[v], mid, e));
}
int main() {
  int k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> arr[i];
  pre();
  seg[1] = get(0, n);
  long long m = n * k;
  int q;
  cin >> q;
  while (q--) {
    int ty, l, r;
    cin >> ty >> l >> r;
    l--;
    if (ty == 1) {
      int x;
      cin >> x;
      upd(l, r, x, 1, 0, m);
    } else {
      cout << get(l, r, 1, 0, m) << endl;
    }
  }
  return 0;
}

```