#include <bits/stdc++.h>
using namespace std;
pair<int, pair<int, int> > L[200007];
int typ[100007];
int l[100007];
int p[100007];
int war[100007];
map<int, int> mapa;
int lazy[2 * 4 * 131072 + 7];
int tree[2 * 4 * 131072 + 7];
int tree2[2 * 4 * 131072 + 7];
int t[100007];
int Lp[8 * 100007], Pp[8 * 100007];
void akt(int v) {
  while (v != 0) {
    tree[v] = min(tree[v * 2], tree[2 * v + 1]);
    v /= 2;
  }
}
int minn(int ll, int rr, int v, int l, int r) {
  int odp = 1000000007;
  if (l > rr || r < ll || v >= 2 * 4 * 131072) {
    return 1000000007;
  }
  if (l >= ll && r <= rr) {
    odp = min(odp, tree[v]);
    return odp;
  }
  if (lazy[v]) {
    lazy[2 * v] = lazy[v];
    lazy[2 * v + 1] = lazy[v];
    tree[2 * v] = lazy[v];
    tree[2 * v + 1] = lazy[v];
    lazy[v] = 0;
  }
  int sr = (l + r) / 2;
  odp = min(odp, minn(ll, rr, v * 2, l, sr));
  odp = min(odp, minn(ll, rr, 2 * v + 1, sr + 1, r));
  return odp;
}
void setuj(int ll, int rr, int v, int w, int l, int r) {
  if (l > rr || r < ll || v >= 2 * 4 * 131072) {
    return;
  }
  if (l >= ll && r <= rr) {
    tree[v] = w;
    lazy[v] = w;
    akt(v / 2);
    return;
  }
  if (lazy[v]) {
    lazy[2 * v] = lazy[v];
    lazy[2 * v + 1] = lazy[v];
    tree[2 * v] = lazy[v];
    tree[2 * v + 1] = lazy[v];
    lazy[v] = 0;
  }
  int sr = (l + r) / 2;
  setuj(ll, rr, v * 2, w, l, sr);
  setuj(ll, rr, 2 * v + 1, w, sr + 1, r);
  return;
}
int minn2(int ll, int rr, int v, int l, int r) {
  int odp = 1000000007;
  if (l > rr || r < ll || v >= 2 * 4 * 131072) {
    return 1000000007;
  }
  if (l >= ll && r <= rr) {
    odp = min(odp, tree2[v]);
    return odp;
  }
  int sr = (l + r) / 2;
  odp = min(odp, minn2(ll, rr, v * 2, l, sr));
  odp = min(odp, minn2(ll, rr, 2 * v + 1, sr + 1, r));
  return odp;
}
int main(void) {
  int licznik = 0;
  int n, k, q, a, b, x, c;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    t[i] = x;
    tree2[i + 4 * 131072] = x;
  }
  for (int i = 4 * 131072 + n; i < 4 * 131072 * 2; i++) {
    tree2[i] = 1000000007;
  }
  for (int i = 4 * 131072 - 1; i > 0; i--) {
    tree2[i] = min(tree2[i * 2], tree2[i * 2 + 1]);
  }
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    x = 0;
    scanf("%d %d %d", &a, &b, &c);
    if (a == 1) {
      scanf("%d", &x);
    }
    L[i] = {b, {a, i}};
    L[i + q] = {c, {a, i}};
    war[i] = x;
  }
  sort(L, L + 2 * q);
  for (int i = 0; i < 2 * q; i++) {
    a = L[i].first;
    b = L[i].second.first;
    c = L[i].second.second;
    if (!mapa[a]) {
      licznik++;
      mapa[a] = licznik;
    }
    int d = mapa[a];
    typ[c] = b;
    if (l[c]) {
      p[c] = 2 * d - 1;
      Pp[max(2 * d - 3, 0)] = a - 1;
      Lp[2 * d - 1] = a + 1;
      tree[2 * d - 1 + 4 * 131072 - 1] = t[(a - 1) % n];
    } else {
      l[c] = 2 * d - 1;
      Pp[max(2 * d - 3, 0)] = a - 1;
      Lp[2 * d - 1] = a + 1;
      tree[2 * d - 1 + 4 * 131072 - 1] = t[(a - 1) % n];
    }
  }
  for (int i = 2 * licznik - 1 + 4 * 131072 + 1; i < 2 * 4 * 131072; i++) {
    tree[i] = 1000000007;
  }
  for (int i = 1; i < 4 * 131072; i += 2) {
    a = Lp[i];
    b = Pp[i];
    if (a > b) {
      tree[i + 4 * 131072] = 1000000007;
      continue;
    }
    if ((a - 1) / n != (b - 1) / n) {
      if (b >= a + n) {
        tree[i + 4 * 131072] = minn2(1, n, 1, 1, 4 * 131072);
      } else {
        tree[i + 4 * 131072] = min(minn2(1, (b - 1) % n + 1, 1, 1, 4 * 131072),
                                   minn2((a - 1) % n + 1, n, 1, 1, 4 * 131072));
      }
    } else
      tree[i + 4 * 131072] =
          minn2((a - 1) % n + 1, (b - 1) % n + 1, 1, 1, 4 * 131072);
  }
  for (int i = 4 * 131072 - 1; i > 0; i--) {
    tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
  }
  for (int i = 0; i < q; i++) {
    a = typ[i];
    b = l[i];
    c = p[i];
    x = war[i];
    if (a == 1) {
      setuj(b, c, 1, x, 1, 4 * 131072);
    } else {
      printf("%d\n", minn(b, c, 1, 1, 4 * 131072));
    }
  }
  return 0;
}

### Prompt

Your task is to create 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;
pair<int, pair<int, int> > L[200007];
int typ[100007];
int l[100007];
int p[100007];
int war[100007];
map<int, int> mapa;
int lazy[2 * 4 * 131072 + 7];
int tree[2 * 4 * 131072 + 7];
int tree2[2 * 4 * 131072 + 7];
int t[100007];
int Lp[8 * 100007], Pp[8 * 100007];
void akt(int v) {
  while (v != 0) {
    tree[v] = min(tree[v * 2], tree[2 * v + 1]);
    v /= 2;
  }
}
int minn(int ll, int rr, int v, int l, int r) {
  int odp = 1000000007;
  if (l > rr || r < ll || v >= 2 * 4 * 131072) {
    return 1000000007;
  }
  if (l >= ll && r <= rr) {
    odp = min(odp, tree[v]);
    return odp;
  }
  if (lazy[v]) {
    lazy[2 * v] = lazy[v];
    lazy[2 * v + 1] = lazy[v];
    tree[2 * v] = lazy[v];
    tree[2 * v + 1] = lazy[v];
    lazy[v] = 0;
  }
  int sr = (l + r) / 2;
  odp = min(odp, minn(ll, rr, v * 2, l, sr));
  odp = min(odp, minn(ll, rr, 2 * v + 1, sr + 1, r));
  return odp;
}
void setuj(int ll, int rr, int v, int w, int l, int r) {
  if (l > rr || r < ll || v >= 2 * 4 * 131072) {
    return;
  }
  if (l >= ll && r <= rr) {
    tree[v] = w;
    lazy[v] = w;
    akt(v / 2);
    return;
  }
  if (lazy[v]) {
    lazy[2 * v] = lazy[v];
    lazy[2 * v + 1] = lazy[v];
    tree[2 * v] = lazy[v];
    tree[2 * v + 1] = lazy[v];
    lazy[v] = 0;
  }
  int sr = (l + r) / 2;
  setuj(ll, rr, v * 2, w, l, sr);
  setuj(ll, rr, 2 * v + 1, w, sr + 1, r);
  return;
}
int minn2(int ll, int rr, int v, int l, int r) {
  int odp = 1000000007;
  if (l > rr || r < ll || v >= 2 * 4 * 131072) {
    return 1000000007;
  }
  if (l >= ll && r <= rr) {
    odp = min(odp, tree2[v]);
    return odp;
  }
  int sr = (l + r) / 2;
  odp = min(odp, minn2(ll, rr, v * 2, l, sr));
  odp = min(odp, minn2(ll, rr, 2 * v + 1, sr + 1, r));
  return odp;
}
int main(void) {
  int licznik = 0;
  int n, k, q, a, b, x, c;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    t[i] = x;
    tree2[i + 4 * 131072] = x;
  }
  for (int i = 4 * 131072 + n; i < 4 * 131072 * 2; i++) {
    tree2[i] = 1000000007;
  }
  for (int i = 4 * 131072 - 1; i > 0; i--) {
    tree2[i] = min(tree2[i * 2], tree2[i * 2 + 1]);
  }
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    x = 0;
    scanf("%d %d %d", &a, &b, &c);
    if (a == 1) {
      scanf("%d", &x);
    }
    L[i] = {b, {a, i}};
    L[i + q] = {c, {a, i}};
    war[i] = x;
  }
  sort(L, L + 2 * q);
  for (int i = 0; i < 2 * q; i++) {
    a = L[i].first;
    b = L[i].second.first;
    c = L[i].second.second;
    if (!mapa[a]) {
      licznik++;
      mapa[a] = licznik;
    }
    int d = mapa[a];
    typ[c] = b;
    if (l[c]) {
      p[c] = 2 * d - 1;
      Pp[max(2 * d - 3, 0)] = a - 1;
      Lp[2 * d - 1] = a + 1;
      tree[2 * d - 1 + 4 * 131072 - 1] = t[(a - 1) % n];
    } else {
      l[c] = 2 * d - 1;
      Pp[max(2 * d - 3, 0)] = a - 1;
      Lp[2 * d - 1] = a + 1;
      tree[2 * d - 1 + 4 * 131072 - 1] = t[(a - 1) % n];
    }
  }
  for (int i = 2 * licznik - 1 + 4 * 131072 + 1; i < 2 * 4 * 131072; i++) {
    tree[i] = 1000000007;
  }
  for (int i = 1; i < 4 * 131072; i += 2) {
    a = Lp[i];
    b = Pp[i];
    if (a > b) {
      tree[i + 4 * 131072] = 1000000007;
      continue;
    }
    if ((a - 1) / n != (b - 1) / n) {
      if (b >= a + n) {
        tree[i + 4 * 131072] = minn2(1, n, 1, 1, 4 * 131072);
      } else {
        tree[i + 4 * 131072] = min(minn2(1, (b - 1) % n + 1, 1, 1, 4 * 131072),
                                   minn2((a - 1) % n + 1, n, 1, 1, 4 * 131072));
      }
    } else
      tree[i + 4 * 131072] =
          minn2((a - 1) % n + 1, (b - 1) % n + 1, 1, 1, 4 * 131072);
  }
  for (int i = 4 * 131072 - 1; i > 0; i--) {
    tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
  }
  for (int i = 0; i < q; i++) {
    a = typ[i];
    b = l[i];
    c = p[i];
    x = war[i];
    if (a == 1) {
      setuj(b, c, 1, x, 1, 4 * 131072);
    } else {
      printf("%d\n", minn(b, c, 1, 1, 4 * 131072));
    }
  }
  return 0;
}

```