#include <bits/stdc++.h>
using namespace std;
const long long N = 1e6 + 22;
long long n, k, t;
long long a[N];
long long qt[N], ql[N], qr[N], qx[N];
vector<long long> v;
struct segtree {
  long long seg[N * 4], flag[N * 4];
  void build(long long ind, long long s, long long e) {
    if (s == e - 1) {
      seg[ind] = a[s];
      return;
    }
    long long mid = (s + e) / 2;
    build(((ind)*2), s, mid), build(((ind)*2 + 1), mid, e);
    seg[ind] = min(seg[((ind)*2)], seg[((ind)*2 + 1)]);
  }
  void relax(long long ind) {
    if (!flag[ind]) return;
    seg[((ind)*2)] = seg[((ind)*2 + 1)] = flag[((ind)*2)] =
        flag[((ind)*2 + 1)] = flag[ind];
    flag[ind] = 0;
  }
  void add(long long ind, long long s, long long e, long long l, long long r,
           long long x) {
    if (s >= r || l >= e) return;
    if (l <= s && e <= r) {
      seg[ind] = x;
      flag[ind] = x;
      return;
    }
    long long mid = (s + e) / 2;
    relax(ind);
    add(((ind)*2), s, mid, l, r, x), add(((ind)*2 + 1), mid, e, l, r, x);
    seg[ind] = min(seg[((ind)*2 + 1)], seg[((ind)*2)]);
  }
  long long solve(long long ind, long long s, long long e, long long l,
                  long long r) {
    if (s >= r || l >= e) return (2e9);
    if (l <= s && e <= r) return seg[ind];
    long long mid = (s + e) / 2;
    relax(ind);
    return min(solve(((ind)*2), s, mid, l, r),
               solve(((ind)*2 + 1), mid, e, l, r));
  }
} s1, s2;
int32_t main() {
  cin >> n >> k;
  for (long long i = 0; i < (n); i++) cin >> a[i];
  s1.build(1, 0, n);
  cin >> t;
  for (long long i = 0; i < (t); i++) {
    cin >> qt[i] >> ql[i] >> qr[i];
    if (qt[i] == 1) cin >> qx[i];
    ql[i]--;
    v.push_back(ql[i]), v.push_back(qr[i]);
  }
  v.push_back(n * k);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (long long i = 0; i < (v.size() - 1); i++) {
    long long x = v[i], y = v[i + 1];
    y--;
    if (x / n + 1 < y / n)
      a[i] = s1.solve(1, 0, n, 0, n);
    else if (x / n + 1 == y / n)
      a[i] = min(s1.solve(1, 0, n, x % n, n), s1.solve(1, 0, n, 0, y % n + 1));
    else
      a[i] = s1.solve(1, 0, n, x % n, y % n + 1);
  }
  n = v.size();
  s2.build(1, 0, n);
  for (long long i = 0; i < (t); i++) {
    ql[i] = lower_bound(v.begin(), v.end(), ql[i]) - v.begin();
    qr[i] = lower_bound(v.begin(), v.end(), qr[i]) - v.begin();
    if (qt[i] == 1)
      s2.add(1, 0, n, ql[i], qr[i], qx[i]);
    else
      cout << s2.solve(1, 0, n, ql[i], qr[i]) << 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 long long N = 1e6 + 22;
long long n, k, t;
long long a[N];
long long qt[N], ql[N], qr[N], qx[N];
vector<long long> v;
struct segtree {
  long long seg[N * 4], flag[N * 4];
  void build(long long ind, long long s, long long e) {
    if (s == e - 1) {
      seg[ind] = a[s];
      return;
    }
    long long mid = (s + e) / 2;
    build(((ind)*2), s, mid), build(((ind)*2 + 1), mid, e);
    seg[ind] = min(seg[((ind)*2)], seg[((ind)*2 + 1)]);
  }
  void relax(long long ind) {
    if (!flag[ind]) return;
    seg[((ind)*2)] = seg[((ind)*2 + 1)] = flag[((ind)*2)] =
        flag[((ind)*2 + 1)] = flag[ind];
    flag[ind] = 0;
  }
  void add(long long ind, long long s, long long e, long long l, long long r,
           long long x) {
    if (s >= r || l >= e) return;
    if (l <= s && e <= r) {
      seg[ind] = x;
      flag[ind] = x;
      return;
    }
    long long mid = (s + e) / 2;
    relax(ind);
    add(((ind)*2), s, mid, l, r, x), add(((ind)*2 + 1), mid, e, l, r, x);
    seg[ind] = min(seg[((ind)*2 + 1)], seg[((ind)*2)]);
  }
  long long solve(long long ind, long long s, long long e, long long l,
                  long long r) {
    if (s >= r || l >= e) return (2e9);
    if (l <= s && e <= r) return seg[ind];
    long long mid = (s + e) / 2;
    relax(ind);
    return min(solve(((ind)*2), s, mid, l, r),
               solve(((ind)*2 + 1), mid, e, l, r));
  }
} s1, s2;
int32_t main() {
  cin >> n >> k;
  for (long long i = 0; i < (n); i++) cin >> a[i];
  s1.build(1, 0, n);
  cin >> t;
  for (long long i = 0; i < (t); i++) {
    cin >> qt[i] >> ql[i] >> qr[i];
    if (qt[i] == 1) cin >> qx[i];
    ql[i]--;
    v.push_back(ql[i]), v.push_back(qr[i]);
  }
  v.push_back(n * k);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (long long i = 0; i < (v.size() - 1); i++) {
    long long x = v[i], y = v[i + 1];
    y--;
    if (x / n + 1 < y / n)
      a[i] = s1.solve(1, 0, n, 0, n);
    else if (x / n + 1 == y / n)
      a[i] = min(s1.solve(1, 0, n, x % n, n), s1.solve(1, 0, n, 0, y % n + 1));
    else
      a[i] = s1.solve(1, 0, n, x % n, y % n + 1);
  }
  n = v.size();
  s2.build(1, 0, n);
  for (long long i = 0; i < (t); i++) {
    ql[i] = lower_bound(v.begin(), v.end(), ql[i]) - v.begin();
    qr[i] = lower_bound(v.begin(), v.end(), qr[i]) - v.begin();
    if (qt[i] == 1)
      s2.add(1, 0, n, ql[i], qr[i], qx[i]);
    else
      cout << s2.solve(1, 0, n, ql[i], qr[i]) << endl;
  }
  return 0;
}

```