#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 10;
const long long inf = 1e9 + 10;
long long seg[2 * N];
long long n, k;
long long query(long long l, long long r) {
  l += n;
  r += n + 1;
  long long res = inf;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = min(res, seg[l++]);
    if (r & 1) res = min(res, seg[--r]);
  }
  return res;
}
struct node {
  long long l, r, mn, lazy;
  node *L, *R;
  void init(long long ll, long long rr, long long val) {
    mn = val;
    l = ll;
    r = rr;
    lazy = inf;
    L = R = NULL;
  }
};
node* root;
long long go(long long l, long long r) {
  if ((r - l + 1) >= n) return seg[1];
  l %= n;
  r %= n;
  if (l <= r) return query(l, r);
  return min(query(l, n - 1), query(0, r));
}
void upd(node* nd, long long l, long long r, long long x) {
  if (nd->lazy != inf) nd->mn = nd->lazy;
  long long ss = nd->l;
  long long se = nd->r;
  if (ss > r || se < l) return;
  if (l <= ss && se <= r) {
    nd->mn = nd->lazy = x;
    return;
  }
  long long mid = (ss + se) / 2;
  if (nd->L == NULL) {
    nd->L = new node();
    nd->L->init(ss, mid, go(ss, mid));
  }
  if (nd->R == NULL) {
    nd->R = new node();
    nd->R->init(mid + 1, se, go(mid + 1, se));
  }
  if (nd->lazy != inf) {
    nd->L->lazy = nd->lazy;
    nd->R->lazy = nd->lazy;
    nd->lazy = inf;
  }
  upd(nd->L, l, r, x);
  upd(nd->R, l, r, x);
  nd->mn = min(nd->L->mn, nd->R->mn);
}
long long query2(node* nd, long long l, long long r) {
  if (nd->lazy != inf) nd->mn = nd->lazy;
  long long ss = nd->l;
  long long se = nd->r;
  if (ss > r || se < l) return inf;
  if (l <= ss && se <= r) return nd->mn;
  long long mid = (ss + se) / 2;
  if (nd->L == NULL) {
    nd->L = new node();
    nd->L->init(ss, mid, go(ss, mid));
  }
  if (nd->R == NULL) {
    nd->R = new node();
    nd->R->init(mid + 1, se, go(mid + 1, se));
  }
  if (nd->lazy != inf) {
    nd->L->lazy = nd->lazy;
    nd->R->lazy = nd->lazy;
    nd->lazy = inf;
  }
  return min(query2(nd->L, l, r), query2(nd->R, l, r));
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (long long i = 0; i < n; i++) cin >> seg[i + n];
  for (long long i = n - 1; i >= 1; i--)
    seg[i] = min(seg[i << 1], seg[i << 1 ^ 1]);
  root = new node();
  root->init(0, (n * k) - 1, seg[1]);
  long long q;
  cin >> q;
  long long t, l, r, x;
  while (q--) {
    cin >> t >> l >> r;
    l--;
    r--;
    if (t == 1) {
      cin >> x;
      upd(root, l, r, x);
    } else
      cout << query2(root, l, r) << '\n';
  }
}

### 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 long long N = 1e5 + 10;
const long long inf = 1e9 + 10;
long long seg[2 * N];
long long n, k;
long long query(long long l, long long r) {
  l += n;
  r += n + 1;
  long long res = inf;
  for (; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = min(res, seg[l++]);
    if (r & 1) res = min(res, seg[--r]);
  }
  return res;
}
struct node {
  long long l, r, mn, lazy;
  node *L, *R;
  void init(long long ll, long long rr, long long val) {
    mn = val;
    l = ll;
    r = rr;
    lazy = inf;
    L = R = NULL;
  }
};
node* root;
long long go(long long l, long long r) {
  if ((r - l + 1) >= n) return seg[1];
  l %= n;
  r %= n;
  if (l <= r) return query(l, r);
  return min(query(l, n - 1), query(0, r));
}
void upd(node* nd, long long l, long long r, long long x) {
  if (nd->lazy != inf) nd->mn = nd->lazy;
  long long ss = nd->l;
  long long se = nd->r;
  if (ss > r || se < l) return;
  if (l <= ss && se <= r) {
    nd->mn = nd->lazy = x;
    return;
  }
  long long mid = (ss + se) / 2;
  if (nd->L == NULL) {
    nd->L = new node();
    nd->L->init(ss, mid, go(ss, mid));
  }
  if (nd->R == NULL) {
    nd->R = new node();
    nd->R->init(mid + 1, se, go(mid + 1, se));
  }
  if (nd->lazy != inf) {
    nd->L->lazy = nd->lazy;
    nd->R->lazy = nd->lazy;
    nd->lazy = inf;
  }
  upd(nd->L, l, r, x);
  upd(nd->R, l, r, x);
  nd->mn = min(nd->L->mn, nd->R->mn);
}
long long query2(node* nd, long long l, long long r) {
  if (nd->lazy != inf) nd->mn = nd->lazy;
  long long ss = nd->l;
  long long se = nd->r;
  if (ss > r || se < l) return inf;
  if (l <= ss && se <= r) return nd->mn;
  long long mid = (ss + se) / 2;
  if (nd->L == NULL) {
    nd->L = new node();
    nd->L->init(ss, mid, go(ss, mid));
  }
  if (nd->R == NULL) {
    nd->R = new node();
    nd->R->init(mid + 1, se, go(mid + 1, se));
  }
  if (nd->lazy != inf) {
    nd->L->lazy = nd->lazy;
    nd->R->lazy = nd->lazy;
    nd->lazy = inf;
  }
  return min(query2(nd->L, l, r), query2(nd->R, l, r));
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (long long i = 0; i < n; i++) cin >> seg[i + n];
  for (long long i = n - 1; i >= 1; i--)
    seg[i] = min(seg[i << 1], seg[i << 1 ^ 1]);
  root = new node();
  root->init(0, (n * k) - 1, seg[1]);
  long long q;
  cin >> q;
  long long t, l, r, x;
  while (q--) {
    cin >> t >> l >> r;
    l--;
    r--;
    if (t == 1) {
      cin >> x;
      upd(root, l, r, x);
    } else
      cout << query2(root, l, r) << '\n';
  }
}

```