You are given an array A consisting of N positive integers. You have to answer Q queries on it of?

... following type:
•l r k : Let S denote the sorted (in increasing order) set of elements of array A with its indices between l and r. Note that set S contains distinct elements (i.e. no duplicates).
You need to find kth number in it. If such a number does not exist, i.e. the S has less than k elements, output -1.

All the indices in the queries are 1-based.

Input

The first line of input contains two space separated integers N and Q denoting the number of elements in A, and the number of queries, respectively.

The second line of input contains N space separated integers denoting the array A.

Each of the next Q lines contains five integers ai, bi, ci, di, ki.
We will generate li, ri indices for this query as follows:
Let answer for i - 1th query equal ansi - 1.
For 0th query ans0 = 0.
Define li = (ai x max(ansi - 1, 0) + bi) mod N + 1,
ri = (ci x max(ansi-1, 0) + di) mod N + 1.
If li > ri, then swap li and ri.

Output

For each query, output the answer to the query in a single line. If such a number doesn't exist, output -1.

Constraints
•1 ≤ N, Q ≤ 105
•1 ≤ Ai ≤ 109
•0 ≤ ai, bi, ci, di ≤ N
•1 ≤ li ≤ ri ≤ N
•1 ≤ ki ≤ N

Example
Input:
4 4
3 2 1 2
0 1 0 3 2
2 0 0 3 4
1 2 1 3 2
2 0 0 3 3

Output:
2
-1
2
3

Input:
10 10
9 10 6 3 8 4 9 6 4 10
0 2 0 9 3
1 9 1 3 3
1 8 1 0 3
1 2 1 7 2
1 6 1 2 3
1 4 1 3 1
1 6 1 6 1
1 4 1 8 1
1 9 1 3 3
1 9 1 2 1

Output:
6
9
10
4
6
3
10
4
6
4

Subtasks
•Subtask #1 (10 points) : Q x N ≤ 107
•Subtask #2 (20 points) : ki = 1
•Subtask #3 (30 points) : ai = 0, ci = 0
•Subtask #4 (40 points) : Original constraints

Explanation

Example #1:

Query 1. Sorted set of elements : {1, 2}. Second number in this is 2.

Query 2. Sorted set of elements : {1, 2, 3}. Fourth number doesn't exist, hence answer is -1.

Query 3. Sorted set of elements : {1, 2}. Second number in this set is 2.

Query 4. Sorted set of elements : {1, 2, 3}. Third number in this set is 3.

Author: mgch
Tester: kevinsogo
Date Added: 23-08-2015
Time Limit: 6 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC