#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1, -1, -1, 0, 1, -1, 0, 1};
int kx8[] = {1, 1, 2, 2, -1, -1, -2, -2};
int ky8[] = {2, -2, 1, -1, 2, -2, 1, -1};
const int M = 1000005;
int a[M], sum[4 * M], prop[4 * M], n, k, N;
struct node {
  int typ, l, r, val;
} dt[M];
void build(int l, int r, int k) {
  if (l == r) {
    sum[k] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(l, mid, k * 2);
  build(mid + 1, r, k * 2 + 1);
  sum[k] = min(sum[k * 2], sum[k * 2 + 1]);
}
long long query(int l, int r, int k, int L, int R) {
  if (l > R || r < L) return 2134567891;
  if (l >= L && r <= R) return sum[k];
  int mid = (l + r) / 2;
  return min(query(l, mid, k * 2, L, R), query(mid + 1, r, k * 2 + 1, L, R));
}
void propagate(int l, int r, int k) {
  if (prop[k] == -1) return;
  if (l != r) {
    prop[k * 2] = prop[k];
    prop[k * 2 + 1] = prop[k];
  }
  sum[k] = prop[k];
  prop[k] = -1;
}
void update(int l, int r, int k, int L, int R, int val) {
  propagate(l, r, k);
  if (l > R || r < L) return;
  if (l >= L && r <= R) {
    prop[k] = val;
    propagate(l, r, k);
    return;
  }
  int mid = (l + r) / 2;
  update(l, mid, k * 2, L, R, val);
  update(mid + 1, r, k * 2 + 1, L, R, val);
  sum[k] = min(sum[k * 2], sum[k * 2 + 1]);
}
long long fquery(int l, int r, int k, int L, int R) {
  propagate(l, r, k);
  if (l > R || r < L) return 2134567891;
  if (l >= L && r <= R) return sum[k];
  int mid = (l + r) / 2;
  return min(fquery(l, mid, k * 2, L, R), fquery(mid + 1, r, k * 2 + 1, L, R));
}
long long extra(long long l, long long r) {
  if (r - l + 1 >= n) return sum[1];
  l = l % n;
  if (l == 0) l = n;
  r = r % n;
  if (r == 0) r = n;
  if (l <= r)
    return query(1, n, 1, l, r);
  else
    return min(query(1, n, 1, 1, r), query(1, n, 1, l, n));
}
map<int, int> mp;
set<int> st;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  build(1, n, 1);
  int m;
  cin >> m;
  for (int i = 0; i < (m); i++) {
    cin >> dt[i].typ >> dt[i].l >> dt[i].r;
    if (dt[i].typ == 1) cin >> dt[i].val;
    st.insert(dt[i].l);
    st.insert(dt[i].r);
  }
  int pre = *st.begin();
  int cnt = 0;
  for (auto x : st) {
    if (x - pre > 1) {
      ++cnt;
      a[cnt] = extra(pre + 1, x - 1);
    }
    ++cnt;
    mp[x] = cnt;
    a[cnt] = extra(x, x);
    pre = x;
  }
  memset((prop), -1, sizeof(prop));
  n = cnt;
  build(1, n, 1);
  for (int i = 0; i < (m); i++) {
    if (dt[i].typ == 1) {
      update(1, n, 1, mp[dt[i].l], mp[dt[i].r], dt[i].val);
    } else {
      cout << fquery(1, n, 1, mp[dt[i].l], mp[dt[i].r]) << endl;
    }
  }
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

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;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1, -1, -1, 0, 1, -1, 0, 1};
int kx8[] = {1, 1, 2, 2, -1, -1, -2, -2};
int ky8[] = {2, -2, 1, -1, 2, -2, 1, -1};
const int M = 1000005;
int a[M], sum[4 * M], prop[4 * M], n, k, N;
struct node {
  int typ, l, r, val;
} dt[M];
void build(int l, int r, int k) {
  if (l == r) {
    sum[k] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(l, mid, k * 2);
  build(mid + 1, r, k * 2 + 1);
  sum[k] = min(sum[k * 2], sum[k * 2 + 1]);
}
long long query(int l, int r, int k, int L, int R) {
  if (l > R || r < L) return 2134567891;
  if (l >= L && r <= R) return sum[k];
  int mid = (l + r) / 2;
  return min(query(l, mid, k * 2, L, R), query(mid + 1, r, k * 2 + 1, L, R));
}
void propagate(int l, int r, int k) {
  if (prop[k] == -1) return;
  if (l != r) {
    prop[k * 2] = prop[k];
    prop[k * 2 + 1] = prop[k];
  }
  sum[k] = prop[k];
  prop[k] = -1;
}
void update(int l, int r, int k, int L, int R, int val) {
  propagate(l, r, k);
  if (l > R || r < L) return;
  if (l >= L && r <= R) {
    prop[k] = val;
    propagate(l, r, k);
    return;
  }
  int mid = (l + r) / 2;
  update(l, mid, k * 2, L, R, val);
  update(mid + 1, r, k * 2 + 1, L, R, val);
  sum[k] = min(sum[k * 2], sum[k * 2 + 1]);
}
long long fquery(int l, int r, int k, int L, int R) {
  propagate(l, r, k);
  if (l > R || r < L) return 2134567891;
  if (l >= L && r <= R) return sum[k];
  int mid = (l + r) / 2;
  return min(fquery(l, mid, k * 2, L, R), fquery(mid + 1, r, k * 2 + 1, L, R));
}
long long extra(long long l, long long r) {
  if (r - l + 1 >= n) return sum[1];
  l = l % n;
  if (l == 0) l = n;
  r = r % n;
  if (r == 0) r = n;
  if (l <= r)
    return query(1, n, 1, l, r);
  else
    return min(query(1, n, 1, 1, r), query(1, n, 1, l, n));
}
map<int, int> mp;
set<int> st;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  build(1, n, 1);
  int m;
  cin >> m;
  for (int i = 0; i < (m); i++) {
    cin >> dt[i].typ >> dt[i].l >> dt[i].r;
    if (dt[i].typ == 1) cin >> dt[i].val;
    st.insert(dt[i].l);
    st.insert(dt[i].r);
  }
  int pre = *st.begin();
  int cnt = 0;
  for (auto x : st) {
    if (x - pre > 1) {
      ++cnt;
      a[cnt] = extra(pre + 1, x - 1);
    }
    ++cnt;
    mp[x] = cnt;
    a[cnt] = extra(x, x);
    pre = x;
  }
  memset((prop), -1, sizeof(prop));
  n = cnt;
  build(1, n, 1);
  for (int i = 0; i < (m); i++) {
    if (dt[i].typ == 1) {
      update(1, n, 1, mp[dt[i].l], mp[dt[i].r], dt[i].val);
    } else {
      cout << fquery(1, n, 1, mp[dt[i].l], mp[dt[i].r]) << endl;
    }
  }
  return 0;
}

```