#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007LL;
long long base = 37;
long long large = 1000000000000000000LL;
vector<int> setv;
vector<int> b;
vector<int> mini;
vector<int> lc, rc;
vector<int> root;
int sz = 1;
int n, k;
void build(int o, int l, int r) {
  if (l == r) {
    setv[o] = b[l];
    mini[o] = b[l];
  } else {
    int m = (l + r) / 2;
    lc[o] = sz++;
    build(lc[o], l, m);
    rc[o] = sz++;
    build(rc[o], m + 1, r);
    mini[o] = min(mini[lc[o]], mini[rc[o]]);
  }
}
int maintain(int o, int l, int r, int as) {
  int t = sz++;
  lc[t] = lc[o];
  rc[t] = rc[o];
  if (l == r || setv[o] != -1 || as != -1) {
    setv[t] = setv[o];
    mini[t] = setv[o];
    if (as != -1) {
      setv[t] = as;
      mini[t] = as;
    }
  } else {
    mini[t] = min(mini[lc[t]], mini[rc[t]]);
  }
  return t;
}
int ul, ur, uv;
int update(int o, int l, int r, int as) {
  int t = sz++;
  lc[t] = lc[o];
  rc[t] = rc[o];
  if (ul <= l && ur >= r) {
    setv[t] = uv;
    mini[t] = setv[t];
  } else {
    int m = (l + r) / 2;
    int sv = -1;
    if (setv[o] != -1) {
      sv = setv[o];
    }
    if (as != -1) sv = as;
    if (ul <= m) {
      lc[t] = update(lc[t], l, m, sv);
    } else {
      lc[t] = maintain(lc[t], l, m, sv);
    }
    if (ur > m) {
      rc[t] = update(rc[t], m + 1, r, sv);
    } else {
      rc[t] = maintain(rc[t], m + 1, r, sv);
    }
    mini[t] = min(mini[lc[t]], mini[rc[t]]);
  }
  return t;
}
int re, ql, qr;
void query(int o, int l, int r) {
  if (setv[o] > 0) {
    re = min(re, mini[o]);
  } else {
    if (ql <= l && qr >= r) {
      re = min(re, mini[o]);
    } else {
      int m = (l + r) / 2;
      if (ql <= m) query(lc[o], l, m);
      if (qr > m) query(rc[o], m + 1, r);
    }
  }
}
int ul2, ur2, uv2;
vector<int> setv2;
vector<int> mini2;
void maintain2(int o, int l, int r) {
  if (setv2[o] != -1) {
    mini2[o] = setv2[o];
  } else {
    if (l == r)
      mini2[o] = mini[root[l]];
    else
      mini2[o] = min(mini2[o * 2], mini2[o * 2 + 1]);
  }
}
void build2(int o, int l, int r) {
  if (l == r) {
    mini2[o] = mini[root[l]];
  } else {
    int m = (l + r) / 2;
    build2(o * 2, l, m);
    build2(o * 2 + 1, m + 1, r);
    mini2[o] = min(mini2[o * 2], mini2[o * 2 + 1]);
  }
}
void update2(int o, int l, int r) {
  if (ul2 <= l && ur2 >= r) {
    setv2[o] = uv2;
    mini2[o] = uv2;
  } else {
    int m = (l + r) / 2;
    if (setv2[o] != -1) {
      setv2[o * 2] = setv2[o * 2 + 1] = setv2[o];
      setv2[o] = -1;
    }
    if (ul2 <= m) {
      update2(o * 2, l, m);
    } else {
      maintain2(o * 2, l, m);
    }
    if (ur2 > m)
      update2(o * 2 + 1, m + 1, r);
    else
      maintain2(o * 2 + 1, m + 1, r);
    maintain2(o, l, r);
  }
}
int up2;
void singleupdate2(int o, int l, int r) {
  if (l == r) {
    int tl, tr, tv;
    tl = ul;
    tr = ur;
    tv = uv;
    if (setv2[o] != -1) {
      ul = 0;
      ur = n - 1;
      uv = setv2[o];
      root[l] = update(root[l], 0, n - 1, -1);
      setv2[o] = -1;
    }
    ul = tl;
    ur = tr;
    uv = tv;
    root[l] = update(root[l], 0, n - 1, -1);
    mini2[o] = mini[root[l]];
  } else {
    int m = (l + r) / 2;
    if (setv2[o] != -1) {
      setv2[o * 2] = setv2[o * 2 + 1] = setv2[o];
      setv2[o] = -1;
    }
    if (up2 <= m) {
      singleupdate2(o * 2, l, m);
    } else {
      maintain2(o * 2, l, m);
    }
    if (up2 > m)
      singleupdate2(o * 2 + 1, m + 1, r);
    else
      maintain2(o * 2 + 1, m + 1, r);
    maintain2(o, l, r);
  }
}
int ql2, qr2, re2;
void query2(int o, int l, int r) {
  if (setv2[o] != -1) {
    re2 = min(re2, setv2[o]);
  } else {
    if (ql2 <= l && qr2 >= r) {
      re2 = min(re2, mini2[o]);
    } else {
      int m = (l + r) / 2;
      if (ql2 <= m) query2(o * 2, l, m);
      if (qr2 > m) query2(o * 2 + 1, m + 1, r);
    }
  }
}
int qp2;
void singlequery2(int o, int l, int r) {
  if (setv2[o] != -1) {
    re2 = min(re2, setv2[o]);
  } else {
    if (l == r) {
      re = 1000000000;
      query(root[l], 0, n - 1);
      re2 = min(re2, re);
    } else {
      int m = (l + r) / 2;
      if (qp2 <= m) singlequery2(o * 2, l, m);
      if (qp2 > m) singlequery2(o * 2 + 1, m + 1, r);
    }
  }
}
int main() {
  cin >> n >> k;
  b.assign(n, 0);
  for (int i = 0; i < n; i++) cin >> b[i];
  int q;
  cin >> q;
  setv.assign(4 * n + 10 + 80 * q, -1);
  lc = setv;
  rc = lc;
  mini = setv;
  root.assign(k, 0);
  build(0, 0, n - 1);
  setv2.assign(4 * k + 10, -1);
  mini2 = setv2;
  build2(1, 0, k - 1);
  while (q--) {
    int t;
    cin >> t;
    if (t == 2) {
      re = 1000000000;
      re2 = re;
      int ttl, ttr;
      cin >> ttl >> ttr;
      ttl--;
      ttr--;
      int tl = ttl / n;
      int tr = ttr / n;
      if (tl == tr) {
        qp2 = tl;
        ql = ttl % n;
        qr = ttr % n;
        singlequery2(1, 0, k - 1);
      } else {
        qp2 = tl;
        ql = ttl % n;
        qr = n - 1;
        singlequery2(1, 0, k - 1);
        qp2 = tr;
        ql = 0;
        qr = ttr % n;
        singlequery2(1, 0, k - 1);
        if (tl + 1 <= tr - 1) {
          ql2 = tl + 1;
          qr2 = tr - 1;
          query2(1, 0, k - 1);
        }
      }
      cout << re2 << endl;
    } else {
      int ttl, ttr, ttv;
      cin >> ttl >> ttr >> ttv;
      ttl--;
      ttr--;
      int tl = ttl / n;
      int tr = ttr / n;
      if (tl == tr) {
        ul = ttl % n;
        ur = ttr % n;
        uv = ttv;
        up2 = tl;
        singleupdate2(1, 0, k - 1);
      } else {
        up2 = tl;
        ul = ttl % n;
        ur = n - 1;
        uv = ttv;
        singleupdate2(1, 0, k - 1);
        up2 = tr;
        ul = 0;
        ur = ttr % n;
        uv = ttv;
        singleupdate2(1, 0, k - 1);
        if (tl + 1 <= tr - 1) {
          ul2 = tl + 1;
          ur2 = tr - 1;
          uv2 = ttv;
          update2(1, 0, k - 1);
        }
      }
    }
  }
  return 0;
}

### 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;
long long mod = 1000000007LL;
long long base = 37;
long long large = 1000000000000000000LL;
vector<int> setv;
vector<int> b;
vector<int> mini;
vector<int> lc, rc;
vector<int> root;
int sz = 1;
int n, k;
void build(int o, int l, int r) {
  if (l == r) {
    setv[o] = b[l];
    mini[o] = b[l];
  } else {
    int m = (l + r) / 2;
    lc[o] = sz++;
    build(lc[o], l, m);
    rc[o] = sz++;
    build(rc[o], m + 1, r);
    mini[o] = min(mini[lc[o]], mini[rc[o]]);
  }
}
int maintain(int o, int l, int r, int as) {
  int t = sz++;
  lc[t] = lc[o];
  rc[t] = rc[o];
  if (l == r || setv[o] != -1 || as != -1) {
    setv[t] = setv[o];
    mini[t] = setv[o];
    if (as != -1) {
      setv[t] = as;
      mini[t] = as;
    }
  } else {
    mini[t] = min(mini[lc[t]], mini[rc[t]]);
  }
  return t;
}
int ul, ur, uv;
int update(int o, int l, int r, int as) {
  int t = sz++;
  lc[t] = lc[o];
  rc[t] = rc[o];
  if (ul <= l && ur >= r) {
    setv[t] = uv;
    mini[t] = setv[t];
  } else {
    int m = (l + r) / 2;
    int sv = -1;
    if (setv[o] != -1) {
      sv = setv[o];
    }
    if (as != -1) sv = as;
    if (ul <= m) {
      lc[t] = update(lc[t], l, m, sv);
    } else {
      lc[t] = maintain(lc[t], l, m, sv);
    }
    if (ur > m) {
      rc[t] = update(rc[t], m + 1, r, sv);
    } else {
      rc[t] = maintain(rc[t], m + 1, r, sv);
    }
    mini[t] = min(mini[lc[t]], mini[rc[t]]);
  }
  return t;
}
int re, ql, qr;
void query(int o, int l, int r) {
  if (setv[o] > 0) {
    re = min(re, mini[o]);
  } else {
    if (ql <= l && qr >= r) {
      re = min(re, mini[o]);
    } else {
      int m = (l + r) / 2;
      if (ql <= m) query(lc[o], l, m);
      if (qr > m) query(rc[o], m + 1, r);
    }
  }
}
int ul2, ur2, uv2;
vector<int> setv2;
vector<int> mini2;
void maintain2(int o, int l, int r) {
  if (setv2[o] != -1) {
    mini2[o] = setv2[o];
  } else {
    if (l == r)
      mini2[o] = mini[root[l]];
    else
      mini2[o] = min(mini2[o * 2], mini2[o * 2 + 1]);
  }
}
void build2(int o, int l, int r) {
  if (l == r) {
    mini2[o] = mini[root[l]];
  } else {
    int m = (l + r) / 2;
    build2(o * 2, l, m);
    build2(o * 2 + 1, m + 1, r);
    mini2[o] = min(mini2[o * 2], mini2[o * 2 + 1]);
  }
}
void update2(int o, int l, int r) {
  if (ul2 <= l && ur2 >= r) {
    setv2[o] = uv2;
    mini2[o] = uv2;
  } else {
    int m = (l + r) / 2;
    if (setv2[o] != -1) {
      setv2[o * 2] = setv2[o * 2 + 1] = setv2[o];
      setv2[o] = -1;
    }
    if (ul2 <= m) {
      update2(o * 2, l, m);
    } else {
      maintain2(o * 2, l, m);
    }
    if (ur2 > m)
      update2(o * 2 + 1, m + 1, r);
    else
      maintain2(o * 2 + 1, m + 1, r);
    maintain2(o, l, r);
  }
}
int up2;
void singleupdate2(int o, int l, int r) {
  if (l == r) {
    int tl, tr, tv;
    tl = ul;
    tr = ur;
    tv = uv;
    if (setv2[o] != -1) {
      ul = 0;
      ur = n - 1;
      uv = setv2[o];
      root[l] = update(root[l], 0, n - 1, -1);
      setv2[o] = -1;
    }
    ul = tl;
    ur = tr;
    uv = tv;
    root[l] = update(root[l], 0, n - 1, -1);
    mini2[o] = mini[root[l]];
  } else {
    int m = (l + r) / 2;
    if (setv2[o] != -1) {
      setv2[o * 2] = setv2[o * 2 + 1] = setv2[o];
      setv2[o] = -1;
    }
    if (up2 <= m) {
      singleupdate2(o * 2, l, m);
    } else {
      maintain2(o * 2, l, m);
    }
    if (up2 > m)
      singleupdate2(o * 2 + 1, m + 1, r);
    else
      maintain2(o * 2 + 1, m + 1, r);
    maintain2(o, l, r);
  }
}
int ql2, qr2, re2;
void query2(int o, int l, int r) {
  if (setv2[o] != -1) {
    re2 = min(re2, setv2[o]);
  } else {
    if (ql2 <= l && qr2 >= r) {
      re2 = min(re2, mini2[o]);
    } else {
      int m = (l + r) / 2;
      if (ql2 <= m) query2(o * 2, l, m);
      if (qr2 > m) query2(o * 2 + 1, m + 1, r);
    }
  }
}
int qp2;
void singlequery2(int o, int l, int r) {
  if (setv2[o] != -1) {
    re2 = min(re2, setv2[o]);
  } else {
    if (l == r) {
      re = 1000000000;
      query(root[l], 0, n - 1);
      re2 = min(re2, re);
    } else {
      int m = (l + r) / 2;
      if (qp2 <= m) singlequery2(o * 2, l, m);
      if (qp2 > m) singlequery2(o * 2 + 1, m + 1, r);
    }
  }
}
int main() {
  cin >> n >> k;
  b.assign(n, 0);
  for (int i = 0; i < n; i++) cin >> b[i];
  int q;
  cin >> q;
  setv.assign(4 * n + 10 + 80 * q, -1);
  lc = setv;
  rc = lc;
  mini = setv;
  root.assign(k, 0);
  build(0, 0, n - 1);
  setv2.assign(4 * k + 10, -1);
  mini2 = setv2;
  build2(1, 0, k - 1);
  while (q--) {
    int t;
    cin >> t;
    if (t == 2) {
      re = 1000000000;
      re2 = re;
      int ttl, ttr;
      cin >> ttl >> ttr;
      ttl--;
      ttr--;
      int tl = ttl / n;
      int tr = ttr / n;
      if (tl == tr) {
        qp2 = tl;
        ql = ttl % n;
        qr = ttr % n;
        singlequery2(1, 0, k - 1);
      } else {
        qp2 = tl;
        ql = ttl % n;
        qr = n - 1;
        singlequery2(1, 0, k - 1);
        qp2 = tr;
        ql = 0;
        qr = ttr % n;
        singlequery2(1, 0, k - 1);
        if (tl + 1 <= tr - 1) {
          ql2 = tl + 1;
          qr2 = tr - 1;
          query2(1, 0, k - 1);
        }
      }
      cout << re2 << endl;
    } else {
      int ttl, ttr, ttv;
      cin >> ttl >> ttr >> ttv;
      ttl--;
      ttr--;
      int tl = ttl / n;
      int tr = ttr / n;
      if (tl == tr) {
        ul = ttl % n;
        ur = ttr % n;
        uv = ttv;
        up2 = tl;
        singleupdate2(1, 0, k - 1);
      } else {
        up2 = tl;
        ul = ttl % n;
        ur = n - 1;
        uv = ttv;
        singleupdate2(1, 0, k - 1);
        up2 = tr;
        ul = 0;
        ur = ttr % n;
        uv = ttv;
        singleupdate2(1, 0, k - 1);
        if (tl + 1 <= tr - 1) {
          ul2 = tl + 1;
          ur2 = tr - 1;
          uv2 = ttv;
          update2(1, 0, k - 1);
        }
      }
    }
  }
  return 0;
}

```