#include <bits/stdc++.h>
using namespace std;
int n, m, q, seq[100005], lst[100005][20], bit[100005], tg[10000005],
    vl[10000005], ls[10000005], rs[10000005], tt = 1, mini = 2E9;
int ask(int l, int r) {
  int t = bit[r - l + 1];
  return min(lst[l][t], lst[r - (1 << t) + 1][t]);
}
int qry(int l, int r) {
  if (r - l + 1 >= n) return mini;
  if ((l - 1) / n == (r - 1) / n)
    return ask((l - 1) % n + 1, (r - 1) % n + 1);
  else
    return min(ask((l - 1) % n + 1, n), ask(1, (r - 1) % n + 1));
}
void update(int t, int l, int r) {
  if (~tg[t])
    vl[t] = tg[t] ? tg[t] : qry(l, r);
  else
    vl[t] = min(vl[ls[t]], vl[rs[t]]);
}
void pushdown(int t, int l, int r, int d) {
  if (!ls[t]) ls[t] = ++tt;
  if (!rs[t]) rs[t] = ++tt;
  if (~tg[t]) {
    tg[ls[t]] = tg[t], update(ls[t], l, d);
    tg[rs[t]] = tg[t], update(rs[t], d + 1, r);
  }
}
void edt(int t, int l, int r, int x, int y, int v) {
  if (l == x && y == r)
    tg[t] = v;
  else {
    int d = (l + r) >> 1;
    pushdown(t, l, r, d), tg[t] = -1;
    if (y <= d)
      edt(ls[t], l, d, x, y, v);
    else if (x > d)
      edt(rs[t], d + 1, r, x, y, v);
    else
      edt(ls[t], l, d, x, d, v), edt(rs[t], d + 1, r, d + 1, y, v);
  }
  update(t, l, r);
}
int qry(int t, int l, int r, int x, int y) {
  if (l == x && y == r) return vl[t];
  int d = (l + r) >> 1;
  pushdown(t, l, r, d);
  if (y <= d)
    return qry(ls[t], l, d, x, y);
  else if (x > d)
    return qry(rs[t], d + 1, r, x, y);
  else
    return min(qry(ls[t], l, d, x, d), qry(rs[t], d + 1, r, d + 1, y));
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%d", seq + i), lst[i][0] = seq[i], mini = min(mini, seq[i]);
  for (int i = 2; i <= n; ++i) bit[i] = bit[i >> 1] + 1;
  for (int j = 1; j < 20; ++j)
    for (int i = 1; i <= n; ++i)
      if (i + (1 << j) - 1 <= n)
        lst[i][j] = min(lst[i][j - 1], lst[i + (1 << j - 1)][j - 1]);
  for (scanf("%d", &q), update(1, 1, n * m); q--;) {
    static int k, l, r, v;
    scanf("%d%d%d", &k, &l, &r);
    if (k == 1)
      scanf("%d", &v), edt(1, 1, n * m, l, r, v);
    else
      printf("%d\n", qry(1, 1, n * m, l, r));
  }
}

### Prompt

Your task is to create 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;
int n, m, q, seq[100005], lst[100005][20], bit[100005], tg[10000005],
    vl[10000005], ls[10000005], rs[10000005], tt = 1, mini = 2E9;
int ask(int l, int r) {
  int t = bit[r - l + 1];
  return min(lst[l][t], lst[r - (1 << t) + 1][t]);
}
int qry(int l, int r) {
  if (r - l + 1 >= n) return mini;
  if ((l - 1) / n == (r - 1) / n)
    return ask((l - 1) % n + 1, (r - 1) % n + 1);
  else
    return min(ask((l - 1) % n + 1, n), ask(1, (r - 1) % n + 1));
}
void update(int t, int l, int r) {
  if (~tg[t])
    vl[t] = tg[t] ? tg[t] : qry(l, r);
  else
    vl[t] = min(vl[ls[t]], vl[rs[t]]);
}
void pushdown(int t, int l, int r, int d) {
  if (!ls[t]) ls[t] = ++tt;
  if (!rs[t]) rs[t] = ++tt;
  if (~tg[t]) {
    tg[ls[t]] = tg[t], update(ls[t], l, d);
    tg[rs[t]] = tg[t], update(rs[t], d + 1, r);
  }
}
void edt(int t, int l, int r, int x, int y, int v) {
  if (l == x && y == r)
    tg[t] = v;
  else {
    int d = (l + r) >> 1;
    pushdown(t, l, r, d), tg[t] = -1;
    if (y <= d)
      edt(ls[t], l, d, x, y, v);
    else if (x > d)
      edt(rs[t], d + 1, r, x, y, v);
    else
      edt(ls[t], l, d, x, d, v), edt(rs[t], d + 1, r, d + 1, y, v);
  }
  update(t, l, r);
}
int qry(int t, int l, int r, int x, int y) {
  if (l == x && y == r) return vl[t];
  int d = (l + r) >> 1;
  pushdown(t, l, r, d);
  if (y <= d)
    return qry(ls[t], l, d, x, y);
  else if (x > d)
    return qry(rs[t], d + 1, r, x, y);
  else
    return min(qry(ls[t], l, d, x, d), qry(rs[t], d + 1, r, d + 1, y));
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%d", seq + i), lst[i][0] = seq[i], mini = min(mini, seq[i]);
  for (int i = 2; i <= n; ++i) bit[i] = bit[i >> 1] + 1;
  for (int j = 1; j < 20; ++j)
    for (int i = 1; i <= n; ++i)
      if (i + (1 << j) - 1 <= n)
        lst[i][j] = min(lst[i][j - 1], lst[i + (1 << j - 1)][j - 1]);
  for (scanf("%d", &q), update(1, 1, n * m); q--;) {
    static int k, l, r, v;
    scanf("%d%d%d", &k, &l, &r);
    if (k == 1)
      scanf("%d", &v), edt(1, 1, n * m, l, r, v);
    else
      printf("%d\n", qry(1, 1, n * m, l, r));
  }
}

```