#include <bits/stdc++.h>
template <typename T>
T max(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
T min(T a, T b) {
  return a > b ? b : a;
}
template <typename T>
void swap(T &a, T &b) {
  T c = a;
  a = b;
  b = c;
}
int n, k, q, initData[100010];
int li, ri, x;
class STtable {
 public:
  int data[100010][21];
  void init() {
    for (int i = 1; i <= n; ++i) data[i][0] = initData[i];
    for (int i = 1; i <= 20; ++i) {
      for (int j = 1; j + (1 << i) <= n + 1; ++j) {
        data[j][i] = min(data[j][i - 1], data[j + (1 << (i - 1))][i - 1]);
      }
    }
  }
  long long query(int l, int r) {
    int k = (int)(log(double(r - l + 1)) / log(2.0));
    return min(data[l][k], data[r - (1 << k) + 1][k]);
  }
};
STtable myStable;
class SegmentTree {
 public:
  struct node {
    long long data, lazy;
    node *ls, *rs;
  } tree[5000001], *root;
  int nodeCnt;
  int cal(int x) {
    int res = x % n;
    return res ? res : n;
  }
  node *new_node(int l, int r) {
    node *res = &tree[nodeCnt];
    nodeCnt++;
    if ((l - 1) / n == (r - 1) / n) {
      res->data = myStable.query(cal(l), cal(r));
    } else if ((r - 1) / n == ((l - 1) / n) + 1) {
      res->data = min(myStable.query(1, cal(r)), myStable.query(cal(l), n));
    } else {
      res->data = myStable.query(1, n);
    }
    res->lazy = 0;
    res->ls = res->rs = NULL;
    return res;
  }
  void init() {
    nodeCnt = 0;
    root = new_node(1, n * k);
  }
  void pushtag(node *i, int val) {
    i->data = (long long)val;
    i->lazy = (long long)val;
  }
  void release(node *i, int l, int r) {
    if (i->lazy) {
      int mid = (l + r) >> 1;
      if (i->ls == NULL) i->ls = new_node(l, mid);
      if (i->rs == NULL) i->rs = new_node(mid + 1, r);
      pushtag(i->ls, i->lazy);
      pushtag(i->rs, i->lazy);
      i->lazy = 0;
    }
  }
  void update(node *i, int L, int R, int l, int r, int val) {
    if (l <= L and R <= r) {
      pushtag(i, val);
    } else {
      release(i, L, R);
      int mid = (L + R) >> 1;
      if (l <= mid) {
        if (i->ls == NULL) i->ls = new_node(L, mid);
        update(i->ls, L, mid, l, r, val);
      }
      if (r > mid) {
        if (i->rs == NULL) i->rs = new_node(mid + 1, R);
        update(i->rs, mid + 1, R, l, r, val);
      }
      long long res = 1ll << 40;
      if (i->ls)
        res = min(res, i->ls->data);
      else {
        if ((L - 1) / n == (mid - 1) / n) {
          res = min(res, myStable.query(cal(L), cal(mid)));
        } else if ((mid - 1) / n == ((L - 1) / n) + 1) {
          res = min(
              res, min(myStable.query(1, cal(mid)), myStable.query(cal(L), n)));
        } else {
          res = min(res, myStable.query(1, n));
        }
      }
      if (i->rs)
        res = min(res, i->rs->data);
      else {
        if ((mid) / n == (R - 1) / n) {
          res = min(res, myStable.query(cal(mid + 1), cal(R)));
        } else if ((R - 1) / n == ((mid) / n) + 1) {
          res = min(res, min(myStable.query(1, cal(R)),
                             myStable.query(cal(mid + 1), n)));
        } else {
          res = min(res, myStable.query(1, n));
        }
      }
      i->data = res;
    }
  }
  long long query(node *i, int L, int R, int l, int r) {
    if (l <= L and R <= r) {
      return i->data;
    } else {
      release(i, L, R);
      int mid = (L + R) >> 1;
      long long res = 1ll << 40;
      if (l <= mid and i->ls) res = min(res, query(i->ls, L, mid, l, r));
      if (l <= mid and i->ls == NULL) {
        int lm = max(L, l);
        int m = min(mid, r);
        if ((lm - 1) / n == (m - 1) / n) {
          res = min(res, myStable.query(cal(lm), cal(m)));
        } else if ((m - 1) / n == ((lm - 1) / n) + 1) {
          res = min(res,
                    min(myStable.query(1, cal(m)), myStable.query(cal(lm), n)));
        } else {
          res = min(res, myStable.query(1, n));
        }
      }
      if (r > mid and i->rs) res = min(res, query(i->rs, mid + 1, R, l, r));
      if (r > mid and i->rs == NULL) {
        int rm = min(R, r);
        int m = max(l, mid + 1);
        if ((m - 1) / n == (rm - 1) / n) {
          res = min(res, myStable.query(cal(m), cal(rm)));
        } else if ((rm - 1) / n == ((m - 1) / n) + 1) {
          res = min(res,
                    min(myStable.query(1, cal(rm)), myStable.query(cal(m), n)));
        } else {
          res = min(res, myStable.query(1, n));
        }
      }
      return res;
    }
  }
};
SegmentTree mysegtree;
int main() {
  scanf("%d", &n);
  scanf("%d", &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &initData[i]);
  myStable.init();
  mysegtree.init();
  scanf("%d", &q);
  int opt;
  for (int i = 1; i <= q; ++i) {
    scanf("%d", &opt);
    if (opt == 1) {
      scanf("%d", &li);
      scanf("%d", &ri);
      scanf("%d", &x);
      mysegtree.update(mysegtree.root, 1, n * k, li, ri, x);
    } else {
      scanf("%d", &li);
      scanf("%d", &ri);
      printf("%lld\n", mysegtree.query(mysegtree.root, 1, n * k, li, ri));
    }
  }
  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>
template <typename T>
T max(T a, T b) {
  return a > b ? a : b;
}
template <typename T>
T min(T a, T b) {
  return a > b ? b : a;
}
template <typename T>
void swap(T &a, T &b) {
  T c = a;
  a = b;
  b = c;
}
int n, k, q, initData[100010];
int li, ri, x;
class STtable {
 public:
  int data[100010][21];
  void init() {
    for (int i = 1; i <= n; ++i) data[i][0] = initData[i];
    for (int i = 1; i <= 20; ++i) {
      for (int j = 1; j + (1 << i) <= n + 1; ++j) {
        data[j][i] = min(data[j][i - 1], data[j + (1 << (i - 1))][i - 1]);
      }
    }
  }
  long long query(int l, int r) {
    int k = (int)(log(double(r - l + 1)) / log(2.0));
    return min(data[l][k], data[r - (1 << k) + 1][k]);
  }
};
STtable myStable;
class SegmentTree {
 public:
  struct node {
    long long data, lazy;
    node *ls, *rs;
  } tree[5000001], *root;
  int nodeCnt;
  int cal(int x) {
    int res = x % n;
    return res ? res : n;
  }
  node *new_node(int l, int r) {
    node *res = &tree[nodeCnt];
    nodeCnt++;
    if ((l - 1) / n == (r - 1) / n) {
      res->data = myStable.query(cal(l), cal(r));
    } else if ((r - 1) / n == ((l - 1) / n) + 1) {
      res->data = min(myStable.query(1, cal(r)), myStable.query(cal(l), n));
    } else {
      res->data = myStable.query(1, n);
    }
    res->lazy = 0;
    res->ls = res->rs = NULL;
    return res;
  }
  void init() {
    nodeCnt = 0;
    root = new_node(1, n * k);
  }
  void pushtag(node *i, int val) {
    i->data = (long long)val;
    i->lazy = (long long)val;
  }
  void release(node *i, int l, int r) {
    if (i->lazy) {
      int mid = (l + r) >> 1;
      if (i->ls == NULL) i->ls = new_node(l, mid);
      if (i->rs == NULL) i->rs = new_node(mid + 1, r);
      pushtag(i->ls, i->lazy);
      pushtag(i->rs, i->lazy);
      i->lazy = 0;
    }
  }
  void update(node *i, int L, int R, int l, int r, int val) {
    if (l <= L and R <= r) {
      pushtag(i, val);
    } else {
      release(i, L, R);
      int mid = (L + R) >> 1;
      if (l <= mid) {
        if (i->ls == NULL) i->ls = new_node(L, mid);
        update(i->ls, L, mid, l, r, val);
      }
      if (r > mid) {
        if (i->rs == NULL) i->rs = new_node(mid + 1, R);
        update(i->rs, mid + 1, R, l, r, val);
      }
      long long res = 1ll << 40;
      if (i->ls)
        res = min(res, i->ls->data);
      else {
        if ((L - 1) / n == (mid - 1) / n) {
          res = min(res, myStable.query(cal(L), cal(mid)));
        } else if ((mid - 1) / n == ((L - 1) / n) + 1) {
          res = min(
              res, min(myStable.query(1, cal(mid)), myStable.query(cal(L), n)));
        } else {
          res = min(res, myStable.query(1, n));
        }
      }
      if (i->rs)
        res = min(res, i->rs->data);
      else {
        if ((mid) / n == (R - 1) / n) {
          res = min(res, myStable.query(cal(mid + 1), cal(R)));
        } else if ((R - 1) / n == ((mid) / n) + 1) {
          res = min(res, min(myStable.query(1, cal(R)),
                             myStable.query(cal(mid + 1), n)));
        } else {
          res = min(res, myStable.query(1, n));
        }
      }
      i->data = res;
    }
  }
  long long query(node *i, int L, int R, int l, int r) {
    if (l <= L and R <= r) {
      return i->data;
    } else {
      release(i, L, R);
      int mid = (L + R) >> 1;
      long long res = 1ll << 40;
      if (l <= mid and i->ls) res = min(res, query(i->ls, L, mid, l, r));
      if (l <= mid and i->ls == NULL) {
        int lm = max(L, l);
        int m = min(mid, r);
        if ((lm - 1) / n == (m - 1) / n) {
          res = min(res, myStable.query(cal(lm), cal(m)));
        } else if ((m - 1) / n == ((lm - 1) / n) + 1) {
          res = min(res,
                    min(myStable.query(1, cal(m)), myStable.query(cal(lm), n)));
        } else {
          res = min(res, myStable.query(1, n));
        }
      }
      if (r > mid and i->rs) res = min(res, query(i->rs, mid + 1, R, l, r));
      if (r > mid and i->rs == NULL) {
        int rm = min(R, r);
        int m = max(l, mid + 1);
        if ((m - 1) / n == (rm - 1) / n) {
          res = min(res, myStable.query(cal(m), cal(rm)));
        } else if ((rm - 1) / n == ((m - 1) / n) + 1) {
          res = min(res,
                    min(myStable.query(1, cal(rm)), myStable.query(cal(m), n)));
        } else {
          res = min(res, myStable.query(1, n));
        }
      }
      return res;
    }
  }
};
SegmentTree mysegtree;
int main() {
  scanf("%d", &n);
  scanf("%d", &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &initData[i]);
  myStable.init();
  mysegtree.init();
  scanf("%d", &q);
  int opt;
  for (int i = 1; i <= q; ++i) {
    scanf("%d", &opt);
    if (opt == 1) {
      scanf("%d", &li);
      scanf("%d", &ri);
      scanf("%d", &x);
      mysegtree.update(mysegtree.root, 1, n * k, li, ri, x);
    } else {
      scanf("%d", &li);
      scanf("%d", &ri);
      printf("%lld\n", mysegtree.query(mysegtree.root, 1, n * k, li, ri));
    }
  }
  return 0;
}

```