Étant donné une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$. Écrivez un programme pour traiter les requêtes suivantes :

• l r k : Soit $S$ l'ensemble (sans doublons) constitué des numéros du $l$-ième au $r$-ième dans $A$, triés dans l'ordre croissant. Affichez le $k$-ième plus petit nombre de $S$. Si le $k$-ième plus petit nombre n'existe pas, affichez $-1$.

La séquence est indexée à partir de $1$.

Entrée

La première ligne contient un entier $N$, la longueur de la séquence. ($1 \le N \le 100\,000$)

La deuxième ligne contient $N$ entiers $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 10^9$)

La troisième ligne contient un entier $M$, le nombre de requêtes. ($1 \le M \le 100\,000$)

Les $M$ lignes suivantes contiennent chacune cinq entiers $a_i, b_i, c_i, d_i, k_i$, utilisés pour construire les requêtes. ($0 \le a_i, b_i, c_i, d_i \le N$, $1 \le k_i \le N$)

Les $l_i$ et $r_i$ de chaque requête sont construits comme suit :

Soit $ans_{i-1}$ la réponse à la $(i-1)$-ième requête (la réponse à la $0$-ième requête est $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$

Si $l_i > r_i$, échangez $l_i$ et $r_i$.

Sortie

Pour chaque requête, affichez une ligne contenant la réponse dans l'ordre.

Exemples

Entrée 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

Sortie 1

2
-1
2
3

Entrée 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

Sortie 2

6
9
10
4
6
3
10
4
6
4