시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 1536 MB 61 14 7 17.500%

문제

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

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

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

입력

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

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

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

넷째 줄부터 M개의 줄에는 쿼리를 만드는 정보인 ai, bi, ci, di, ki가 한 줄에 하나씩 주어진다. (0 ≤ ai, bi, ci, di ≤ N, 1 ≤ ki ≤ N)

각각의 쿼리 li, ri는 다음과 같이 만든다.

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

  • li = (ai x max(ansi-1, 0) + bi) mod N + 1
  • ri = (ci x max(ansi-1, 0) + di) mod N + 1

만약, li > ri 이면 li와 ri를 바꾼다.

출력

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

예제 입력 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

출처