#include <bits/stdc++.h>
using namespace std;
struct node {
  int low;
  int high;
  int val;
  int toPush;
  node() : toPush(0) {}
};
vector<node> seg;
const int inf = 2e9;
void init(int n, vector<int> arr) {
  seg.clear();
  seg = vector<node>(2 * n);
  int len = arr.size();
  for (int i = n; i < 2 * n; ++i) {
    if (i - n < len)
      seg[i].val = arr[i - n];
    else
      seg[i].val = inf;
    seg[i].low = i - n;
    seg[i].high = i - n + 1;
  }
  for (int i = n - 1; i > 0; --i) {
    seg[i].val = min(seg[2 * i].val, seg[(2 * i) + 1].val);
    seg[i].high = max(seg[2 * i].high, seg[(2 * i) + 1].high);
    seg[i].low = min(seg[2 * i].low, seg[(2 * i) + 1].low);
  }
}
void pushNode(int ind) {
  if (seg[ind].toPush == 0) return;
  seg[ind].toPush = 0;
  seg[2 * ind].val = seg[2 * ind + 1].val = seg[ind].val;
  seg[2 * ind].toPush = seg[2 * ind + 1].toPush = 1;
}
int getMin(int low, int high) {
  int ans = inf;
  queue<int> index;
  index.push(1);
  while (!index.empty()) {
    int tp = index.front();
    index.pop();
    node nd = seg[tp];
    if (nd.low >= low && nd.high <= high) {
      ans = min(ans, nd.val);
      continue;
    }
    if (nd.low >= high || nd.high <= low) {
      continue;
    }
    pushNode(tp);
    index.push(2 * tp);
    index.push(2 * tp + 1);
  }
  return ans;
}
void pushChange(int low, int high, int val) {
  queue<int> index;
  stack<int> toUpdate;
  index.push(1);
  while (!index.empty()) {
    int tp = index.front();
    index.pop();
    if (seg[tp].low >= low && seg[tp].high <= high) {
      seg[tp].val = val;
      seg[tp].toPush = 1;
      continue;
    }
    if (seg[tp].low >= high || seg[tp].high <= low) {
      continue;
    }
    pushNode(tp);
    toUpdate.push(tp);
    index.push(2 * tp);
    index.push(2 * tp + 1);
  }
  while (!toUpdate.empty()) {
    int tp = toUpdate.top();
    toUpdate.pop();
    seg[tp].val = min(seg[2 * tp].val, seg[2 * tp + 1].val);
  }
}
int getCycMin(int low, int high) {
  int n = seg.size() / 2;
  if (high - low >= n) return getMin(0, n);
  low %= n;
  high %= n;
  if (low < high) return getMin(low, high);
  return min(getMin(low, n), getMin(0, high));
}
int main() {
  int Test = 1;
  for (int test = 1; test <= Test; ++test) {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
      cin >> arr[i];
    }
    init(n, arr);
    int q;
    cin >> q;
    int qr[q][4];
    vector<int> indic;
    for (int i = 0; i < q; ++i) {
      cin >> qr[i][0] >> qr[i][1] >> qr[i][2];
      qr[i][1]--;
      indic.push_back(qr[i][1]);
      indic.push_back(qr[i][2]);
      if (qr[i][0] == 1) {
        cin >> qr[i][3];
      }
    }
    sort(indic.begin(), indic.end());
    auto iter = unique(indic.begin(), indic.end());
    int newSize = iter - indic.begin();
    indic.resize(newSize);
    map<int, int> nq;
    arr.clear();
    for (unsigned int i = 0; i < indic.size(); ++i) {
      nq[indic[i]] = i;
    }
    for (unsigned int i = 0; i < indic.size() - 1; ++i) {
      arr.push_back(getCycMin(indic[i], indic[i + 1]));
    }
    for (int i = 0; i < q; ++i) {
      qr[i][1] = nq[qr[i][1]];
      qr[i][2] = nq[qr[i][2]];
    }
    init(arr.size(), arr);
    for (int i = 0; i < q; ++i) {
      if (qr[i][0] == 1) {
        pushChange(qr[i][1], qr[i][2], qr[i][3]);
        continue;
      }
      cout << getMin(qr[i][1], qr[i][2]) << endl;
    }
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
struct node {
  int low;
  int high;
  int val;
  int toPush;
  node() : toPush(0) {}
};
vector<node> seg;
const int inf = 2e9;
void init(int n, vector<int> arr) {
  seg.clear();
  seg = vector<node>(2 * n);
  int len = arr.size();
  for (int i = n; i < 2 * n; ++i) {
    if (i - n < len)
      seg[i].val = arr[i - n];
    else
      seg[i].val = inf;
    seg[i].low = i - n;
    seg[i].high = i - n + 1;
  }
  for (int i = n - 1; i > 0; --i) {
    seg[i].val = min(seg[2 * i].val, seg[(2 * i) + 1].val);
    seg[i].high = max(seg[2 * i].high, seg[(2 * i) + 1].high);
    seg[i].low = min(seg[2 * i].low, seg[(2 * i) + 1].low);
  }
}
void pushNode(int ind) {
  if (seg[ind].toPush == 0) return;
  seg[ind].toPush = 0;
  seg[2 * ind].val = seg[2 * ind + 1].val = seg[ind].val;
  seg[2 * ind].toPush = seg[2 * ind + 1].toPush = 1;
}
int getMin(int low, int high) {
  int ans = inf;
  queue<int> index;
  index.push(1);
  while (!index.empty()) {
    int tp = index.front();
    index.pop();
    node nd = seg[tp];
    if (nd.low >= low && nd.high <= high) {
      ans = min(ans, nd.val);
      continue;
    }
    if (nd.low >= high || nd.high <= low) {
      continue;
    }
    pushNode(tp);
    index.push(2 * tp);
    index.push(2 * tp + 1);
  }
  return ans;
}
void pushChange(int low, int high, int val) {
  queue<int> index;
  stack<int> toUpdate;
  index.push(1);
  while (!index.empty()) {
    int tp = index.front();
    index.pop();
    if (seg[tp].low >= low && seg[tp].high <= high) {
      seg[tp].val = val;
      seg[tp].toPush = 1;
      continue;
    }
    if (seg[tp].low >= high || seg[tp].high <= low) {
      continue;
    }
    pushNode(tp);
    toUpdate.push(tp);
    index.push(2 * tp);
    index.push(2 * tp + 1);
  }
  while (!toUpdate.empty()) {
    int tp = toUpdate.top();
    toUpdate.pop();
    seg[tp].val = min(seg[2 * tp].val, seg[2 * tp + 1].val);
  }
}
int getCycMin(int low, int high) {
  int n = seg.size() / 2;
  if (high - low >= n) return getMin(0, n);
  low %= n;
  high %= n;
  if (low < high) return getMin(low, high);
  return min(getMin(low, n), getMin(0, high));
}
int main() {
  int Test = 1;
  for (int test = 1; test <= Test; ++test) {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
      cin >> arr[i];
    }
    init(n, arr);
    int q;
    cin >> q;
    int qr[q][4];
    vector<int> indic;
    for (int i = 0; i < q; ++i) {
      cin >> qr[i][0] >> qr[i][1] >> qr[i][2];
      qr[i][1]--;
      indic.push_back(qr[i][1]);
      indic.push_back(qr[i][2]);
      if (qr[i][0] == 1) {
        cin >> qr[i][3];
      }
    }
    sort(indic.begin(), indic.end());
    auto iter = unique(indic.begin(), indic.end());
    int newSize = iter - indic.begin();
    indic.resize(newSize);
    map<int, int> nq;
    arr.clear();
    for (unsigned int i = 0; i < indic.size(); ++i) {
      nq[indic[i]] = i;
    }
    for (unsigned int i = 0; i < indic.size() - 1; ++i) {
      arr.push_back(getCycMin(indic[i], indic[i + 1]));
    }
    for (int i = 0; i < q; ++i) {
      qr[i][1] = nq[qr[i][1]];
      qr[i][2] = nq[qr[i][2]];
    }
    init(arr.size(), arr);
    for (int i = 0; i < q; ++i) {
      if (qr[i][0] == 1) {
        pushChange(qr[i][1], qr[i][2], qr[i][3]);
        continue;
      }
      cout << getMin(qr[i][1], qr[i][2]) << endl;
    }
  }
  return 0;
}

```