#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int SZ = 100000;
int N, K, Q, segmin[4 * SZ], seg[8 * SZ], lazy[8 * SZ];
map<int, int> key;
vector<int> tot;
vector<pair<pair<int, int>, pair<int, int>>> q;
int qmin(int l, int r) {
  if (r - l >= N)
    l = 0, r = N;
  else {
    l %= N, r %= N;
    if (r < l) r += N;
  }
  int res = MOD;
  for (l += 2 * SZ, r += 2 * SZ; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = min(res, segmin[l++]);
    if (r & 1) res = min(res, segmin[--r]);
  }
  return res;
}
void push(int ind, int low, int high) {
  if (lazy[ind] != MOD) {
    seg[ind] = lazy[ind];
    if (low != high) lazy[2 * ind] = lazy[ind], lazy[2 * ind + 1] = lazy[ind];
    lazy[ind] = MOD;
  }
}
int qmin1(int ind, int low, int high, int L, int R) {
  push(ind, low, high);
  if (low > R || high < L) return MOD;
  if (L <= low && high <= R) return seg[ind];
  return min(qmin1(2 * ind, low, (low + high) / 2, L, R),
             qmin1(2 * ind + 1, (low + high) / 2 + 1, high, L, R));
}
void modifymin1(int ind, int low, int high, int L, int R, int val) {
  push(ind, low, high);
  if (high < L || R < low) return;
  if (L <= low && high <= R) {
    seg[ind] = val;
    if (low != high) lazy[2 * ind] = val, lazy[2 * ind + 1] = val;
    return;
  }
  modifymin1(2 * ind, low, (low + high) / 2, L, R, val);
  modifymin1(2 * ind + 1, (low + high) / 2 + 1, high, L, R, val);
  seg[ind] = min(seg[2 * ind], seg[2 * ind + 1]);
}
int main() {
  for (int i = 0; i < 4 * SZ; i++) lazy[i] = MOD;
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    segmin[i + 2 * SZ] = segmin[i + 2 * SZ + N] = x;
  }
  for (int i = 2 * SZ - 1; i > 0; --i)
    segmin[i] = min(segmin[2 * i], segmin[2 * i + 1]);
  int cur = 0;
  tot.push_back(N * K);
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int t, l, r, x;
    cin >> t >> l >> r;
    l--, r--;
    if (t == 1) cin >> x;
    q.push_back({{t, x}, {l, r}});
    tot.push_back(l);
    tot.push_back(r + 1);
  }
  sort(tot.begin(), tot.end());
  tot.erase(unique(tot.begin(), tot.end()), tot.end());
  for (int i = 0; i < tot.size(); i++) key[tot[i]] = i;
  for (int i = 0; i < tot.size() - 1; i++)
    modifymin1(1, 0, 2 * SZ - 1, i, i + 1, qmin(tot[i], tot[i + 1]));
  for (auto a : q) {
    if (a.first.first == 1)
      modifymin1(1, 0, 2 * SZ - 1, key[a.second.first],
                 key[a.second.second + 1] - 1, a.first.second);
    else
      cout << qmin1(1, 0, 2 * SZ - 1, key[a.second.first],
                    key[a.second.second + 1] - 1)
           << "\n";
  }
}

### Prompt

Please formulate a Cpp solution 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;
const int MOD = 1000000007;
const int SZ = 100000;
int N, K, Q, segmin[4 * SZ], seg[8 * SZ], lazy[8 * SZ];
map<int, int> key;
vector<int> tot;
vector<pair<pair<int, int>, pair<int, int>>> q;
int qmin(int l, int r) {
  if (r - l >= N)
    l = 0, r = N;
  else {
    l %= N, r %= N;
    if (r < l) r += N;
  }
  int res = MOD;
  for (l += 2 * SZ, r += 2 * SZ; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = min(res, segmin[l++]);
    if (r & 1) res = min(res, segmin[--r]);
  }
  return res;
}
void push(int ind, int low, int high) {
  if (lazy[ind] != MOD) {
    seg[ind] = lazy[ind];
    if (low != high) lazy[2 * ind] = lazy[ind], lazy[2 * ind + 1] = lazy[ind];
    lazy[ind] = MOD;
  }
}
int qmin1(int ind, int low, int high, int L, int R) {
  push(ind, low, high);
  if (low > R || high < L) return MOD;
  if (L <= low && high <= R) return seg[ind];
  return min(qmin1(2 * ind, low, (low + high) / 2, L, R),
             qmin1(2 * ind + 1, (low + high) / 2 + 1, high, L, R));
}
void modifymin1(int ind, int low, int high, int L, int R, int val) {
  push(ind, low, high);
  if (high < L || R < low) return;
  if (L <= low && high <= R) {
    seg[ind] = val;
    if (low != high) lazy[2 * ind] = val, lazy[2 * ind + 1] = val;
    return;
  }
  modifymin1(2 * ind, low, (low + high) / 2, L, R, val);
  modifymin1(2 * ind + 1, (low + high) / 2 + 1, high, L, R, val);
  seg[ind] = min(seg[2 * ind], seg[2 * ind + 1]);
}
int main() {
  for (int i = 0; i < 4 * SZ; i++) lazy[i] = MOD;
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    segmin[i + 2 * SZ] = segmin[i + 2 * SZ + N] = x;
  }
  for (int i = 2 * SZ - 1; i > 0; --i)
    segmin[i] = min(segmin[2 * i], segmin[2 * i + 1]);
  int cur = 0;
  tot.push_back(N * K);
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int t, l, r, x;
    cin >> t >> l >> r;
    l--, r--;
    if (t == 1) cin >> x;
    q.push_back({{t, x}, {l, r}});
    tot.push_back(l);
    tot.push_back(r + 1);
  }
  sort(tot.begin(), tot.end());
  tot.erase(unique(tot.begin(), tot.end()), tot.end());
  for (int i = 0; i < tot.size(); i++) key[tot[i]] = i;
  for (int i = 0; i < tot.size() - 1; i++)
    modifymin1(1, 0, 2 * SZ - 1, i, i + 1, qmin(tot[i], tot[i + 1]));
  for (auto a : q) {
    if (a.first.first == 1)
      modifymin1(1, 0, 2 * SZ - 1, key[a.second.first],
                 key[a.second.second + 1] - 1, a.first.second);
    else
      cout << qmin1(1, 0, 2 * SZ - 1, key[a.second.first],
                    key[a.second.second + 1] - 1)
           << "\n";
  }
}

```