Cho dãy $A_1, A_2, \ldots, A_N$ có độ dài $N$. Viết chương trình xử lý các truy vấn sau:

• l r k: Gọi $S$ là tập hợp (không trùng lặp) gồm các số từ vị trí $l$ đến $r$ trong $A$, được sắp xếp theo thứ tự tăng dần. In ra số nhỏ thứ $k$ trong $S$. Nếu số nhỏ thứ $k$ không tồn tại, in ra $-1$.

Dãy được đánh chỉ số bắt đầu từ $1$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$, độ dài của dãy. ($1 \le N \le 100{,}000$)

Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 10^9$)

Dòng thứ ba chứa số nguyên $M$, số lượng truy vấn. ($1 \le M \le 100{,}000$)

$M$ dòng tiếp theo, mỗi dòng chứa năm số nguyên $a_i, b_i, c_i, d_i, k_i$, dùng để xây dựng các truy vấn. ($0 \le a_i, b_i, c_i, d_i \le N$, $1 \le k_i \le N$)

$l_i$ và $r_i$ của mỗi truy vấn được xây dựng như sau:

Gọi $ans_{i-1}$ là đáp án của truy vấn thứ $(i-1)$ (đáp án của truy vấn thứ $0$ là $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$

Nếu $l_i > r_i$, đổi chỗ $l_i$ và $r_i$.

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa đáp án theo thứ tự.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

2
-1
2
3

Dữ liệu vào 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

Dữ liệu ra 2

6
9
10
4
6
3
10
4
6
4