Dada una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$. Escribe un programa para procesar las siguientes consultas:

• l r k: Sea $S$ el conjunto (sin duplicados) formado por los números desde el $l$-ésimo hasta el $r$-ésimo en $A$, ordenados en orden ascendente. Imprime el $k$-ésimo número más pequeño en $S$. Si el $k$-ésimo número más pequeño no existe, imprime $-1$.

La secuencia se indexa a partir de $1$.

Entrada

La primera línea contiene un entero $N$, la longitud de la secuencia. ($1 \le N \le 100{,}000$)

La segunda línea contiene $N$ enteros $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 10^9$)

La tercera línea contiene un entero $M$, el número de consultas. ($1 \le M \le 100{,}000$)

Las siguientes $M$ líneas contienen cada una cinco enteros $a_i, b_i, c_i, d_i, k_i$, utilizados para construir las consultas. ($0 \le a_i, b_i, c_i, d_i \le N$, $1 \le k_i \le N$)

Los $l_i$ y $r_i$ de cada consulta se construyen de la siguiente manera:

Sea $ans_{i-1}$ la respuesta a la $(i-1)$-ésima consulta (la respuesta a la $0$-ésima consulta es $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$, intercambia $l_i$ y $r_i$.

Salida

Para cada consulta, imprime una línea en orden que contenga la respuesta.

Ejemplos

Entrada 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

Salida 1

2
-1
2
3

Entrada 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

Salida 2

6
9
10
4
6
3
10
4
6
4