#include <bits/stdc++.h>
using namespace std;
int mint;
struct tree {
  int l, r;
  int ls, rs;
  int w, tag;
  tree() {}
  tree(int L, int R, int LS, int RS, int W, int TAG) {
    l = L;
    r = R;
    ls = LS;
    rs = RS;
    w = W;
    tag = TAG;
  }
} tr[5000004];
int a[100004];
int n, k, cnt;
int up, td[400004];
int pask(int l, int r) {
  int ans = 1999122700;
  for (l = l + up - 1, r = r + up + 1; r - l > 1; r >>= 1, l >>= 1) {
    if (~l & 1) ans = min(ans, td[l + 1]);
    if (r & 1) ans = min(ans, td[r - 1]);
  }
  return ans;
}
int ask(int l, int r) {
  if (r - l + 1 >= n) return mint;
  l--;
  l %= n;
  l++;
  r--;
  r %= n;
  r++;
  if (l <= r)
    return pask(l, r);
  else
    return min(pask(l, n), pask(1, r));
}
void takedown(int k) {
  int l = tr[k].l, r = tr[k].r;
  int mid = (l + r) >> 1;
  if (tr[k].ls == -1) {
    tr[k].ls = ++cnt;
    tr[cnt] = tree(l, mid, -1, -1, ask(l, mid), -1);
  }
  if (tr[k].rs == -1) {
    tr[k].rs = ++cnt;
    tr[cnt] = tree(mid + 1, r, -1, -1, ask(mid + 1, r), -1);
  }
}
void push(int k) {
  takedown(k);
  if (tr[k].tag == -1) return;
  int tag = tr[k].tag;
  tr[k].tag = -1;
  tr[tr[k].ls].w = tag;
  tr[tr[k].ls].tag = tag;
  tr[tr[k].rs].w = tag;
  tr[tr[k].rs].tag = tag;
}
void change(int k, int a, int b, int x) {
  int l = tr[k].l, r = tr[k].r;
  if (l == a && r == b) {
    tr[k].tag = x;
    tr[k].w = x;
    return;
  }
  push(k);
  int mid = (l + r) >> 1;
  if (b <= mid)
    change(tr[k].ls, a, b, x);
  else if (a > mid)
    change(tr[k].rs, a, b, x);
  else {
    change(tr[k].ls, a, mid, x);
    change(tr[k].rs, mid + 1, b, x);
  }
  tr[k].w = min(tr[tr[k].ls].w, tr[tr[k].rs].w);
}
int query(int k, int a, int b) {
  int l = tr[k].l, r = tr[k].r;
  if (l == a && r == b) return tr[k].w;
  push(k);
  int mid = (l + r) >> 1;
  if (b <= mid)
    return query(tr[k].ls, a, b);
  else if (a > mid)
    return query(tr[k].rs, a, b);
  else
    return min(query(tr[k].ls, a, mid), query(tr[k].rs, mid + 1, b));
}
int main() {
  cnt = 0;
  up = 1;
  scanf("%d%d", &n, &k);
  mint = -1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (mint == -1) mint = a[i];
    mint = min(mint, a[i]);
  }
  while (up < n + 2) up <<= 1;
  for (int i = 1; i <= n; i++) td[i + up] = a[i];
  for (int i = up; i >= 1; i--) td[i] = min(td[i << 1], td[i << 1 | 1]);
  tr[++cnt] = tree(1, n * k, -1, -1, mint, -1);
  int q;
  scanf("%d", &q);
  while (q--) {
    int t, l, r, x;
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      scanf("%d", &x);
      change(1, l, r, x);
    }
    if (t == 2) {
      printf("%d\n", query(1, l, r));
    }
  }
  return 0;
}

### Prompt

Create a solution in cpp for 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 mint;
struct tree {
  int l, r;
  int ls, rs;
  int w, tag;
  tree() {}
  tree(int L, int R, int LS, int RS, int W, int TAG) {
    l = L;
    r = R;
    ls = LS;
    rs = RS;
    w = W;
    tag = TAG;
  }
} tr[5000004];
int a[100004];
int n, k, cnt;
int up, td[400004];
int pask(int l, int r) {
  int ans = 1999122700;
  for (l = l + up - 1, r = r + up + 1; r - l > 1; r >>= 1, l >>= 1) {
    if (~l & 1) ans = min(ans, td[l + 1]);
    if (r & 1) ans = min(ans, td[r - 1]);
  }
  return ans;
}
int ask(int l, int r) {
  if (r - l + 1 >= n) return mint;
  l--;
  l %= n;
  l++;
  r--;
  r %= n;
  r++;
  if (l <= r)
    return pask(l, r);
  else
    return min(pask(l, n), pask(1, r));
}
void takedown(int k) {
  int l = tr[k].l, r = tr[k].r;
  int mid = (l + r) >> 1;
  if (tr[k].ls == -1) {
    tr[k].ls = ++cnt;
    tr[cnt] = tree(l, mid, -1, -1, ask(l, mid), -1);
  }
  if (tr[k].rs == -1) {
    tr[k].rs = ++cnt;
    tr[cnt] = tree(mid + 1, r, -1, -1, ask(mid + 1, r), -1);
  }
}
void push(int k) {
  takedown(k);
  if (tr[k].tag == -1) return;
  int tag = tr[k].tag;
  tr[k].tag = -1;
  tr[tr[k].ls].w = tag;
  tr[tr[k].ls].tag = tag;
  tr[tr[k].rs].w = tag;
  tr[tr[k].rs].tag = tag;
}
void change(int k, int a, int b, int x) {
  int l = tr[k].l, r = tr[k].r;
  if (l == a && r == b) {
    tr[k].tag = x;
    tr[k].w = x;
    return;
  }
  push(k);
  int mid = (l + r) >> 1;
  if (b <= mid)
    change(tr[k].ls, a, b, x);
  else if (a > mid)
    change(tr[k].rs, a, b, x);
  else {
    change(tr[k].ls, a, mid, x);
    change(tr[k].rs, mid + 1, b, x);
  }
  tr[k].w = min(tr[tr[k].ls].w, tr[tr[k].rs].w);
}
int query(int k, int a, int b) {
  int l = tr[k].l, r = tr[k].r;
  if (l == a && r == b) return tr[k].w;
  push(k);
  int mid = (l + r) >> 1;
  if (b <= mid)
    return query(tr[k].ls, a, b);
  else if (a > mid)
    return query(tr[k].rs, a, b);
  else
    return min(query(tr[k].ls, a, mid), query(tr[k].rs, mid + 1, b));
}
int main() {
  cnt = 0;
  up = 1;
  scanf("%d%d", &n, &k);
  mint = -1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (mint == -1) mint = a[i];
    mint = min(mint, a[i]);
  }
  while (up < n + 2) up <<= 1;
  for (int i = 1; i <= n; i++) td[i + up] = a[i];
  for (int i = up; i >= 1; i--) td[i] = min(td[i << 1], td[i << 1 | 1]);
  tr[++cnt] = tree(1, n * k, -1, -1, mint, -1);
  int q;
  scanf("%d", &q);
  while (q--) {
    int t, l, r, x;
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      scanf("%d", &x);
      change(1, l, r, x);
    }
    if (t == 2) {
      printf("%d\n", query(1, l, r));
    }
  }
  return 0;
}

```