#include <bits/stdc++.h>
using namespace std;
namespace INPUT {
const int L = 1 << 15;
char _buf[L], *S, *T, c;
char _gc() {
  if (S == T) {
    T = (S = _buf) + fread(_buf, 1, L, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
void readi(int &X) {
  for (c = _gc(); c < '0' || c > '9'; c = _gc())
    ;
  X = c ^ 48;
  for (c = _gc(); c >= '0' && c <= '9'; X = X * 10 + (c ^ 48), c = _gc())
    ;
}
}  // namespace INPUT
const int Maxx = 1E9;
const int Maxn = 2E5 + 5;
int N, K, Q;
int a[Maxn];
int Log2[Maxn];
int st[Maxn][20];
void RMQ() {
  for (int i = 2; i < Maxn; ++i) Log2[i] = Log2[i >> 1] + 1;
  for (int i = 1; i <= (N << 1); ++i) {
    st[i][0] = a[i];
    for (int k = 1; (1 << k) <= i; ++k)
      st[i][k] = min(st[i][k - 1], st[i - (1 << (k - 1))][k - 1]);
  }
}
int Get_Mn(int L, int R) {
  if (R - L + 1 < N) {
    L = (L - 1) % N + 1, R = (R - 1) % N + 1;
    if (R < L) R += N;
  } else
    L = 1, R = N;
  int k = Log2[R - L + 1];
  return min(st[R][k], st[L + (1 << k) - 1][k]);
}
int root;
namespace SEG {
int tot;
int ch[Maxn << 5][2];
int mn[Maxn << 5], tap[Maxn << 5];
void Tap_Down(int i) {
  if (tap[i] != 0) {
    if (!ch[i][0]) ch[i][0] = ++tot;
    if (!ch[i][1]) ch[i][1] = ++tot;
    mn[ch[i][0]] = mn[ch[i][1]] = tap[ch[i][0]] = tap[ch[i][1]] = tap[i];
    tap[i] = 0;
  }
}
void Updata(int i, int L, int R) {
  int mid = (L + R) >> 1;
  if (ch[i][0])
    mn[i] = mn[ch[i][0]];
  else
    mn[i] = Get_Mn(L, mid);
  if (ch[i][1])
    mn[i] = min(mn[i], mn[ch[i][1]]);
  else
    mn[i] = min(mn[i], Get_Mn(mid + 1, R));
}
void Insert(int &i, int L, int R, int l, int r, int x) {
  if (!i) i = ++tot;
  if (L >= l && R <= r) {
    tap[i] = mn[i] = x;
    return;
  }
  Tap_Down(i);
  int mid = (L + R) >> 1;
  if (r <= mid)
    Insert(ch[i][0], L, mid, l, r, x);
  else if (l > mid)
    Insert(ch[i][1], mid + 1, R, l, r, x);
  else
    Insert(ch[i][0], L, mid, l, mid, x),
        Insert(ch[i][1], mid + 1, R, mid + 1, r, x);
  Updata(i, L, R);
}
int Query(int i, int L, int R, int l, int r) {
  if (!i) return Get_Mn(l, r);
  if (L >= l && R <= r) return mn[i];
  Tap_Down(i);
  int mid = (L + R) >> 1;
  if (r <= mid)
    return Query(ch[i][0], L, mid, l, r);
  else if (l > mid)
    return Query(ch[i][1], mid + 1, R, l, r);
  else
    return min(Query(ch[i][0], L, mid, l, mid),
               Query(ch[i][1], mid + 1, R, mid + 1, r));
}
}  // namespace SEG
int main() {
  INPUT::readi(N), INPUT::readi(K);
  for (int i = 1; i <= N; ++i) INPUT::readi(a[i]), a[i + N] = a[i];
  RMQ();
  INPUT::readi(Q);
  int opt, l, r, x;
  while (Q--) {
    INPUT::readi(opt), INPUT::readi(l), INPUT::readi(r);
    if (opt == 1)
      INPUT::readi(x), SEG::Insert(root, 1, N * K, l, r, x);
    else
      printf("%d\n", SEG::Query(root, 1, N * K, l, r));
  }
  return 0;
}

### Prompt

Please create a solution in Cpp 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;
namespace INPUT {
const int L = 1 << 15;
char _buf[L], *S, *T, c;
char _gc() {
  if (S == T) {
    T = (S = _buf) + fread(_buf, 1, L, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
void readi(int &X) {
  for (c = _gc(); c < '0' || c > '9'; c = _gc())
    ;
  X = c ^ 48;
  for (c = _gc(); c >= '0' && c <= '9'; X = X * 10 + (c ^ 48), c = _gc())
    ;
}
}  // namespace INPUT
const int Maxx = 1E9;
const int Maxn = 2E5 + 5;
int N, K, Q;
int a[Maxn];
int Log2[Maxn];
int st[Maxn][20];
void RMQ() {
  for (int i = 2; i < Maxn; ++i) Log2[i] = Log2[i >> 1] + 1;
  for (int i = 1; i <= (N << 1); ++i) {
    st[i][0] = a[i];
    for (int k = 1; (1 << k) <= i; ++k)
      st[i][k] = min(st[i][k - 1], st[i - (1 << (k - 1))][k - 1]);
  }
}
int Get_Mn(int L, int R) {
  if (R - L + 1 < N) {
    L = (L - 1) % N + 1, R = (R - 1) % N + 1;
    if (R < L) R += N;
  } else
    L = 1, R = N;
  int k = Log2[R - L + 1];
  return min(st[R][k], st[L + (1 << k) - 1][k]);
}
int root;
namespace SEG {
int tot;
int ch[Maxn << 5][2];
int mn[Maxn << 5], tap[Maxn << 5];
void Tap_Down(int i) {
  if (tap[i] != 0) {
    if (!ch[i][0]) ch[i][0] = ++tot;
    if (!ch[i][1]) ch[i][1] = ++tot;
    mn[ch[i][0]] = mn[ch[i][1]] = tap[ch[i][0]] = tap[ch[i][1]] = tap[i];
    tap[i] = 0;
  }
}
void Updata(int i, int L, int R) {
  int mid = (L + R) >> 1;
  if (ch[i][0])
    mn[i] = mn[ch[i][0]];
  else
    mn[i] = Get_Mn(L, mid);
  if (ch[i][1])
    mn[i] = min(mn[i], mn[ch[i][1]]);
  else
    mn[i] = min(mn[i], Get_Mn(mid + 1, R));
}
void Insert(int &i, int L, int R, int l, int r, int x) {
  if (!i) i = ++tot;
  if (L >= l && R <= r) {
    tap[i] = mn[i] = x;
    return;
  }
  Tap_Down(i);
  int mid = (L + R) >> 1;
  if (r <= mid)
    Insert(ch[i][0], L, mid, l, r, x);
  else if (l > mid)
    Insert(ch[i][1], mid + 1, R, l, r, x);
  else
    Insert(ch[i][0], L, mid, l, mid, x),
        Insert(ch[i][1], mid + 1, R, mid + 1, r, x);
  Updata(i, L, R);
}
int Query(int i, int L, int R, int l, int r) {
  if (!i) return Get_Mn(l, r);
  if (L >= l && R <= r) return mn[i];
  Tap_Down(i);
  int mid = (L + R) >> 1;
  if (r <= mid)
    return Query(ch[i][0], L, mid, l, r);
  else if (l > mid)
    return Query(ch[i][1], mid + 1, R, l, r);
  else
    return min(Query(ch[i][0], L, mid, l, mid),
               Query(ch[i][1], mid + 1, R, mid + 1, r));
}
}  // namespace SEG
int main() {
  INPUT::readi(N), INPUT::readi(K);
  for (int i = 1; i <= N; ++i) INPUT::readi(a[i]), a[i + N] = a[i];
  RMQ();
  INPUT::readi(Q);
  int opt, l, r, x;
  while (Q--) {
    INPUT::readi(opt), INPUT::readi(l), INPUT::readi(r);
    if (opt == 1)
      INPUT::readi(x), SEG::Insert(root, 1, N * K, l, r, x);
    else
      printf("%d\n", SEG::Query(root, 1, N * K, l, r));
  }
  return 0;
}

```