给定一个长度为 $N$ 的数列 $A_1, A_2, \ldots, A_N$。请编写一个程序，处理以下查询：

• l r k：令 $S$ 为由 $A$ 中第 $l$ 个数到第 $r$ 个数构成的、按升序排序的集合（不允许重复），输出其中的第 $k$ 小的数。如果第 $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