長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ が与えられる。以下のクエリを処理するプログラムを作成せよ。

• l r k: $A$ の $l$ 番目から $r$ 番目までの数からなる集合（重複なし） $S$ を昇順に並べたとき、$S$ の中で $k$ 番目に小さい数を出力せよ。$k$ 番目に小さい数が存在しない場合は、$-1$ を出力せよ。

数列のインデックスは $1$ から始まる。

入力

$1$ 行目には整数 $N$ が与えられる。これは数列の長さである ($1 \le N \le 100{,}000$)。

$2$ 行目には $N$ 個の整数 $A_1, A_2, \ldots, A_N$ が与えられる ($1 \le A_i \le 10^9$)。

$3$ 行目には整数 $M$ が与えられる。これはクエリの数である ($1 \le M \le 100{,}000$)。

次の $M$ 行にはそれぞれ $5$ 個の整数 $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$ 行ずつ順に出力せよ。

入出力例

入力例 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