#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <set>
#include <map>
#include <complex>
#include <iostream>
#include <time.h>
#include <math.h>
#include <stack>
#include <stdlib.h>
#include <memory.h>
#include <bitset>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;

const int MaxN = 1e5 + 10;
const int MaxQ = 1e5 + 10;
const int MaxL = 20;
const int INF = 1e9 + 7;

struct CartesianTreeNode {
  int x, l, r;
  int size;
} ct[2 * MaxL * MaxL * MaxN];

struct SegmentTreeNode {
  int l, r;
  int ct;
} st[2 * MaxL * MaxN];

int ctptr, stptr;
int a[MaxN], n, q;
int stroots[MaxN];

int rnd(int l, int r) {
  return (1LL * RAND_MAX * rand() + rand()) % (r - l + 1) + l;
}

int ctree(int x, int l = 0, int r = 0) {
  int ret = ++ctptr;
  ct[ret].l = l;
  ct[ret].r = r;
  ct[ret].x = x;
  ct[ret].size = 1 + ct[ct[ret].l].size + ct[ct[ret].r].size;
  return ret;
}

int merge(int l, int r) {
  if (l == 0 || r == 0) {
    return l ? l : r;
  }
  int ret = ++ctptr;
  if (rnd(0, ct[l].size + ct[r].size - 1) < ct[l].size) {
    ct[ret].r = merge(ct[l].r, r);
    ct[ret].l = ct[l].l;
    ct[ret].x = ct[l].x;
    ct[ret].size = ct[l].size + ct[r].size;
  } else {
    ct[ret].l = merge(l, ct[r].l);
    ct[ret].r = ct[r].r;
    ct[ret].x = ct[r].x;
    ct[ret].size = ct[l].size + ct[r].size;
  }
  return ret;
}

pair < int, int > split(int t, int x) {
  if (t == 0) {
    return make_pair(0, 0);
  }
  if (ct[t].x <= x) {
    pair < int, int > rsplit = split(ct[t].r, x);
    return make_pair(ctree(ct[t].x, ct[t].l, rsplit.first), rsplit.second);
  }
  pair < int, int > lsplit = split(ct[t].l, x);
  return make_pair(lsplit.first, ctree(ct[t].x, lsplit.second, ct[t].r));
}

int Erase(int root, int key) {
  pair < int, int > u = split(root, key - 1);
  pair < int, int > v = split(u.second, key);
  return merge(u.first, v.second);
}

int Erase(int v, int l, int r, int pos, int val) {
  int ret = ++stptr;
  st[ret].ct = Erase(st[v].ct, val);
  if (l != r) {
    int m = (l + r) / 2;
    if (pos <= m) {
      st[ret].l = Erase(st[v].l, l, m, pos, val);
      st[ret].r = st[v].r;
    } else {
      st[ret].r = Erase(st[v].r, m + 1, r, pos, val);
      st[ret].l = st[v].l;
    }
  }
  return ret;
}

int Insert(int root, int key) {
  pair < int, int > u = split(root, key - 1);
  pair < int, int > v = split(u.second, key);
  return merge(u.first, merge(ctree(key), v.second));
}

int Insert(int v, int l, int r, int pos, int val) {
  int ret = ++stptr;
  st[ret].ct = Insert(st[v].ct, val);
  if (l != r) {
    int m = (l + r) / 2;
    if (pos <= m) {
      st[ret].l = Insert(st[v].l, l, m, pos, val);
      st[ret].r = st[v].r;
    } else {
      st[ret].r = Insert(st[v].r, m + 1, r, pos, val);
      st[ret].l = st[v].l;
    }
  }
  return ret;
}

int Solve(int v, int l, int r, int qr, int qk) {
  pair < int, int > f = split(st[v].ct, qr);
  if (ct[f.first].size < qk) {
    return -1;
  }
  while (l != r) {
    int m = (l + r) / 2;
    pair < int, int > f = split(st[st[v].l].ct, qr);
    if (ct[f.first].size < qk) {
      qk -= ct[f.first].size;
      l = m + 1;
      v = st[v].r;
    } else {
      r = m;
      v = st[v].l;
    }
  }
  return l;
}

int main() {
//  freopen("input.txt", "r", stdin);
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  vector < int > b;
  for (int i = 0; i < n; ++i) {
    b.push_back(a[i]);
  }
  sort(b.begin(), b.end());
  b.resize(unique(b.begin(), b.end()) - b.begin());
  for (int i = 0; i < n; ++i) {
    a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
  }
  vector < int > c(b.size(), INF);
  stroots[n] = 0;
  for (int i = n - 1; i >= 0; --i) {
    stroots[i] = stroots[i + 1];
    if (c[a[i]] != INF) {
      stroots[i] = Erase(stroots[i], 0, (int)b.size() - 1, a[i], c[a[i]]);
    }
    c[a[i]] = i;
    stroots[i] = Insert(stroots[i], 0, (int)b.size() - 1, a[i], c[a[i]]);
  }
  int octptr = ctptr;
  for (int i = 0, res = 0; i < q; ++i) {
    int l, r, k;
    int ai, bi, ci, di;
    scanf("%d%d%d%d%d", &ai, &bi, &ci, &di, &k);
    l = (1LL * ai * max(res, 0) + bi) % n + 1;
    r = (1LL * ci * max(res, 0) + di) % n + 1;
    if (l > r) {
      swap(l, r);
    }
    l--;
    r--;
    res = Solve(stroots[l], 0, (int)b.size() - 1, r, k);
    if (res != -1) {
      res = b[res];
    }
    printf("%d\n", res);
    while (ctptr > octptr) {
      ct[ctptr].x = 0;
      ct[ctptr].l = 0;
      ct[ctptr].r = 0;
      ct[ctptr].size = 0;
      ctptr--;
    }
  }
  return 0;
}