길이가 N인 수열 A₁, A₂, ..., A_N이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.</p>

• l r k: S를 A의 l번째 수부터 r번째 수까지 수로 이루어진 오름차순으로 정렬된 집합(중복을 허용하지 않음)이라고 했을 때, k번째 수를 출력한다. 만약, k번째 수가 존재하지 않으면 -1을 출력한다.

수열의 인덱스는 1부터 시작한다.

입력 형식

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)</p>

둘째 줄에는 A₁, A₂, ..., A_N이 주어진다. (1 ≤ A_i ≤ 10⁹)

셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)

넷째 줄부터 M개의 줄에는 쿼리를 만드는 정보인 a_i, b_i, c_i, d_i, k_i가 한 줄에 하나씩 주어진다. (0 ≤ a_i, b_i, c_i, d_i ≤ N, 1 ≤ k_i ≤ N)

각각의 쿼리 l_i, r_i는 다음과 같이 만든다.

먼저, i-1번째 쿼리의 정답을 ans_i-1이라고 한다. (0번째 쿼리의 정답 ans₀ = 0)

• l_i = (a_i x max(ans_i-1, 0) + b_i) mod N + 1
• r_i = (c_i x max(ans_i-1, 0) + d_i) mod 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