#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int a[222222], b[222222];
int mn[222222][22], val[222222];
pair<pair<int, int>, int> query[222222];
struct Node {
  int st, ed, mn;
  int flag1, flag2;
} mem[222222 << 2];
void push_up(int u) {
  mem[u].mn = min(mem[(u << 1)].mn, mem[((u << 1) + 1)].mn);
}
void push_down(int u) {
  if (!mem[u].flag1) return;
  mem[(u << 1)].mn = mem[((u << 1) + 1)].mn = mem[u].flag2;
  mem[(u << 1)].flag1 = mem[((u << 1) + 1)].flag1 = 1;
  mem[(u << 1)].flag2 = mem[((u << 1) + 1)].flag2 = mem[u].flag2;
  mem[u].flag1 = 0;
}
void build(int u, int L, int R) {
  mem[u].st = L, mem[u].ed = R;
  mem[u].flag1 = mem[u].flag2 = 0;
  if (L + 1 == R) {
    mem[u].mn = val[L];
    return;
  }
  build((u << 1), L, L + R >> 1);
  build(((u << 1) + 1), L + R >> 1, R);
  push_up(u);
}
void update(int u, int L, int R, int v) {
  int st = max(mem[u].st, L);
  int ed = min(mem[u].ed, R);
  if (st >= ed) return;
  if (mem[u].st == st && mem[u].ed == ed) {
    mem[u].mn = v;
    mem[u].flag1 = 1, mem[u].flag2 = v;
    return;
  }
  push_down(u);
  update((u << 1), st, ed, v);
  update(((u << 1) + 1), st, ed, v);
  push_up(u);
}
int calc(int u, int L, int R) {
  int st = max(mem[u].st, L);
  int ed = min(mem[u].ed, R);
  if (st >= ed) return 0x3f3f3f3f;
  if (mem[u].st == st && mem[u].ed == ed) return mem[u].mn;
  push_down(u);
  return min(calc((u << 1), st, ed), calc(((u << 1) + 1), st, ed));
}
int calc(int l, int r) {
  if (l >= r) return 0x3f3f3f3f;
  int k = 31 - (__builtin_clz(r - l));
  return min(mn[l][k], mn[r - (1 << k)][k]);
}
int main() {
  int n, m, k, q, l, r, c = 0x3f3f3f3f;
  cin >> n >> k;
  for (int i = 0; i < n; i++) gn(b[i]), smin(c, b[i]);
  for (int i = 0; i < n; i++) mn[i][0] = b[i];
  for (int k = 1; k < 22; k++)
    for (int i = 0; i + (1 << k) <= n; i++)
      mn[i][k] = min(mn[i][k - 1], mn[i + (1 << k - 1)][k - 1]);
  cin >> q;
  m = 0;
  for (int i = 0, t; i < q; i++) {
    gn(t);
    gn(l, r);
    l--;
    a[m++] = l, a[m++] = r;
    int u = 0x3f3f3f3f;
    if (t == 1) gn(u);
    query[i] = make_pair(make_pair(l, r), u);
  }
  sort(a, a + m);
  m = unique(a, a + m) - a;
  for (int i = 0; i < m - 1; i++) {
    int st1 = a[i] / n, st2 = a[i] % n;
    int ed1 = a[i + 1] / n, ed2 = a[i + 1] % n;
    if (ed1 > st1 + 1)
      val[i] = c;
    else if (ed1 > st1) {
      if (ed2 > st2)
        val[i] = c;
      else
        val[i] = min(calc(st2, n), calc(0, ed2));
    } else
      val[i] = calc(st2, ed2);
  }
  val[m - 1] = 0x3f3f3f3f;
  build(1, 0, m);
  for (int i = 0; i < q; i++) {
    l = query[i].first.first, r = query[i].first.second;
    int st = lower_bound(a, a + m, l) - a;
    int ed = lower_bound(a, a + m, r) - a;
    int u = query[i].second;
    if (u != 0x3f3f3f3f)
      update(1, st, ed, u);
    else
      println(calc(1, st, ed));
  }
  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;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int a[222222], b[222222];
int mn[222222][22], val[222222];
pair<pair<int, int>, int> query[222222];
struct Node {
  int st, ed, mn;
  int flag1, flag2;
} mem[222222 << 2];
void push_up(int u) {
  mem[u].mn = min(mem[(u << 1)].mn, mem[((u << 1) + 1)].mn);
}
void push_down(int u) {
  if (!mem[u].flag1) return;
  mem[(u << 1)].mn = mem[((u << 1) + 1)].mn = mem[u].flag2;
  mem[(u << 1)].flag1 = mem[((u << 1) + 1)].flag1 = 1;
  mem[(u << 1)].flag2 = mem[((u << 1) + 1)].flag2 = mem[u].flag2;
  mem[u].flag1 = 0;
}
void build(int u, int L, int R) {
  mem[u].st = L, mem[u].ed = R;
  mem[u].flag1 = mem[u].flag2 = 0;
  if (L + 1 == R) {
    mem[u].mn = val[L];
    return;
  }
  build((u << 1), L, L + R >> 1);
  build(((u << 1) + 1), L + R >> 1, R);
  push_up(u);
}
void update(int u, int L, int R, int v) {
  int st = max(mem[u].st, L);
  int ed = min(mem[u].ed, R);
  if (st >= ed) return;
  if (mem[u].st == st && mem[u].ed == ed) {
    mem[u].mn = v;
    mem[u].flag1 = 1, mem[u].flag2 = v;
    return;
  }
  push_down(u);
  update((u << 1), st, ed, v);
  update(((u << 1) + 1), st, ed, v);
  push_up(u);
}
int calc(int u, int L, int R) {
  int st = max(mem[u].st, L);
  int ed = min(mem[u].ed, R);
  if (st >= ed) return 0x3f3f3f3f;
  if (mem[u].st == st && mem[u].ed == ed) return mem[u].mn;
  push_down(u);
  return min(calc((u << 1), st, ed), calc(((u << 1) + 1), st, ed));
}
int calc(int l, int r) {
  if (l >= r) return 0x3f3f3f3f;
  int k = 31 - (__builtin_clz(r - l));
  return min(mn[l][k], mn[r - (1 << k)][k]);
}
int main() {
  int n, m, k, q, l, r, c = 0x3f3f3f3f;
  cin >> n >> k;
  for (int i = 0; i < n; i++) gn(b[i]), smin(c, b[i]);
  for (int i = 0; i < n; i++) mn[i][0] = b[i];
  for (int k = 1; k < 22; k++)
    for (int i = 0; i + (1 << k) <= n; i++)
      mn[i][k] = min(mn[i][k - 1], mn[i + (1 << k - 1)][k - 1]);
  cin >> q;
  m = 0;
  for (int i = 0, t; i < q; i++) {
    gn(t);
    gn(l, r);
    l--;
    a[m++] = l, a[m++] = r;
    int u = 0x3f3f3f3f;
    if (t == 1) gn(u);
    query[i] = make_pair(make_pair(l, r), u);
  }
  sort(a, a + m);
  m = unique(a, a + m) - a;
  for (int i = 0; i < m - 1; i++) {
    int st1 = a[i] / n, st2 = a[i] % n;
    int ed1 = a[i + 1] / n, ed2 = a[i + 1] % n;
    if (ed1 > st1 + 1)
      val[i] = c;
    else if (ed1 > st1) {
      if (ed2 > st2)
        val[i] = c;
      else
        val[i] = min(calc(st2, n), calc(0, ed2));
    } else
      val[i] = calc(st2, ed2);
  }
  val[m - 1] = 0x3f3f3f3f;
  build(1, 0, m);
  for (int i = 0; i < q; i++) {
    l = query[i].first.first, r = query[i].first.second;
    int st = lower_bound(a, a + m, l) - a;
    int ed = lower_bound(a, a + m, r) - a;
    int u = query[i].second;
    if (u != 0x3f3f3f3f)
      update(1, st, ed, u);
    else
      println(calc(1, st, ed));
  }
  return 0;
}

```