13927번 - 수열과 쿼리 14

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

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

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

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

둘째 줄에는 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를 바꾼다.

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