#include <bits/stdc++.h>
using namespace std;
const int mod = (int)1e9 + 7;
const int inf = (int)1e9 + 123;
const long long infl = (long long)1e18 + 123;
const double eps = 1e-10;
const int MAX_N = (int)1e5 + 123;
int mini[20][MAX_N], lg[MAX_N];
int n, k;
int a[MAX_N];
int getMini(int l, int r) {
  int i = lg[r - l + 1];
  return min(mini[i][l], mini[i][r - (1 << i) + 1]);
}
int getMiniInBigArray(int l, int r) {
  if (r - l + 1 >= n) return getMini(0, n - 1);
  l %= n, r %= n;
  if (l <= r) return getMini(l, r);
  return min(getMini(l, n - 1), getMini(0, r));
}
struct Tree {
  int mini, flag, l, r;
  Tree() : mini(inf), flag(-1), l(-1), r(-1) {}
  Tree(int x) : mini(x), flag(-1), l(-1), r(-1) {}
};
vector<Tree> t;
void push(int v, int tl, int tr) {
  if (t[v].flag == -1) return;
  t[v].mini = t[v].flag;
  if (tl != tr) {
    int tm = (tl + tr) / 2;
    if (t[v].l == -1) {
      t[v].l = (int)((t).size());
      t.push_back(Tree(getMiniInBigArray(tl, tm)));
    }
    if (t[v].r == -1) {
      t[v].r = (int)((t).size());
      t.push_back(Tree(getMiniInBigArray(tm + 1, tr)));
    }
    t[t[v].l].flag = t[t[v].r].flag = t[v].flag;
  }
  t[v].flag = -1;
}
void update(int l, int r, int x, int v = 0, int tl = 0, int tr = n * k - 1) {
  push(v, tl, tr);
  if (tl > r || l > tr) return;
  if (tl >= l && tr <= r) {
    t[v].flag = x;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  if (t[v].l == -1) {
    t[v].l = (int)((t).size());
    t.push_back(Tree(getMiniInBigArray(tl, tm)));
  }
  if (t[v].r == -1) {
    t[v].r = (int)((t).size());
    t.push_back(Tree(getMiniInBigArray(tm + 1, tr)));
  }
  update(l, r, x, t[v].l, tl, tm), update(l, r, x, t[v].r, tm + 1, tr);
  t[v].mini = min(t[t[v].l].mini, t[t[v].r].mini);
}
int get(int l, int r, int v = 0, int tl = 0, int tr = n * k - 1) {
  push(v, tl, tr);
  if (tl > r || l > tr) return inf;
  if (tl >= l && tr <= r) return t[v].mini;
  int tm = (tl + tr) / 2;
  if (t[v].l == -1) {
    t[v].l = (int)((t).size());
    t.push_back(Tree(getMiniInBigArray(tl, tm)));
  }
  if (t[v].r == -1) {
    t[v].r = (int)((t).size());
    t.push_back(Tree(getMiniInBigArray(tm + 1, tr)));
  }
  return min(get(l, r, t[v].l, tl, tm), get(l, r, t[v].r, tm + 1, tr));
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 1, j = 0; i <= n; i++) {
    if ((1 << (j + 1)) == i) j++;
    lg[i] = j;
  }
  for (int it = 0; it < 20; it++)
    for (int i = 0; i + (1 << it) - 1 < n; i++)
      mini[it][i] =
          (it == 0 ? a[i]
                   : min(mini[it - 1][i], mini[it - 1][i + (1 << (it - 1))]));
  t.push_back(Tree(getMiniInBigArray(0, n * k - 1)));
  int query;
  scanf("%d", &query);
  for (int i = 1, tp, l, r, x; i <= query; i++) {
    scanf("%d%d%d", &tp, &l, &r);
    if (tp == 1) {
      scanf("%d", &x);
      l--, r--;
      update(l, r, x);
    } else {
      l--, r--;
      printf("%d\n", get(l, r));
    }
  }
  return 0;
}

### Prompt

Your challenge is to write 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;
const int mod = (int)1e9 + 7;
const int inf = (int)1e9 + 123;
const long long infl = (long long)1e18 + 123;
const double eps = 1e-10;
const int MAX_N = (int)1e5 + 123;
int mini[20][MAX_N], lg[MAX_N];
int n, k;
int a[MAX_N];
int getMini(int l, int r) {
  int i = lg[r - l + 1];
  return min(mini[i][l], mini[i][r - (1 << i) + 1]);
}
int getMiniInBigArray(int l, int r) {
  if (r - l + 1 >= n) return getMini(0, n - 1);
  l %= n, r %= n;
  if (l <= r) return getMini(l, r);
  return min(getMini(l, n - 1), getMini(0, r));
}
struct Tree {
  int mini, flag, l, r;
  Tree() : mini(inf), flag(-1), l(-1), r(-1) {}
  Tree(int x) : mini(x), flag(-1), l(-1), r(-1) {}
};
vector<Tree> t;
void push(int v, int tl, int tr) {
  if (t[v].flag == -1) return;
  t[v].mini = t[v].flag;
  if (tl != tr) {
    int tm = (tl + tr) / 2;
    if (t[v].l == -1) {
      t[v].l = (int)((t).size());
      t.push_back(Tree(getMiniInBigArray(tl, tm)));
    }
    if (t[v].r == -1) {
      t[v].r = (int)((t).size());
      t.push_back(Tree(getMiniInBigArray(tm + 1, tr)));
    }
    t[t[v].l].flag = t[t[v].r].flag = t[v].flag;
  }
  t[v].flag = -1;
}
void update(int l, int r, int x, int v = 0, int tl = 0, int tr = n * k - 1) {
  push(v, tl, tr);
  if (tl > r || l > tr) return;
  if (tl >= l && tr <= r) {
    t[v].flag = x;
    push(v, tl, tr);
    return;
  }
  int tm = (tl + tr) / 2;
  if (t[v].l == -1) {
    t[v].l = (int)((t).size());
    t.push_back(Tree(getMiniInBigArray(tl, tm)));
  }
  if (t[v].r == -1) {
    t[v].r = (int)((t).size());
    t.push_back(Tree(getMiniInBigArray(tm + 1, tr)));
  }
  update(l, r, x, t[v].l, tl, tm), update(l, r, x, t[v].r, tm + 1, tr);
  t[v].mini = min(t[t[v].l].mini, t[t[v].r].mini);
}
int get(int l, int r, int v = 0, int tl = 0, int tr = n * k - 1) {
  push(v, tl, tr);
  if (tl > r || l > tr) return inf;
  if (tl >= l && tr <= r) return t[v].mini;
  int tm = (tl + tr) / 2;
  if (t[v].l == -1) {
    t[v].l = (int)((t).size());
    t.push_back(Tree(getMiniInBigArray(tl, tm)));
  }
  if (t[v].r == -1) {
    t[v].r = (int)((t).size());
    t.push_back(Tree(getMiniInBigArray(tm + 1, tr)));
  }
  return min(get(l, r, t[v].l, tl, tm), get(l, r, t[v].r, tm + 1, tr));
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 1, j = 0; i <= n; i++) {
    if ((1 << (j + 1)) == i) j++;
    lg[i] = j;
  }
  for (int it = 0; it < 20; it++)
    for (int i = 0; i + (1 << it) - 1 < n; i++)
      mini[it][i] =
          (it == 0 ? a[i]
                   : min(mini[it - 1][i], mini[it - 1][i + (1 << (it - 1))]));
  t.push_back(Tree(getMiniInBigArray(0, n * k - 1)));
  int query;
  scanf("%d", &query);
  for (int i = 1, tp, l, r, x; i <= query; i++) {
    scanf("%d%d%d", &tp, &l, &r);
    if (tp == 1) {
      scanf("%d", &x);
      l--, r--;
      update(l, r, x);
    } else {
      l--, r--;
      printf("%d\n", get(l, r));
    }
  }
  return 0;
}

```