#include <bits/stdc++.h>
const int N = 100005, inf = 1000000007;
using namespace std;
int n, m, f[N][21], cnt, MN;
set<pair<int, int> > R;
struct poi {
  int l, r, cov;
} a[N << 2];
void modify(int l, int r, int x) {
  ++cnt;
  a[cnt].l = l, a[cnt].r = r, a[cnt].cov = x;
  int pos = cnt;
  std ::set<pair<int, int> >::iterator it;
  for (it = R.lower_bound(make_pair(l, 0)); it != R.end();
       it = R.lower_bound(make_pair(l, 0))) {
    int u = (*it).second;
    if (a[u].l > r) break;
    if (a[u].l >= l && a[u].r <= r) {
      R.erase(make_pair(a[u].r, u));
      continue;
    }
    if (a[u].l < l && a[u].r <= r) {
      R.erase(make_pair(a[u].r, u));
      a[u].r = l - 1;
      R.insert(make_pair(a[u].r, u));
      continue;
    }
    if (a[u].l < l && a[u].r > r) {
      R.erase(make_pair(a[u].r, u));
      int tmp = a[u].r;
      a[u].r = l - 1;
      R.insert(make_pair(a[u].r, u));
      ++cnt;
      a[cnt].l = r + 1, a[cnt].r = tmp, a[cnt].cov = a[u].cov;
      R.insert(make_pair(tmp, cnt));
      break;
    }
    if (a[u].l <= r && a[u].r > r) {
      a[u].l = r + 1;
      continue;
    }
  }
  R.insert(make_pair(r, pos));
}
int get(int l, int r) {
  int i = floor(log(r - l + 1) / log(2));
  return min(f[l][i], f[r - (1 << i) + 1][i]);
}
int calc(int l, int r) {
  if (l > r) return inf;
  int L = (l - 1) / n + 1, R = (r - 1) / n + 1;
  l = (l - 1) % n + 1;
  r = (r - 1) % n + 1;
  if (L == R) return get(l, r);
  if (L + 1 == R) return min(get(l, n), get(1, r));
  return get(1, n);
}
void solve(int l, int r) {
  int ret = inf, las = l - 1;
  std ::set<pair<int, int> >::iterator it;
  for (it = R.lower_bound(make_pair(l, 0)); it != R.end(); ++it) {
    int u = (*it).second;
    if (a[u].l > r) break;
    ret = min(ret, a[u].cov);
    ret = min(ret, calc(las + 1, a[u].l - 1));
    las = a[u].r;
    if (ret == MN) break;
  }
  ret = min(ret, calc(las + 1, r));
  printf("%d\n", ret);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &f[i][0]);
  for (int j = 1; j <= 20; ++j)
    for (int i = 1; i <= n - (1 << (j - 1)); ++i)
      f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
  int q, op, l, r, x;
  scanf("%d", &q);
  MN = get(1, n);
  for (int cas = 1; cas <= q; ++cas) {
    scanf("%d", &op);
    if (op & 1) {
      scanf("%d%d%d", &l, &r, &x);
      MN = min(MN, x);
      modify(l, r, x);
    } else {
      scanf("%d%d", &l, &r);
      solve(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 int N = 100005, inf = 1000000007;
using namespace std;
int n, m, f[N][21], cnt, MN;
set<pair<int, int> > R;
struct poi {
  int l, r, cov;
} a[N << 2];
void modify(int l, int r, int x) {
  ++cnt;
  a[cnt].l = l, a[cnt].r = r, a[cnt].cov = x;
  int pos = cnt;
  std ::set<pair<int, int> >::iterator it;
  for (it = R.lower_bound(make_pair(l, 0)); it != R.end();
       it = R.lower_bound(make_pair(l, 0))) {
    int u = (*it).second;
    if (a[u].l > r) break;
    if (a[u].l >= l && a[u].r <= r) {
      R.erase(make_pair(a[u].r, u));
      continue;
    }
    if (a[u].l < l && a[u].r <= r) {
      R.erase(make_pair(a[u].r, u));
      a[u].r = l - 1;
      R.insert(make_pair(a[u].r, u));
      continue;
    }
    if (a[u].l < l && a[u].r > r) {
      R.erase(make_pair(a[u].r, u));
      int tmp = a[u].r;
      a[u].r = l - 1;
      R.insert(make_pair(a[u].r, u));
      ++cnt;
      a[cnt].l = r + 1, a[cnt].r = tmp, a[cnt].cov = a[u].cov;
      R.insert(make_pair(tmp, cnt));
      break;
    }
    if (a[u].l <= r && a[u].r > r) {
      a[u].l = r + 1;
      continue;
    }
  }
  R.insert(make_pair(r, pos));
}
int get(int l, int r) {
  int i = floor(log(r - l + 1) / log(2));
  return min(f[l][i], f[r - (1 << i) + 1][i]);
}
int calc(int l, int r) {
  if (l > r) return inf;
  int L = (l - 1) / n + 1, R = (r - 1) / n + 1;
  l = (l - 1) % n + 1;
  r = (r - 1) % n + 1;
  if (L == R) return get(l, r);
  if (L + 1 == R) return min(get(l, n), get(1, r));
  return get(1, n);
}
void solve(int l, int r) {
  int ret = inf, las = l - 1;
  std ::set<pair<int, int> >::iterator it;
  for (it = R.lower_bound(make_pair(l, 0)); it != R.end(); ++it) {
    int u = (*it).second;
    if (a[u].l > r) break;
    ret = min(ret, a[u].cov);
    ret = min(ret, calc(las + 1, a[u].l - 1));
    las = a[u].r;
    if (ret == MN) break;
  }
  ret = min(ret, calc(las + 1, r));
  printf("%d\n", ret);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &f[i][0]);
  for (int j = 1; j <= 20; ++j)
    for (int i = 1; i <= n - (1 << (j - 1)); ++i)
      f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
  int q, op, l, r, x;
  scanf("%d", &q);
  MN = get(1, n);
  for (int cas = 1; cas <= q; ++cas) {
    scanf("%d", &op);
    if (op & 1) {
      scanf("%d%d%d", &l, &r, &x);
      MN = min(MN, x);
      modify(l, r, x);
    } else {
      scanf("%d%d", &l, &r);
      solve(l, r);
    }
  }
  return 0;
}

```