#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 10;
const int N = 2e5 + 10;
const int M = 20;
int n, k, m, np;
int a[N];
int p[N];
int rmq[N][M];
pair<int, int> typ[N];
pair<int, int> qu[N];
int callRMQ(int L, int R) {
  int lv = int(log2(R - L + 1));
  return min(rmq[L][lv], rmq[R - (1 << lv) + 1][lv]);
}
struct segtree {
  int b[N << 2], laz[N << 2];
  void build(int node, int L, int R) {
    laz[node] = -1;
    if (L == R) {
      int crL = p[L], crR = p[L + 1];
      if (crR - crL >= n)
        b[node] = callRMQ(0, n - 1);
      else {
        crL %= n, crR %= n;
        if (crL < crR)
          b[node] = callRMQ(crL, crR - 1);
        else
          b[node] = callRMQ(crL, crR + n - 1);
      }
      return;
    }
    build(node * 2, L, (L + R) / 2);
    build(node * 2 + 1, (L + R) / 2 + 1, R);
    b[node] = min(b[node * 2], b[node * 2 + 1]);
  }
  void lazyupdate(int node, int L, int R) {
    if (laz[node] != -1) {
      b[node] = laz[node];
      if (L < R) laz[node * 2] = laz[node * 2 + 1] = laz[node];
      laz[node] = -1;
    }
  }
  void update(int node, int L, int R, int l, int r, int val) {
    lazyupdate(node, L, R);
    if (L > r || R < l) return;
    if (l <= L && R <= r) {
      laz[node] = val;
      lazyupdate(node, L, R);
      return;
    }
    update(node * 2, L, (L + R) / 2, l, r, val);
    update(node * 2 + 1, (L + R) / 2 + 1, R, l, r, val);
    b[node] = min(b[node * 2], b[node * 2 + 1]);
  }
  int get(int node, int L, int R, int l, int r) {
    lazyupdate(node, L, R);
    if (L > r || R < l) return inf;
    if (l <= L && R <= r) return b[node];
    return min(get(node * 2, L, (L + R) / 2, l, r),
               get(node * 2 + 1, (L + R) / 2 + 1, R, l, r));
  }
} mseg;
void prepare() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) a[n + i] = a[i];
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> typ[i].first >> qu[i].first >> qu[i].second;
    if (typ[i].first == 1) cin >> typ[i].second;
    qu[i].first--, qu[i].second--;
  }
  np = 0;
  for (int i = 0; i < m; i++) p[++np] = qu[i].first, p[++np] = qu[i].second + 1;
  p[++np] = n * k;
  p[++np] = 0;
  sort(p + 1, p + np + 1);
  np = unique(p + 1, p + np + 1) - p - 1;
  for (int i = 0; i < 2 * n; i++) rmq[i][0] = a[i];
  for (int j = 1; j < M; j++)
    for (int i = 0; i <= 2 * n - (1 << j); i++)
      rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
  mseg.build(1, 1, np - 1);
}
void solve() {
  for (int i = 0; i < m; i++) {
    int L = lower_bound(p + 1, p + np + 1, qu[i].first) - p;
    int R = lower_bound(p + 1, p + np + 1, qu[i].second + 1) - p - 1;
    if (typ[i].first == 1)
      mseg.update(1, 1, np - 1, L, R, typ[i].second);
    else
      cout << mseg.get(1, 1, np - 1, L, R) << '\n';
  }
}
int main() {
  prepare();
  solve();
}

### Prompt

In Cpp, your task is to solve 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;
const int inf = 1e9 + 10;
const int N = 2e5 + 10;
const int M = 20;
int n, k, m, np;
int a[N];
int p[N];
int rmq[N][M];
pair<int, int> typ[N];
pair<int, int> qu[N];
int callRMQ(int L, int R) {
  int lv = int(log2(R - L + 1));
  return min(rmq[L][lv], rmq[R - (1 << lv) + 1][lv]);
}
struct segtree {
  int b[N << 2], laz[N << 2];
  void build(int node, int L, int R) {
    laz[node] = -1;
    if (L == R) {
      int crL = p[L], crR = p[L + 1];
      if (crR - crL >= n)
        b[node] = callRMQ(0, n - 1);
      else {
        crL %= n, crR %= n;
        if (crL < crR)
          b[node] = callRMQ(crL, crR - 1);
        else
          b[node] = callRMQ(crL, crR + n - 1);
      }
      return;
    }
    build(node * 2, L, (L + R) / 2);
    build(node * 2 + 1, (L + R) / 2 + 1, R);
    b[node] = min(b[node * 2], b[node * 2 + 1]);
  }
  void lazyupdate(int node, int L, int R) {
    if (laz[node] != -1) {
      b[node] = laz[node];
      if (L < R) laz[node * 2] = laz[node * 2 + 1] = laz[node];
      laz[node] = -1;
    }
  }
  void update(int node, int L, int R, int l, int r, int val) {
    lazyupdate(node, L, R);
    if (L > r || R < l) return;
    if (l <= L && R <= r) {
      laz[node] = val;
      lazyupdate(node, L, R);
      return;
    }
    update(node * 2, L, (L + R) / 2, l, r, val);
    update(node * 2 + 1, (L + R) / 2 + 1, R, l, r, val);
    b[node] = min(b[node * 2], b[node * 2 + 1]);
  }
  int get(int node, int L, int R, int l, int r) {
    lazyupdate(node, L, R);
    if (L > r || R < l) return inf;
    if (l <= L && R <= r) return b[node];
    return min(get(node * 2, L, (L + R) / 2, l, r),
               get(node * 2 + 1, (L + R) / 2 + 1, R, l, r));
  }
} mseg;
void prepare() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) a[n + i] = a[i];
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> typ[i].first >> qu[i].first >> qu[i].second;
    if (typ[i].first == 1) cin >> typ[i].second;
    qu[i].first--, qu[i].second--;
  }
  np = 0;
  for (int i = 0; i < m; i++) p[++np] = qu[i].first, p[++np] = qu[i].second + 1;
  p[++np] = n * k;
  p[++np] = 0;
  sort(p + 1, p + np + 1);
  np = unique(p + 1, p + np + 1) - p - 1;
  for (int i = 0; i < 2 * n; i++) rmq[i][0] = a[i];
  for (int j = 1; j < M; j++)
    for (int i = 0; i <= 2 * n - (1 << j); i++)
      rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
  mseg.build(1, 1, np - 1);
}
void solve() {
  for (int i = 0; i < m; i++) {
    int L = lower_bound(p + 1, p + np + 1, qu[i].first) - p;
    int R = lower_bound(p + 1, p + np + 1, qu[i].second + 1) - p - 1;
    if (typ[i].first == 1)
      mseg.update(1, 1, np - 1, L, R, typ[i].second);
    else
      cout << mseg.get(1, 1, np - 1, L, R) << '\n';
  }
}
int main() {
  prepare();
  solve();
}

```