길이가 $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$)

둘째 줄에는 $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$는 다음과 같이 만든다.

먼저, $i-1$번째 쿼리의 정답을 $ans_{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$를 바꾼다.

출력

각각의 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

Sample

Input

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

Output

2
-1
2
3

Sample

Input

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

Output

6
9
10
4
6
3
10
4
6
4