#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - 48;
    c = getchar();
  }
  return x * f;
}
struct cow {
  int A[500009];
  struct tree {
    int l, r;
    int val, tag;
  } t[500009 << 2];
  void update(int rt) {
    t[rt].val = min(t[(rt << 1)].val, t[(rt << 1 | 1)].val);
  }
  void pushdown(int rt) {
    if (t[rt].tag == -1) return;
    t[(rt << 1)].tag = t[(rt << 1 | 1)].tag = t[rt].tag;
    t[(rt << 1)].val = t[(rt << 1 | 1)].val = t[rt].tag;
    t[rt].tag = -1;
  }
  void build(int rt, int l, int r) {
    t[rt].l = l;
    t[rt].r = r;
    t[rt].tag = -1;
    if (l == r) {
      t[rt].val = A[l];
      return;
    }
    int mid = (t[rt].l + t[rt].r) / 2;
    build((rt << 1), l, mid);
    build((rt << 1 | 1), mid + 1, r);
    update(rt);
  }
  void change(int rt, int L, int R, int k) {
    if (L <= t[rt].l && t[rt].r <= R) {
      t[rt].tag = t[rt].val = k;
      return;
    }
    int mid = (t[rt].l + t[rt].r) / 2;
    pushdown(rt);
    if (L <= mid) change((rt << 1), L, R, k);
    if (R > mid) change((rt << 1 | 1), L, R, k);
    update(rt);
  }
  int query(int rt, int L, int R) {
    if (L <= t[rt].l && t[rt].r <= R) return t[rt].val;
    int mid = (t[rt].l + t[rt].r) / 2;
    pushdown(rt);
    int ans = 1e9;
    if (L <= mid) ans = min(ans, query((rt << 1), L, R));
    if (R > mid) ans = min(ans, query((rt << 1 | 1), L, R));
    return ans;
  }
} re, now;
int op[500009], l[500009], r[500009], v[500009];
int B[500009];
int n, k;
int getval(int l, int r) {
  if (l > r) return 1e9;
  int key = (r / n) * n;
  if (key == r) key -= n;
  if (l > key) return re.query(1, (l - 1) % n + 1, (r - 1) % n + 1);
  if (l <= key - n) return re.t[1].val;
  return min(re.query(1, 1, (r - 1) % n + 1), re.query(1, (l - 1) % n + 1, n));
}
int main() {
  n = read();
  k = read();
  for (int i = 1; i <= n; i++) re.A[i] = read();
  re.build(1, 1, n);
  int m = read();
  for (int i = 1; i <= m; i++) {
    op[i] = read();
    l[i] = read();
    r[i] = read();
    B[i] = l[i];
    B[i + m] = r[i];
    if (op[i] == 1) v[i] = read();
  }
  sort(B + 1, B + m + m + 1);
  int len = unique(B + 1, B + m + m + 1) - B - 1;
  for (int i = 1; i <= len; i++) {
    now.A[i + i - 1] = re.A[(B[i] - 1) % n + 1];
  }
  for (int i = 1; i < len; i++) {
    now.A[i + i] = getval(B[i] + 1, B[i + 1] - 1);
  }
  now.build(1, 1, len + len - 1);
  for (int i = 1; i <= m; i++) {
    int L = lower_bound(B + 1, B + len + 1, l[i]) - B;
    L = L + L - 1;
    int R = lower_bound(B + 1, B + len + 1, r[i]) - B;
    R = R + R - 1;
    if (op[i] == 1) {
      now.change(1, L, R, v[i]);
    }
    if (op[i] == 2) {
      printf("%d\n", now.query(1, L, 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;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - 48;
    c = getchar();
  }
  return x * f;
}
struct cow {
  int A[500009];
  struct tree {
    int l, r;
    int val, tag;
  } t[500009 << 2];
  void update(int rt) {
    t[rt].val = min(t[(rt << 1)].val, t[(rt << 1 | 1)].val);
  }
  void pushdown(int rt) {
    if (t[rt].tag == -1) return;
    t[(rt << 1)].tag = t[(rt << 1 | 1)].tag = t[rt].tag;
    t[(rt << 1)].val = t[(rt << 1 | 1)].val = t[rt].tag;
    t[rt].tag = -1;
  }
  void build(int rt, int l, int r) {
    t[rt].l = l;
    t[rt].r = r;
    t[rt].tag = -1;
    if (l == r) {
      t[rt].val = A[l];
      return;
    }
    int mid = (t[rt].l + t[rt].r) / 2;
    build((rt << 1), l, mid);
    build((rt << 1 | 1), mid + 1, r);
    update(rt);
  }
  void change(int rt, int L, int R, int k) {
    if (L <= t[rt].l && t[rt].r <= R) {
      t[rt].tag = t[rt].val = k;
      return;
    }
    int mid = (t[rt].l + t[rt].r) / 2;
    pushdown(rt);
    if (L <= mid) change((rt << 1), L, R, k);
    if (R > mid) change((rt << 1 | 1), L, R, k);
    update(rt);
  }
  int query(int rt, int L, int R) {
    if (L <= t[rt].l && t[rt].r <= R) return t[rt].val;
    int mid = (t[rt].l + t[rt].r) / 2;
    pushdown(rt);
    int ans = 1e9;
    if (L <= mid) ans = min(ans, query((rt << 1), L, R));
    if (R > mid) ans = min(ans, query((rt << 1 | 1), L, R));
    return ans;
  }
} re, now;
int op[500009], l[500009], r[500009], v[500009];
int B[500009];
int n, k;
int getval(int l, int r) {
  if (l > r) return 1e9;
  int key = (r / n) * n;
  if (key == r) key -= n;
  if (l > key) return re.query(1, (l - 1) % n + 1, (r - 1) % n + 1);
  if (l <= key - n) return re.t[1].val;
  return min(re.query(1, 1, (r - 1) % n + 1), re.query(1, (l - 1) % n + 1, n));
}
int main() {
  n = read();
  k = read();
  for (int i = 1; i <= n; i++) re.A[i] = read();
  re.build(1, 1, n);
  int m = read();
  for (int i = 1; i <= m; i++) {
    op[i] = read();
    l[i] = read();
    r[i] = read();
    B[i] = l[i];
    B[i + m] = r[i];
    if (op[i] == 1) v[i] = read();
  }
  sort(B + 1, B + m + m + 1);
  int len = unique(B + 1, B + m + m + 1) - B - 1;
  for (int i = 1; i <= len; i++) {
    now.A[i + i - 1] = re.A[(B[i] - 1) % n + 1];
  }
  for (int i = 1; i < len; i++) {
    now.A[i + i] = getval(B[i] + 1, B[i + 1] - 1);
  }
  now.build(1, 1, len + len - 1);
  for (int i = 1; i <= m; i++) {
    int L = lower_bound(B + 1, B + len + 1, l[i]) - B;
    L = L + L - 1;
    int R = lower_bound(B + 1, B + len + 1, r[i]) - B;
    R = R + R - 1;
    if (op[i] == 1) {
      now.change(1, L, R, v[i]);
    }
    if (op[i] == 2) {
      printf("%d\n", now.query(1, L, R));
    }
  }
  return 0;
}

```