#include <bits/stdc++.h>
using namespace std;
int N, K, Q;
signed long long B[101010];
static signed long long const def = 1 << 30;
template <class V, int NV>
class SegTree_3 {
 public:
  vector<V> val, mi;
  SegTree_3() {
    val.resize(NV * 2, def);
    mi.resize(NV * 2, def);
  };
  V getval(int x, int y, int l = 0, int r = NV, int k = 1) {
    if (r <= x || y <= l) return def;
    if (x <= l && r <= y) return mi[k];
    if (val[k] != -1) return val[k];
    return min(getval(x, y, l, (l + r) / 2, k * 2),
               getval(x, y, (l + r) / 2, r, k * 2 + 1));
  }
  void update(int x, int y, V v, int l = 0, int r = NV, int k = 1) {
    if (l >= r) return;
    if (x <= l && r <= y) {
      val[k] = mi[k] = v;
    } else if (l < y && x < r) {
      if (val[k] != -1) {
        val[k * 2] = val[k * 2 + 1] = val[k];
        mi[k * 2] = mi[k * 2 + 1] = val[k];
        val[k] = -1;
      }
      update(x, y, v, l, (l + r) / 2, k * 2);
      update(x, y, v, (l + r) / 2, r, k * 2 + 1);
      mi[k] = min(mi[k * 2], mi[k * 2 + 1]);
    }
  }
};
SegTree_3<int, 1 << 20> st1, st2;
int T[101010], L[101010], R[101010], X[101010];
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> N >> K;
  for (i = 0; i < (N); i++)
    cin >> B[i], st1.update(i, i + 1, B[i]), st1.update(i + N, i + N + 1, B[i]);
  cin >> Q;
  vector<int> V;
  V.push_back(0);
  V.push_back(N * K);
  for (i = 0; i < (Q); i++) {
    cin >> T[i] >> L[i] >> R[i];
    L[i]--;
    V.push_back(L[i]);
    V.push_back(R[i]);
    if (T[i] == 1) cin >> X[i];
  }
  sort((V.begin()), (V.end()));
  V.erase(unique((V.begin()), (V.end())), V.end());
  for (i = 0; i < (V.size() - 1); i++) {
    if (V[i + 1] - V[i] >= N) {
      x = st1.getval(0, N);
    } else {
      y = V[i] / N * N;
      x = st1.getval(V[i] - y, V[i + 1] - y);
    }
    st2.update(i, i + 1, x);
  }
  for (i = 0; i < (Q); i++) {
    x = lower_bound((V.begin()), (V.end()), L[i]) - V.begin();
    y = lower_bound((V.begin()), (V.end()), R[i]) - V.begin();
    if (T[i] == 1) {
      st2.update(x, y, X[i]);
    } else {
      cout << st2.getval(x, y) << endl;
    }
  }
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  solve();
  return 0;
}

### Prompt

Create a solution in Cpp for 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 N, K, Q;
signed long long B[101010];
static signed long long const def = 1 << 30;
template <class V, int NV>
class SegTree_3 {
 public:
  vector<V> val, mi;
  SegTree_3() {
    val.resize(NV * 2, def);
    mi.resize(NV * 2, def);
  };
  V getval(int x, int y, int l = 0, int r = NV, int k = 1) {
    if (r <= x || y <= l) return def;
    if (x <= l && r <= y) return mi[k];
    if (val[k] != -1) return val[k];
    return min(getval(x, y, l, (l + r) / 2, k * 2),
               getval(x, y, (l + r) / 2, r, k * 2 + 1));
  }
  void update(int x, int y, V v, int l = 0, int r = NV, int k = 1) {
    if (l >= r) return;
    if (x <= l && r <= y) {
      val[k] = mi[k] = v;
    } else if (l < y && x < r) {
      if (val[k] != -1) {
        val[k * 2] = val[k * 2 + 1] = val[k];
        mi[k * 2] = mi[k * 2 + 1] = val[k];
        val[k] = -1;
      }
      update(x, y, v, l, (l + r) / 2, k * 2);
      update(x, y, v, (l + r) / 2, r, k * 2 + 1);
      mi[k] = min(mi[k * 2], mi[k * 2 + 1]);
    }
  }
};
SegTree_3<int, 1 << 20> st1, st2;
int T[101010], L[101010], R[101010], X[101010];
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> N >> K;
  for (i = 0; i < (N); i++)
    cin >> B[i], st1.update(i, i + 1, B[i]), st1.update(i + N, i + N + 1, B[i]);
  cin >> Q;
  vector<int> V;
  V.push_back(0);
  V.push_back(N * K);
  for (i = 0; i < (Q); i++) {
    cin >> T[i] >> L[i] >> R[i];
    L[i]--;
    V.push_back(L[i]);
    V.push_back(R[i]);
    if (T[i] == 1) cin >> X[i];
  }
  sort((V.begin()), (V.end()));
  V.erase(unique((V.begin()), (V.end())), V.end());
  for (i = 0; i < (V.size() - 1); i++) {
    if (V[i + 1] - V[i] >= N) {
      x = st1.getval(0, N);
    } else {
      y = V[i] / N * N;
      x = st1.getval(V[i] - y, V[i + 1] - y);
    }
    st2.update(i, i + 1, x);
  }
  for (i = 0; i < (Q); i++) {
    x = lower_bound((V.begin()), (V.end()), L[i]) - V.begin();
    y = lower_bound((V.begin()), (V.end()), R[i]) - V.begin();
    if (T[i] == 1) {
      st2.update(x, y, X[i]);
    } else {
      cout << st2.getval(x, y) << endl;
    }
  }
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  solve();
  return 0;
}

```