#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int oo = 0x3f3f3f3f;
const int max0 = 18;
const int maxn = 200100;
struct node;
node *newnode();
struct node {
  node *c[2];
  int Min, label;
  node() : Min(0), label(-1) { memset(c, 0, sizeof c); }
  void update() {
    Min = oo;
    for (int i = (0), i_end_ = (2); i < i_end_; ++i)
      if (c[i]) chkmin(Min, c[i]->Min);
  }
  void flag_label(int _label) {
    label = _label;
    Min = _label;
  }
  void push_down() {
    if (~label) {
      for (int i = (0), i_end_ = (2); i < i_end_; ++i)
        if (c[i]) c[i]->flag_label(label);
      label = -1;
    }
  }
};
const int _max0 = 100000;
node *nd_pool;
int nd_res = 0;
inline node *newnode() {
  if (!nd_res) nd_pool = new node[_max0], nd_res = _max0;
  return nd_pool + (--nd_res);
}
int seg_x, seg_y, seg_z, seg_ret;
inline int get_Min(int, int);
void add(node *&rt, int l, int r) {
  if (!rt) rt = newnode(), rt->Min = get_Min(l, r);
  if (seg_x <= l && r <= seg_y) {
    rt->flag_label(seg_z);
    return;
  }
  int mid = (l + r) >> 1;
  if (!rt->c[0]) rt->c[0] = newnode(), rt->c[0]->Min = get_Min(l, mid);
  if (!rt->c[1]) rt->c[1] = newnode(), rt->c[1]->Min = get_Min(mid, r);
  rt->push_down();
  if (seg_x < mid) add(rt->c[0], l, mid);
  if (seg_y > mid) add(rt->c[1], mid, r);
  rt->update();
}
void query(node *&rt, int l, int r) {
  if (!rt) rt = newnode(), rt->Min = get_Min(l, r);
  if (seg_x <= l && r <= seg_y) {
    chkmin(seg_ret, rt->Min);
    return;
  }
  int mid = (l + r) >> 1;
  if (!rt->c[0]) rt->c[0] = newnode(), rt->c[0]->Min = get_Min(l, mid);
  if (!rt->c[1]) rt->c[1] = newnode(), rt->c[1]->Min = get_Min(mid, r);
  rt->push_down();
  if (seg_x < mid) query(rt->c[0], l, mid);
  if (seg_y > mid) query(rt->c[1], mid, r);
}
int n, K;
int a[maxn + 5];
int Min[max0][maxn + 5];
int Log[maxn + 5];
inline void get_ST() {
  for (int i = (0), i_end_ = (n << 1); i < i_end_; ++i) Min[0][i] = a[i];
  for (int i = (1), i_end_ = (max0); i < i_end_; ++i)
    for (int j = (0), j_end_ = (n << 1); j < j_end_; ++j)
      if (j + (1 << (i - 1)) < (n << 1))
        Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (1 << (i - 1))]);
      else
        Min[i][j] = Min[i - 1][j];
}
inline int rmq(int l, int r) {
  int tmp = Log[r - l];
  return min(Min[tmp][l], Min[tmp][r - (1 << tmp)]);
}
inline int get_Min(int l, int r) {
  int to_shift = (l / n) * n;
  l -= to_shift;
  r -= to_shift;
  chkmin(r, n << 1);
  return rmq(l, r);
}
node *rt;
int qn;
int main() {
  for (int i = 1; i <= maxn; ++i) {
    int u = i;
    Log[i] = -1;
    while (u) ++Log[i], u >>= 1;
  }
  scanf("%d%d", &n, &K);
  for (int i = (0), i_end_ = (n); i < i_end_; ++i)
    scanf("%d", a + i), a[n + i] = a[i];
  get_ST();
  rt = newnode();
  rt->Min = get_Min(0, n * K);
  scanf("%d", &qn);
  for (int i = (0), i_end_ = (qn); i < i_end_; ++i) {
    int ty, l, r;
    scanf("%d%d%d", &ty, &l, &r), --l;
    if (ty == 1) {
      int first;
      scanf("%d", &first);
      seg_x = l, seg_y = r, seg_z = first;
      add(rt, 0, n * K);
    } else if (ty == 2) {
      seg_x = l, seg_y = r, seg_ret = oo;
      query(rt, 0, n * K);
      printf("%d\n", seg_ret);
    }
  }
  return 0;
}

### Prompt

Generate 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;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int oo = 0x3f3f3f3f;
const int max0 = 18;
const int maxn = 200100;
struct node;
node *newnode();
struct node {
  node *c[2];
  int Min, label;
  node() : Min(0), label(-1) { memset(c, 0, sizeof c); }
  void update() {
    Min = oo;
    for (int i = (0), i_end_ = (2); i < i_end_; ++i)
      if (c[i]) chkmin(Min, c[i]->Min);
  }
  void flag_label(int _label) {
    label = _label;
    Min = _label;
  }
  void push_down() {
    if (~label) {
      for (int i = (0), i_end_ = (2); i < i_end_; ++i)
        if (c[i]) c[i]->flag_label(label);
      label = -1;
    }
  }
};
const int _max0 = 100000;
node *nd_pool;
int nd_res = 0;
inline node *newnode() {
  if (!nd_res) nd_pool = new node[_max0], nd_res = _max0;
  return nd_pool + (--nd_res);
}
int seg_x, seg_y, seg_z, seg_ret;
inline int get_Min(int, int);
void add(node *&rt, int l, int r) {
  if (!rt) rt = newnode(), rt->Min = get_Min(l, r);
  if (seg_x <= l && r <= seg_y) {
    rt->flag_label(seg_z);
    return;
  }
  int mid = (l + r) >> 1;
  if (!rt->c[0]) rt->c[0] = newnode(), rt->c[0]->Min = get_Min(l, mid);
  if (!rt->c[1]) rt->c[1] = newnode(), rt->c[1]->Min = get_Min(mid, r);
  rt->push_down();
  if (seg_x < mid) add(rt->c[0], l, mid);
  if (seg_y > mid) add(rt->c[1], mid, r);
  rt->update();
}
void query(node *&rt, int l, int r) {
  if (!rt) rt = newnode(), rt->Min = get_Min(l, r);
  if (seg_x <= l && r <= seg_y) {
    chkmin(seg_ret, rt->Min);
    return;
  }
  int mid = (l + r) >> 1;
  if (!rt->c[0]) rt->c[0] = newnode(), rt->c[0]->Min = get_Min(l, mid);
  if (!rt->c[1]) rt->c[1] = newnode(), rt->c[1]->Min = get_Min(mid, r);
  rt->push_down();
  if (seg_x < mid) query(rt->c[0], l, mid);
  if (seg_y > mid) query(rt->c[1], mid, r);
}
int n, K;
int a[maxn + 5];
int Min[max0][maxn + 5];
int Log[maxn + 5];
inline void get_ST() {
  for (int i = (0), i_end_ = (n << 1); i < i_end_; ++i) Min[0][i] = a[i];
  for (int i = (1), i_end_ = (max0); i < i_end_; ++i)
    for (int j = (0), j_end_ = (n << 1); j < j_end_; ++j)
      if (j + (1 << (i - 1)) < (n << 1))
        Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (1 << (i - 1))]);
      else
        Min[i][j] = Min[i - 1][j];
}
inline int rmq(int l, int r) {
  int tmp = Log[r - l];
  return min(Min[tmp][l], Min[tmp][r - (1 << tmp)]);
}
inline int get_Min(int l, int r) {
  int to_shift = (l / n) * n;
  l -= to_shift;
  r -= to_shift;
  chkmin(r, n << 1);
  return rmq(l, r);
}
node *rt;
int qn;
int main() {
  for (int i = 1; i <= maxn; ++i) {
    int u = i;
    Log[i] = -1;
    while (u) ++Log[i], u >>= 1;
  }
  scanf("%d%d", &n, &K);
  for (int i = (0), i_end_ = (n); i < i_end_; ++i)
    scanf("%d", a + i), a[n + i] = a[i];
  get_ST();
  rt = newnode();
  rt->Min = get_Min(0, n * K);
  scanf("%d", &qn);
  for (int i = (0), i_end_ = (qn); i < i_end_; ++i) {
    int ty, l, r;
    scanf("%d%d%d", &ty, &l, &r), --l;
    if (ty == 1) {
      int first;
      scanf("%d", &first);
      seg_x = l, seg_y = r, seg_z = first;
      add(rt, 0, n * K);
    } else if (ty == 2) {
      seg_x = l, seg_y = r, seg_ret = oo;
      query(rt, 0, n * K);
      printf("%d\n", seg_ret);
    }
  }
  return 0;
}

```