#include <bits/stdc++.h>
using namespace std;
struct node {
  int val, lazy, child;
  node() {
    val = child = 0;
    lazy = 1e9 + 7;
  }
  node(int vval, int llazy, int cchild) {
    val = vval;
    lazy = llazy;
    child = cchild;
  }
};
int N, K, Q;
int w, x, y, z;
int arr[100100];
int stree[4 * 100100];
vector<node> tree;
int counter, c1, c2;
int squery(int n, int l, int r, int ql, int qr) {
  if (l > qr || r < ql) {
    return 1e9 + 7;
  } else if (ql <= l && r <= qr) {
    return stree[n];
  } else {
    return min(squery(2 * n, l, (l + r) / 2, ql, qr),
               squery(2 * n + 1, (l + r) / 2 + 1, r, ql, qr));
  }
}
void propogate(int n) {
  tree[tree[n].child].val = tree[n].lazy;
  tree[tree[n].child + 1].val = tree[n].lazy;
  tree[tree[n].child].lazy = tree[n].lazy;
  tree[tree[n].child + 1].lazy = tree[n].lazy;
  tree[n].lazy = 1e9 + 7;
}
void update(int n, int l, int r, int ql, int qr, int q) {
  if (tree[n].child == 0) {
    tree[n].child = counter;
    counter += 2;
    tree.push_back(node());
    tree.push_back(node());
  }
  if (tree[n].lazy != 1e9 + 7 && l != r) {
    propogate(n);
  }
  if (l > qr || r < ql) {
    if (tree[n].val == 0) {
      if ((r - l + 1) >= N) {
        tree[n].val = squery(1, 1, N, 1, N);
      } else {
        c1 = l % N;
        c2 = r % N;
        if (c1 == 0) {
          c1 = N;
        }
        if (c2 == 0) {
          c2 = N;
        }
        if (c1 <= c2) {
          tree[n].val = squery(1, 1, N, c1, c2);
        } else {
          tree[n].val = min(squery(1, 1, N, c1, N), squery(1, 1, N, 1, c2));
        }
      }
    }
    return;
  } else if (ql <= l && r <= qr) {
    tree[n].val = tree[n].lazy = q;
    return;
  } else {
    update(tree[n].child, l, (l + r) / 2, ql, qr, q);
    update(tree[n].child + 1, (l + r) / 2 + 1, r, ql, qr, q);
    tree[n].val = min(tree[tree[n].child].val, tree[tree[n].child + 1].val);
  }
}
int query(int n, int l, int r, int ql, int qr) {
  if (tree[n].child == 0) {
    tree[n].child = counter;
    counter += 2;
    tree.push_back(node());
    tree.push_back(node());
  }
  if (tree[n].val == 0) {
    if ((r - l + 1) >= N) {
      tree[n].val = squery(1, 1, N, 1, N);
    } else {
      c1 = l % N;
      c2 = r % N;
      if (c1 == 0) {
        c1 = N;
      }
      if (c2 == 0) {
        c2 = N;
      }
      if (c1 <= c2) {
        tree[n].val = squery(1, 1, N, c1, c2);
      } else {
        tree[n].val = min(squery(1, 1, N, c1, N), squery(1, 1, N, 1, c2));
      }
    }
  }
  if (tree[n].lazy != 1e9 + 7 && l != r) {
    propogate(n);
  }
  if (l > qr || r < ql) {
    return 1e9 + 7;
  } else if (ql <= l && r <= qr) {
    return tree[n].val;
  } else {
    return min(query(tree[n].child, l, (l + r) / 2, ql, qr),
               query(tree[n].child + 1, (l + r) / 2 + 1, r, ql, qr));
  }
}
void buildtree(int n, int l, int r) {
  if (l == r) {
    stree[n] = arr[l];
    return;
  } else {
    buildtree(2 * n, l, (l + r) / 2);
    buildtree(2 * n + 1, (l + r) / 2 + 1, r);
    stree[n] = min(stree[2 * n], stree[2 * n + 1]);
  }
}
int main() {
  cin >> N >> K;
  for (int i = 1; i <= N; i++) {
    cin >> arr[i];
  }
  buildtree(1, 1, N);
  counter = 1;
  tree.push_back(node());
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    cin >> w;
    if (w == 1) {
      cin >> x >> y >> z;
      update(0, 1, N * K, x, y, z);
    } else {
      cin >> x >> y;
      cout << query(0, 1, N * K, x, y) << endl;
    }
  }
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
struct node {
  int val, lazy, child;
  node() {
    val = child = 0;
    lazy = 1e9 + 7;
  }
  node(int vval, int llazy, int cchild) {
    val = vval;
    lazy = llazy;
    child = cchild;
  }
};
int N, K, Q;
int w, x, y, z;
int arr[100100];
int stree[4 * 100100];
vector<node> tree;
int counter, c1, c2;
int squery(int n, int l, int r, int ql, int qr) {
  if (l > qr || r < ql) {
    return 1e9 + 7;
  } else if (ql <= l && r <= qr) {
    return stree[n];
  } else {
    return min(squery(2 * n, l, (l + r) / 2, ql, qr),
               squery(2 * n + 1, (l + r) / 2 + 1, r, ql, qr));
  }
}
void propogate(int n) {
  tree[tree[n].child].val = tree[n].lazy;
  tree[tree[n].child + 1].val = tree[n].lazy;
  tree[tree[n].child].lazy = tree[n].lazy;
  tree[tree[n].child + 1].lazy = tree[n].lazy;
  tree[n].lazy = 1e9 + 7;
}
void update(int n, int l, int r, int ql, int qr, int q) {
  if (tree[n].child == 0) {
    tree[n].child = counter;
    counter += 2;
    tree.push_back(node());
    tree.push_back(node());
  }
  if (tree[n].lazy != 1e9 + 7 && l != r) {
    propogate(n);
  }
  if (l > qr || r < ql) {
    if (tree[n].val == 0) {
      if ((r - l + 1) >= N) {
        tree[n].val = squery(1, 1, N, 1, N);
      } else {
        c1 = l % N;
        c2 = r % N;
        if (c1 == 0) {
          c1 = N;
        }
        if (c2 == 0) {
          c2 = N;
        }
        if (c1 <= c2) {
          tree[n].val = squery(1, 1, N, c1, c2);
        } else {
          tree[n].val = min(squery(1, 1, N, c1, N), squery(1, 1, N, 1, c2));
        }
      }
    }
    return;
  } else if (ql <= l && r <= qr) {
    tree[n].val = tree[n].lazy = q;
    return;
  } else {
    update(tree[n].child, l, (l + r) / 2, ql, qr, q);
    update(tree[n].child + 1, (l + r) / 2 + 1, r, ql, qr, q);
    tree[n].val = min(tree[tree[n].child].val, tree[tree[n].child + 1].val);
  }
}
int query(int n, int l, int r, int ql, int qr) {
  if (tree[n].child == 0) {
    tree[n].child = counter;
    counter += 2;
    tree.push_back(node());
    tree.push_back(node());
  }
  if (tree[n].val == 0) {
    if ((r - l + 1) >= N) {
      tree[n].val = squery(1, 1, N, 1, N);
    } else {
      c1 = l % N;
      c2 = r % N;
      if (c1 == 0) {
        c1 = N;
      }
      if (c2 == 0) {
        c2 = N;
      }
      if (c1 <= c2) {
        tree[n].val = squery(1, 1, N, c1, c2);
      } else {
        tree[n].val = min(squery(1, 1, N, c1, N), squery(1, 1, N, 1, c2));
      }
    }
  }
  if (tree[n].lazy != 1e9 + 7 && l != r) {
    propogate(n);
  }
  if (l > qr || r < ql) {
    return 1e9 + 7;
  } else if (ql <= l && r <= qr) {
    return tree[n].val;
  } else {
    return min(query(tree[n].child, l, (l + r) / 2, ql, qr),
               query(tree[n].child + 1, (l + r) / 2 + 1, r, ql, qr));
  }
}
void buildtree(int n, int l, int r) {
  if (l == r) {
    stree[n] = arr[l];
    return;
  } else {
    buildtree(2 * n, l, (l + r) / 2);
    buildtree(2 * n + 1, (l + r) / 2 + 1, r);
    stree[n] = min(stree[2 * n], stree[2 * n + 1]);
  }
}
int main() {
  cin >> N >> K;
  for (int i = 1; i <= N; i++) {
    cin >> arr[i];
  }
  buildtree(1, 1, N);
  counter = 1;
  tree.push_back(node());
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    cin >> w;
    if (w == 1) {
      cin >> x >> y >> z;
      update(0, 1, N * K, x, y, z);
    } else {
      cin >> x >> y;
      cout << query(0, 1, N * K, x, y) << endl;
    }
  }
}

```