Дан массив $A_1, A_2, \ldots, A_N$ длины $N$. Напишите программу для обработки следующих запросов:

• l r k: Пусть $S$ — множество (без повторений), состоящее из чисел с $l$-го по $r$-е в $A$, отсортированное по возрастанию. Выведите $k$-е наименьшее число в $S$. Если $k$-е наименьшее число не существует, выведите $-1$.

Нумерация элементов массива начинается с $1$.

Входные данные

Первая строка содержит целое число $N$ — длину массива. ($1 \le N \le 100\,000$)

Вторая строка содержит $N$ целых чисел $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 10^9$)

Третья строка содержит целое число $M$ — количество запросов. ($1 \le M \le 100\,000$)

Следующие $M$ строк содержат по пять целых чисел $a_i, b_i, c_i, d_i, k_i$, используемых для построения запросов. ($0 \le a_i, b_i, c_i, d_i \le N$, $1 \le k_i \le N$)

Значения $l_i$ и $r_i$ каждого запроса формируются следующим образом:

Пусть $ans_{i-1}$ — ответ на $(i-1)$-й запрос (ответ на $0$-й запрос равен $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$

Если $l_i > r_i$, поменяйте местами $l_i$ и $r_i$.

Выходные данные

Для каждого запроса выведите одну строку, содержащую ответ, в порядке следования запросов.

Примеры

Входные данные 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

Выходные данные 1

2
-1
2
3

Входные данные 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

Выходные данные 2

6
9
10
4
6
3
10
4
6
4