Given a sequence $A_1, A_2, \ldots, A_N$ of length $N$. Write a program to process the following queries:

• l r k: Let $S$ be the set (without duplicates) consisting of the $l$-th through $r$-th numbers in $A$, sorted in ascending order. Output the $k$-th smallest number in $S$. If the $k$-th smallest number does not exist, output $-1$.

The sequence is indexed starting from $1$.

Input

The first line contains an integer $N$, the length of the sequence. ($1 \le N \le 100{,}000$)

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 10^9$)

The third line contains an integer $M$, the number of queries. ($1 \le M \le 100{,}000$)

The next $M$ lines each contain five integers $a_i, b_i, c_i, d_i, k_i$, used to construct the queries. ($0 \le a_i, b_i, c_i, d_i \le N$, $1 \le k_i \le N$)

The $l_i$ and $r_i$ of each query are constructed as follows:

Let $ans_{i-1}$ be the answer to the $(i-1)$-th query (the answer to the $0$-th query is $ans_0 = 0$).

• $l_i = (a_i \times \max(ans_{i-1}, 0) + b_i) \bmod N + 1$
• $r_i = (c_i \times \max(ans_{i-1}, 0) + d_i) \bmod N + 1$

If $l_i > r_i$, swap $l_i$ and $r_i$.

Output

For each query, output one line in order containing the answer.

Examples

Input 1

4
3 2 1 2
4
0 1 0 3 2
2 0 0 3 4
1 2 1 3 2
2 0 0 3 3

Output 1

2
-1
2
3

Input 2

10
9 10 6 3 8 4 9 6 4 10
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 2

6
9
10
4
6
3
10
4
6
4