#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define ll long long
#define N 100111

// functional 1d tree
struct Segtree;
Segtree *segtree_combine(Segtree *l, Segtree *r);
struct Segtree {
    int i, j, c;
    Segtree *l, *r;
    Segtree(int i, int j, int c, Segtree *l = NULL, Segtree *r = NULL): i(i), j(j), c(c), l(l), r(r) {}

    Segtree *add_value(int v) {
        if (i <= v && v < j) {
            if (l) {
                return segtree_combine(l->add_value(v), r->add_value(v));
            } else {
                return new Segtree(i, j, c+1);
            }
        } else {
            return this;
        }
    }

    int query(int v) {
        if (j <= v) {
            return c;
        } else if (v <= i) {
            return 0;
        } else {
            return l->query(v) + r->query(v);
        }
    }
};

Segtree *segtree_combine(Segtree *l, Segtree *r) {
    return new Segtree(l->i, r->j, l->c + r->c, l, r);
}


Segtree *segtree_make(int i, int j) {
    if (j - i == 1) {
        return new Segtree(i, j, 0);
    } else {
        int k = i + j >> 1;
        return segtree_combine(segtree_make(i, k), segtree_make(k, j));
    }
}

// utilities for value compression
#define sort_uniq(vec) do {\
    sort((vec).begin(), (vec).end());\
    (vec).erase(unique((vec).begin(), (vec).end()), (vec).end());\
} while (0)
#define create_indexer(vec,index) do {\
    for (int i = 0; i < (vec).size(); i++) {\
        (index)[(vec)[i]] = i;\
    }\
} while (0)
int find_on(vector<int>& arr, int v) {
    int L = -1;
    int R = arr.size();
    while (R - L > 1) {
        int M = L + R >> 1;
        if (arr[M] < v) {
            L = M;
        } else {
            R = M;
        }
    }
    return R;
}

// 2d tree
typedef pair<int,int> pt;
struct Tree {
    vector<int> xs;
    vector<int> ys;
    vector<pt> points;
    Segtree **segtrees;

    void add_point(int x, int y) {
        points.push_back(make_pair(x,y));
        xs.push_back(x);
        ys.push_back(y);
    }

    void seal() {
        // stop further updates
        sort(points.begin(), points.end());
        sort_uniq(xs);
        sort_uniq(ys);
        map<int,int> x_index;
        map<int,int> y_index;
        create_indexer(xs,x_index);
        create_indexer(ys,y_index);
        segtrees = new Segtree*[xs.size()];
        Segtree *curr = segtree_make(0, ys.size());
        for (int i = 0; i < points.size(); i++) {
            int x = points[i].first;
            int y = points[i].second;
            curr = segtrees[x_index[x]] = curr->add_value(y_index[y]);
        }
    }

    int count(int l, int r) {
        int i = find_on(xs,l)-1;
        l = find_on(ys,l);
        r = find_on(ys,r);
        return segtrees[i]->query(r) - segtrees[i]->query(l);
    }
};


// 3d tree
struct Trees {
    int L, R;
    Tree *tree;
    Trees *l, *r;
    Trees (int L, int R): L(L), R(R) {
        tree = new Tree();
        if (R - L == 1) {
            l = r = NULL;
        } else {
            int M = L + R >> 1;
            l = new Trees(L, M);
            r = new Trees(M, R);
        }
    }

    void add_point(int x, int y, int z) {
        if (L <= x && x < R) {
            tree->add_point(y,z);
            if (l) {
                l->add_point(x,y,z);
                r->add_point(x,y,z);
            }
        }
    }

    void seal() {
        // stop further updates
        tree->seal();
        if (l) {
            l->seal();
            r->seal();
        }
    }

    int count(int L, int R) {
        return tree->count(L,R);
    }
};

int A[N];
int prev[N];
int main() {
    int n, q;
    scanf("%d%d", &n, &q);

    // compress values
    vector<int> values;
    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
        values.push_back(A[i]);
    }
    sort_uniq(values);
    map<int,int> index;
    create_indexer(values,index);
    for (int i = 0; i < n; i++) A[i] = index[A[i]];

    // construct a 3d tree
    fprintf(stderr, "adds\n");
    for (int i = 0; i < values.size(); i++) prev[i] = -1;
    Trees *trees = new Trees(0, values.size());
    for (int i = 0; i < n; i++) {
        trees->add_point(A[i], prev[A[i]], i);
        prev[A[i]] = i;
    }

    // prepare the tree from queries
    fprintf(stderr, "seal\n");
    trees->seal();
    
    fprintf(stderr, "queries\n");
    int ans = 0;
    while (q--) {
        int a, b, c, d, k;
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
        int l = (a*(ll)max(ans,0) + b)%n;
        int r = (c*(ll)max(ans,0) + d)%n + 1;
        int L = 0;
        int R = values.size();
        Trees *curr = trees;
        if (curr->count(l,r) < k) {
            ans = -1;
        } else {
            // binary search the answer using the tree's first dimension
            while (R - L > 1) {
                int M = L + R >> 1;
                int ct = curr->l->count(l,r);
                if (k > ct) {
                    k -= ct;
                    L = M;
                    curr = curr->r;
                } else {
                    R = M;
                    curr = curr->l;
                }
            }
            ans = L;
        }

        if (ans >= 0) ans = values[ans];
        printf("%d\n", ans);
    }
    fprintf(stderr, "done\n");
}