#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 20;
int v[maxn], pool[maxn << 2], arr[maxn >> 1], flag[maxn << 2];
void build(int u, int l, int r) {
  if (l == r)
    pool[u] = v[l];
  else {
    int md = l + r >> 1, ls = u << 1, rs = ls | 1;
    build(ls, l, md);
    build(rs, md + 1, r);
    pool[u] = min(pool[ls], pool[rs]);
  }
}
void push_down(int u) {
  if (flag[u]) {
    int ls = u << 1, rs = ls | 1, fl = flag[u];
    flag[u] = 0;
    flag[ls] = fl;
    flag[rs] = fl;
    pool[ls] = fl;
    pool[rs] = fl;
  }
}
void update(int u, int l, int r, int L, int R, int x) {
  if (L <= l and r <= R)
    pool[u] = x, flag[u] = x;
  else {
    push_down(u);
    int md = l + r >> 1, ls = u << 1, rs = ls | 1;
    if (R <= md)
      update(ls, l, md, L, R, x);
    else if (md < L)
      update(rs, md + 1, r, L, R, x);
    else
      update(ls, l, md, L, R, x), update(rs, md + 1, r, L, R, x);
    pool[u] = min(pool[ls], pool[rs]);
  }
}
int calc(int u, int l, int r, int L, int R) {
  if (L <= l and r <= R) return pool[u];
  int md = l + r >> 1, ls = u << 1, rs = ls | 1;
  if (R <= md)
    return calc(ls, l, md, L, R);
  else if (md < L)
    return calc(rs, md + 1, r, L, R);
  else
    return min(calc(ls, l, md, L, R), calc(rs, md + 1, r, L, R));
}
int calc1(int u, int l, int r, int L, int R) {
  if (L <= l and r <= R) return pool[u];
  int md = l + r >> 1, ls = u << 1, rs = ls | 1;
  push_down(u);
  if (R <= md)
    return calc1(ls, l, md, L, R);
  else if (md < L)
    return calc1(rs, md + 1, r, L, R);
  else
    return min(calc1(ls, l, md, L, R), calc1(rs, md + 1, r, L, R));
}
int n, m, l[maxn >> 2], r[maxn >> 2], t[maxn >> 2], x[maxn >> 2], nn, N, k, L,
    R;
int dfn[maxn >> 1];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", v + i);
  build(1, 0, n - 1);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", t + i, l + i, r + i);
    l[i]--;
    r[i]--;
    arr[i] = l[i];
    arr[i + m] = r[i];
    if (t[i] == 1) scanf("%d", x + i);
  }
  nn = m << 1;
  sort(arr, arr + nn);
  nn = unique(arr, arr + nn) - arr;
  if (arr[0]) {
    if (arr[0] >= n)
      v[N++] = pool[1];
    else
      v[N++] = calc(1, 0, n - 1, 0, arr[0]);
  }
  arr[nn] = n * k;
  for (int i = 0; i < nn; i++) {
    dfn[i] = N;
    v[N++] = calc(1, 0, n - 1, arr[i] % n, arr[i] % n);
    if (arr[i] + 1 == arr[i + 1]) continue;
    if (arr[i] + n < arr[i + 1])
      v[N++] = pool[1];
    else {
      L = arr[i] % n, R = arr[i + 1] % n;
      L++, R--;
      if (L == n) L = 0;
      if (R == -1) R = n - 1;
      if (L <= R)
        v[N++] = calc(1, 0, n - 1, L, R);
      else {
        v[N++] = min(calc(1, 0, n - 1, 0, R), calc(1, 0, n - 1, L, n - 1));
      }
    }
  }
  build(1, 0, N - 1);
  for (int i = 0; i < m; i++) {
    L = lower_bound(arr, arr + nn, l[i]) - arr;
    R = lower_bound(arr, arr + nn, r[i]) - arr;
    if (t[i] == 1) {
      update(1, 0, N - 1, dfn[L], dfn[R], x[i]);
    } else {
      printf("%d\n", calc1(1, 0, N - 1, dfn[L], dfn[R]));
    }
  }
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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 = 4e5 + 20;
int v[maxn], pool[maxn << 2], arr[maxn >> 1], flag[maxn << 2];
void build(int u, int l, int r) {
  if (l == r)
    pool[u] = v[l];
  else {
    int md = l + r >> 1, ls = u << 1, rs = ls | 1;
    build(ls, l, md);
    build(rs, md + 1, r);
    pool[u] = min(pool[ls], pool[rs]);
  }
}
void push_down(int u) {
  if (flag[u]) {
    int ls = u << 1, rs = ls | 1, fl = flag[u];
    flag[u] = 0;
    flag[ls] = fl;
    flag[rs] = fl;
    pool[ls] = fl;
    pool[rs] = fl;
  }
}
void update(int u, int l, int r, int L, int R, int x) {
  if (L <= l and r <= R)
    pool[u] = x, flag[u] = x;
  else {
    push_down(u);
    int md = l + r >> 1, ls = u << 1, rs = ls | 1;
    if (R <= md)
      update(ls, l, md, L, R, x);
    else if (md < L)
      update(rs, md + 1, r, L, R, x);
    else
      update(ls, l, md, L, R, x), update(rs, md + 1, r, L, R, x);
    pool[u] = min(pool[ls], pool[rs]);
  }
}
int calc(int u, int l, int r, int L, int R) {
  if (L <= l and r <= R) return pool[u];
  int md = l + r >> 1, ls = u << 1, rs = ls | 1;
  if (R <= md)
    return calc(ls, l, md, L, R);
  else if (md < L)
    return calc(rs, md + 1, r, L, R);
  else
    return min(calc(ls, l, md, L, R), calc(rs, md + 1, r, L, R));
}
int calc1(int u, int l, int r, int L, int R) {
  if (L <= l and r <= R) return pool[u];
  int md = l + r >> 1, ls = u << 1, rs = ls | 1;
  push_down(u);
  if (R <= md)
    return calc1(ls, l, md, L, R);
  else if (md < L)
    return calc1(rs, md + 1, r, L, R);
  else
    return min(calc1(ls, l, md, L, R), calc1(rs, md + 1, r, L, R));
}
int n, m, l[maxn >> 2], r[maxn >> 2], t[maxn >> 2], x[maxn >> 2], nn, N, k, L,
    R;
int dfn[maxn >> 1];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", v + i);
  build(1, 0, n - 1);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", t + i, l + i, r + i);
    l[i]--;
    r[i]--;
    arr[i] = l[i];
    arr[i + m] = r[i];
    if (t[i] == 1) scanf("%d", x + i);
  }
  nn = m << 1;
  sort(arr, arr + nn);
  nn = unique(arr, arr + nn) - arr;
  if (arr[0]) {
    if (arr[0] >= n)
      v[N++] = pool[1];
    else
      v[N++] = calc(1, 0, n - 1, 0, arr[0]);
  }
  arr[nn] = n * k;
  for (int i = 0; i < nn; i++) {
    dfn[i] = N;
    v[N++] = calc(1, 0, n - 1, arr[i] % n, arr[i] % n);
    if (arr[i] + 1 == arr[i + 1]) continue;
    if (arr[i] + n < arr[i + 1])
      v[N++] = pool[1];
    else {
      L = arr[i] % n, R = arr[i + 1] % n;
      L++, R--;
      if (L == n) L = 0;
      if (R == -1) R = n - 1;
      if (L <= R)
        v[N++] = calc(1, 0, n - 1, L, R);
      else {
        v[N++] = min(calc(1, 0, n - 1, 0, R), calc(1, 0, n - 1, L, n - 1));
      }
    }
  }
  build(1, 0, N - 1);
  for (int i = 0; i < m; i++) {
    L = lower_bound(arr, arr + nn, l[i]) - arr;
    R = lower_bound(arr, arr + nn, r[i]) - arr;
    if (t[i] == 1) {
      update(1, 0, N - 1, dfn[L], dfn[R], x[i]);
    } else {
      printf("%d\n", calc1(1, 0, N - 1, dfn[L], dfn[R]));
    }
  }
  return 0;
}

```