#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
struct Ques {
  int opt, l, r, val;
} q[MAXN];
int n, K, m;
int a[MAXN], b[MAXN << 1], Cnt = 0, pre[MAXN << 1];
int date[MAXN], cnt = 0, date_num = 0;
int read() {
  int s = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
  while (isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0', ch = getchar();
  return f ? -s : s;
}
struct Big_Seg {
  struct Tree {
    int min, lazy;
  } tree[MAXN << 3];
  void Push_up(int i) {
    tree[i].min = min(tree[i << 1].min, tree[i << 1 | 1].min);
  }
  void Push_down(int i) {
    if (tree[i].lazy) {
      tree[i << 1].lazy = tree[i << 1 | 1].lazy = tree[i].lazy;
      tree[i << 1].min = tree[i << 1 | 1].min = tree[i].lazy;
      tree[i].lazy = 0;
    }
  }
  void Build(int i, int l, int r) {
    if (l == r) {
      tree[i].min = b[l];
      return;
    }
    int mid = (l + r) >> 1;
    Build(i << 1, l, mid), Build(i << 1 | 1, mid + 1, r);
    Push_up(i);
  }
  void Build0(int i, int l, int r) {
    if (l == r) {
      tree[i].min = a[l];
      return;
    }
    int mid = (l + r) >> 1;
    Build0(i << 1, l, mid), Build0(i << 1 | 1, mid + 1, r);
    Push_up(i);
  }
  void Change(int i, int l, int r, int L, int R, int k) {
    if (L <= l && r <= R) {
      tree[i].min = tree[i].lazy = k;
      return;
    }
    Push_down(i);
    int mid = (l + r) >> 1;
    if (mid >= L) Change(i << 1, l, mid, L, R, k);
    if (mid < R) Change(i << 1 | 1, mid + 1, r, L, R, k);
    Push_up(i);
  }
  int Get_min(int i, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tree[i].min;
    Push_down(i);
    int mid = (l + r) >> 1, ans = INF;
    if (mid >= L) ans = min(ans, Get_min(i << 1, l, mid, L, R));
    if (mid < R) ans = min(ans, Get_min(i << 1 | 1, mid + 1, r, L, R));
    return ans;
  }
} Seg[2];
int main() {
  n = read(), K = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  Seg[0].Build0(1, 1, n);
  m = read();
  for (int i = 1; i <= m; ++i) {
    q[i].opt = read(), q[i].l = read(), q[i].r = read();
    date[++cnt] = q[i].l, date[++cnt] = q[i].r;
    if (q[i].opt == 1) q[i].val = read();
  }
  sort(date + 1, date + cnt + 1);
  date[0] = -INF;
  for (int i = 1; i <= cnt; ++i)
    if (date[i] != date[i - 1]) date[++date_num] = date[i];
  for (int i = 1; i < date_num; ++i) {
    if (date[i] % n == 0)
      b[++Cnt] = a[n];
    else
      b[++Cnt] = a[date[i] % n];
    pre[i] = Cnt;
    if (date[i + 1] > date[i] + 1) {
      if (date[i + 1] - 1 - date[i] - 1 >= n) {
        b[++Cnt] = Seg[0].tree[1].min;
        continue;
      }
      int l = (date[i] + 1) % n, r = (date[i + 1] - 1) % n;
      if (l == 0) l = n;
      if (r == 0) r = n;
      if (l <= r)
        b[++Cnt] = Seg[0].Get_min(1, 1, n, l, r);
      else {
        b[++Cnt] =
            min(Seg[0].Get_min(1, 1, n, 1, r), Seg[0].Get_min(1, 1, n, l, n));
      }
    }
  }
  if (date[date_num] % n == 0)
    b[++Cnt] = a[n];
  else
    b[++Cnt] = a[date[date_num] % n];
  pre[date_num] = Cnt;
  for (int i = 1; i <= m; ++i) {
    q[i].l = lower_bound(date + 1, date + date_num + 1, q[i].l) - date;
    q[i].r = lower_bound(date + 1, date + date_num + 1, q[i].r) - date;
    q[i].l = pre[q[i].l], q[i].r = pre[q[i].r];
  }
  Seg[1].Build(1, 1, Cnt);
  for (int i = 1; i <= m; ++i) {
    if (q[i].opt == 1)
      Seg[1].Change(1, 1, Cnt, q[i].l, q[i].r, q[i].val);
    else
      printf("%d\n", Seg[1].Get_min(1, 1, Cnt, q[i].l, q[i].r));
  }
  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;
const int MAXN = 2e5 + 5;
const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
struct Ques {
  int opt, l, r, val;
} q[MAXN];
int n, K, m;
int a[MAXN], b[MAXN << 1], Cnt = 0, pre[MAXN << 1];
int date[MAXN], cnt = 0, date_num = 0;
int read() {
  int s = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
  while (isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0', ch = getchar();
  return f ? -s : s;
}
struct Big_Seg {
  struct Tree {
    int min, lazy;
  } tree[MAXN << 3];
  void Push_up(int i) {
    tree[i].min = min(tree[i << 1].min, tree[i << 1 | 1].min);
  }
  void Push_down(int i) {
    if (tree[i].lazy) {
      tree[i << 1].lazy = tree[i << 1 | 1].lazy = tree[i].lazy;
      tree[i << 1].min = tree[i << 1 | 1].min = tree[i].lazy;
      tree[i].lazy = 0;
    }
  }
  void Build(int i, int l, int r) {
    if (l == r) {
      tree[i].min = b[l];
      return;
    }
    int mid = (l + r) >> 1;
    Build(i << 1, l, mid), Build(i << 1 | 1, mid + 1, r);
    Push_up(i);
  }
  void Build0(int i, int l, int r) {
    if (l == r) {
      tree[i].min = a[l];
      return;
    }
    int mid = (l + r) >> 1;
    Build0(i << 1, l, mid), Build0(i << 1 | 1, mid + 1, r);
    Push_up(i);
  }
  void Change(int i, int l, int r, int L, int R, int k) {
    if (L <= l && r <= R) {
      tree[i].min = tree[i].lazy = k;
      return;
    }
    Push_down(i);
    int mid = (l + r) >> 1;
    if (mid >= L) Change(i << 1, l, mid, L, R, k);
    if (mid < R) Change(i << 1 | 1, mid + 1, r, L, R, k);
    Push_up(i);
  }
  int Get_min(int i, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tree[i].min;
    Push_down(i);
    int mid = (l + r) >> 1, ans = INF;
    if (mid >= L) ans = min(ans, Get_min(i << 1, l, mid, L, R));
    if (mid < R) ans = min(ans, Get_min(i << 1 | 1, mid + 1, r, L, R));
    return ans;
  }
} Seg[2];
int main() {
  n = read(), K = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  Seg[0].Build0(1, 1, n);
  m = read();
  for (int i = 1; i <= m; ++i) {
    q[i].opt = read(), q[i].l = read(), q[i].r = read();
    date[++cnt] = q[i].l, date[++cnt] = q[i].r;
    if (q[i].opt == 1) q[i].val = read();
  }
  sort(date + 1, date + cnt + 1);
  date[0] = -INF;
  for (int i = 1; i <= cnt; ++i)
    if (date[i] != date[i - 1]) date[++date_num] = date[i];
  for (int i = 1; i < date_num; ++i) {
    if (date[i] % n == 0)
      b[++Cnt] = a[n];
    else
      b[++Cnt] = a[date[i] % n];
    pre[i] = Cnt;
    if (date[i + 1] > date[i] + 1) {
      if (date[i + 1] - 1 - date[i] - 1 >= n) {
        b[++Cnt] = Seg[0].tree[1].min;
        continue;
      }
      int l = (date[i] + 1) % n, r = (date[i + 1] - 1) % n;
      if (l == 0) l = n;
      if (r == 0) r = n;
      if (l <= r)
        b[++Cnt] = Seg[0].Get_min(1, 1, n, l, r);
      else {
        b[++Cnt] =
            min(Seg[0].Get_min(1, 1, n, 1, r), Seg[0].Get_min(1, 1, n, l, n));
      }
    }
  }
  if (date[date_num] % n == 0)
    b[++Cnt] = a[n];
  else
    b[++Cnt] = a[date[date_num] % n];
  pre[date_num] = Cnt;
  for (int i = 1; i <= m; ++i) {
    q[i].l = lower_bound(date + 1, date + date_num + 1, q[i].l) - date;
    q[i].r = lower_bound(date + 1, date + date_num + 1, q[i].r) - date;
    q[i].l = pre[q[i].l], q[i].r = pre[q[i].r];
  }
  Seg[1].Build(1, 1, Cnt);
  for (int i = 1; i <= m; ++i) {
    if (q[i].opt == 1)
      Seg[1].Change(1, 1, Cnt, q[i].l, q[i].r, q[i].val);
    else
      printf("%d\n", Seg[1].Get_min(1, 1, Cnt, q[i].l, q[i].r));
  }
  return 0;
}

```