#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 100500;
struct node {
  int l, r;
  node *L, *R;
  int mn;
  int add;
  node(int l, int r) : l(l), r(r), mn(inf), add(0) {
    if (l + 1 == r) {
      L = R = NULL;
    } else {
      int m = (l + r) / 2;
      L = new node(l, m);
      R = new node(m, r);
    }
  }
  void apply(int x) { add = mn = x; }
  void push() {
    if (add) {
      L->apply(add);
      R->apply(add);
      add = 0;
    }
  }
  void update() { mn = min(L->mn, R->mn); }
  void put(int lq, int rq, int val) {
    if (lq <= l && r <= rq) {
      apply(val);
    } else if (rq <= l || lq >= r) {
    } else {
      push();
      L->put(lq, rq, val);
      R->put(lq, rq, val);
      update();
    }
  }
  int get(int lq, int rq) {
    if (lq <= l && r <= rq) {
      return mn;
    } else if (rq <= l || lq >= r) {
      return inf;
    } else {
      push();
      return min(L->get(lq, rq), R->get(lq, rq));
    }
  }
};
const int maxn = 500500;
int n, k;
int b[maxn];
int q;
int t[maxn], l[maxn], r[maxn], x[maxn];
vector<int> shr;
node *t1, *t2;
void scan() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < (int)(n); ++i) scanf("%d", &b[i]);
  scanf("%d", &q);
  for (int i = 0; i < (int)(q); ++i) {
    scanf("%d", &t[i]);
    if (t[i] == 1) {
      scanf("%d%d%d", &l[i], &r[i], &x[i]);
    } else {
      scanf("%d%d", &l[i], &r[i]);
    }
    --l[i];
  }
}
void solve() {
  for (int i = 0; i < (int)(k + 1); ++i) shr.push_back(i * n);
  for (int i = 0; i < (int)(q); ++i) shr.push_back(l[i]), shr.push_back(r[i]);
  sort((shr).begin(), (shr).end());
  shr.erase(unique((shr).begin(), (shr).end()), shr.end());
  int k = shr.size();
  t1 = new node(0, n);
  for (int i = 0; i < (int)(n); ++i) t1->put(i, i + 1, b[i]);
  t2 = new node(0, k);
  for (int i = 0; i < (int)(k - 1); ++i) {
    int l = shr[i], r = shr[i + 1];
    int lq = l % n, rq = r % n;
    if (rq == 0) rq = n;
    t2->put(i, i + 1, t1->get(lq, rq));
  }
  for (int i = 0; i < (int)(q); ++i) {
    int lq = lower_bound((shr).begin(), (shr).end(), l[i]) - shr.begin();
    int rq = lower_bound((shr).begin(), (shr).end(), r[i]) - shr.begin();
    if (t[i] == 1) {
      t2->put(lq, rq, x[i]);
    } else {
      printf("%d\n", t2->get(lq, rq));
    }
  }
}
int main() {
  scan();
  solve();
  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;
const int inf = 1e9 + 100500;
struct node {
  int l, r;
  node *L, *R;
  int mn;
  int add;
  node(int l, int r) : l(l), r(r), mn(inf), add(0) {
    if (l + 1 == r) {
      L = R = NULL;
    } else {
      int m = (l + r) / 2;
      L = new node(l, m);
      R = new node(m, r);
    }
  }
  void apply(int x) { add = mn = x; }
  void push() {
    if (add) {
      L->apply(add);
      R->apply(add);
      add = 0;
    }
  }
  void update() { mn = min(L->mn, R->mn); }
  void put(int lq, int rq, int val) {
    if (lq <= l && r <= rq) {
      apply(val);
    } else if (rq <= l || lq >= r) {
    } else {
      push();
      L->put(lq, rq, val);
      R->put(lq, rq, val);
      update();
    }
  }
  int get(int lq, int rq) {
    if (lq <= l && r <= rq) {
      return mn;
    } else if (rq <= l || lq >= r) {
      return inf;
    } else {
      push();
      return min(L->get(lq, rq), R->get(lq, rq));
    }
  }
};
const int maxn = 500500;
int n, k;
int b[maxn];
int q;
int t[maxn], l[maxn], r[maxn], x[maxn];
vector<int> shr;
node *t1, *t2;
void scan() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < (int)(n); ++i) scanf("%d", &b[i]);
  scanf("%d", &q);
  for (int i = 0; i < (int)(q); ++i) {
    scanf("%d", &t[i]);
    if (t[i] == 1) {
      scanf("%d%d%d", &l[i], &r[i], &x[i]);
    } else {
      scanf("%d%d", &l[i], &r[i]);
    }
    --l[i];
  }
}
void solve() {
  for (int i = 0; i < (int)(k + 1); ++i) shr.push_back(i * n);
  for (int i = 0; i < (int)(q); ++i) shr.push_back(l[i]), shr.push_back(r[i]);
  sort((shr).begin(), (shr).end());
  shr.erase(unique((shr).begin(), (shr).end()), shr.end());
  int k = shr.size();
  t1 = new node(0, n);
  for (int i = 0; i < (int)(n); ++i) t1->put(i, i + 1, b[i]);
  t2 = new node(0, k);
  for (int i = 0; i < (int)(k - 1); ++i) {
    int l = shr[i], r = shr[i + 1];
    int lq = l % n, rq = r % n;
    if (rq == 0) rq = n;
    t2->put(i, i + 1, t1->get(lq, rq));
  }
  for (int i = 0; i < (int)(q); ++i) {
    int lq = lower_bound((shr).begin(), (shr).end(), l[i]) - shr.begin();
    int rq = lower_bound((shr).begin(), (shr).end(), r[i]) - shr.begin();
    if (t[i] == 1) {
      t2->put(lq, rq, x[i]);
    } else {
      printf("%d\n", t2->get(lq, rq));
    }
  }
}
int main() {
  scan();
  solve();
  return 0;
}

```