#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int LN = 20;
int a[N], _log[N];
int n, k;
struct SparseTable {
  int table[N][LN], n;
  SparseTable() {}
  SparseTable(int n) : n(n) {
    for (int i = 0; i < n; i++) table[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; j++)
      for (int i = 0; i + (1 << j) - 1 < n; i++)
        table[i][j] = min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
  }
  int query(int l, int r) {
    if (r >= l) {
      int tam = r - l + 1;
      return min(table[l][_log[tam]],
                 table[r - (1 << _log[tam]) + 1][_log[tam]]);
    } else
      return min(query(0, r), query(l, n - 1));
  }
} st;
struct node {
  int value, lazy;
  node *l, *r;
  node() {
    l = r = NULL;
    value = lazy = 0x3f3f3f3f;
  }
};
void prop(node *at, int i, int j) {
  if (at->lazy == 0x3f3f3f3f) return;
  at->value = at->lazy;
  if (i != j) {
    if (at->l == NULL) at->l = new node();
    if (at->r == NULL) at->r = new node();
    at->l->lazy = at->r->lazy = at->lazy;
  }
  at->lazy = 0x3f3f3f3f;
}
int query(node *at, int i, int j, int a, int b, int k) {
  prop(at, i, j);
  if (i > b or j < a) return 0x3f3f3f3f;
  if (i >= a and j <= b) {
    at->lazy = k;
    prop(at, i, j);
    return at->value;
  }
  int mid = (i + j) / 2;
  if (at->l == NULL) {
    at->l = new node();
    if (mid - i + 1 >= n)
      at->l->value = st.query(0, n - 1);
    else
      at->l->value = st.query(i % n, mid % n);
  }
  if (at->r == NULL) {
    at->r = new node();
    if (j - (mid + 1) + 1 >= n)
      at->r->value = st.query(0, n - 1);
    else
      at->r->value = st.query((mid + 1) % n, j % n);
  }
  int ret =
      min(query(at->l, i, mid, a, b, k), query(at->r, mid + 1, j, a, b, k));
  at->value = min(at->l->value, at->r->value);
  return ret;
}
int main(void) {
  _log[1] = 0;
  for (int i = 2; i < N; i++) {
    _log[i] = _log[i - 1];
    if ((1 << (_log[i] + 1)) == i) _log[i]++;
  }
  node *root = new node();
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", a + i);
  st = SparseTable(n);
  root->value = st.query(0, n - 1);
  int q;
  scanf("%d", &q);
  int m = n * k - 1;
  while (q--) {
    int t, l, r, x;
    scanf("%d %d %d", &t, &l, &r);
    l--;
    r--;
    if (t == 1) {
      scanf("%d", &x);
      query(root, 0, m, l, r, x);
    } else {
      cout << query(root, 0, m, l, r, 0x3f3f3f3f) << endl;
    }
  }
  return 0;
}

### 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 N = 100010;
const int LN = 20;
int a[N], _log[N];
int n, k;
struct SparseTable {
  int table[N][LN], n;
  SparseTable() {}
  SparseTable(int n) : n(n) {
    for (int i = 0; i < n; i++) table[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; j++)
      for (int i = 0; i + (1 << j) - 1 < n; i++)
        table[i][j] = min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
  }
  int query(int l, int r) {
    if (r >= l) {
      int tam = r - l + 1;
      return min(table[l][_log[tam]],
                 table[r - (1 << _log[tam]) + 1][_log[tam]]);
    } else
      return min(query(0, r), query(l, n - 1));
  }
} st;
struct node {
  int value, lazy;
  node *l, *r;
  node() {
    l = r = NULL;
    value = lazy = 0x3f3f3f3f;
  }
};
void prop(node *at, int i, int j) {
  if (at->lazy == 0x3f3f3f3f) return;
  at->value = at->lazy;
  if (i != j) {
    if (at->l == NULL) at->l = new node();
    if (at->r == NULL) at->r = new node();
    at->l->lazy = at->r->lazy = at->lazy;
  }
  at->lazy = 0x3f3f3f3f;
}
int query(node *at, int i, int j, int a, int b, int k) {
  prop(at, i, j);
  if (i > b or j < a) return 0x3f3f3f3f;
  if (i >= a and j <= b) {
    at->lazy = k;
    prop(at, i, j);
    return at->value;
  }
  int mid = (i + j) / 2;
  if (at->l == NULL) {
    at->l = new node();
    if (mid - i + 1 >= n)
      at->l->value = st.query(0, n - 1);
    else
      at->l->value = st.query(i % n, mid % n);
  }
  if (at->r == NULL) {
    at->r = new node();
    if (j - (mid + 1) + 1 >= n)
      at->r->value = st.query(0, n - 1);
    else
      at->r->value = st.query((mid + 1) % n, j % n);
  }
  int ret =
      min(query(at->l, i, mid, a, b, k), query(at->r, mid + 1, j, a, b, k));
  at->value = min(at->l->value, at->r->value);
  return ret;
}
int main(void) {
  _log[1] = 0;
  for (int i = 2; i < N; i++) {
    _log[i] = _log[i - 1];
    if ((1 << (_log[i] + 1)) == i) _log[i]++;
  }
  node *root = new node();
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", a + i);
  st = SparseTable(n);
  root->value = st.query(0, n - 1);
  int q;
  scanf("%d", &q);
  int m = n * k - 1;
  while (q--) {
    int t, l, r, x;
    scanf("%d %d %d", &t, &l, &r);
    l--;
    r--;
    if (t == 1) {
      scanf("%d", &x);
      query(root, 0, m, l, r, x);
    } else {
      cout << query(root, 0, m, l, r, 0x3f3f3f3f) << endl;
    }
  }
  return 0;
}

```