20846번 - 수열과 쿼리 40

길이가 N인 수열 A₁, A₂, ..., A_N과 정수 M이 주어진다. 쿼리 Q개를 수행해보자. 쿼리는 두 정수 d와 k로 이루어져 있으며, 다음을 순서대로 수행하는 것이다.

• 새로운 수열 B_i = (A_i + d) mod M을 만든다. (1 ≤ i ≤ N)
• 모든 i (1 ≤ i ≤ N)에 대해서, i번째 접미사를 B_i, B_i+1, ..., B_N 으로 정의한다.
• 사전 순으로 K번째로 작은 수열 B의 접미사 번호를 출력한다.

첫째 줄에 수열의 크기 N과 정수 M이 주어진다.

둘째 줄에는 A₁, A₂, ..., A_N이 주어진다.

셋째 줄에는 쿼리의 개수 Q가 주어진다.

넷째 줄부터 Q개의 줄에 쿼리 d, k가 한 줄에 하나씩 주어진다.

각각의 쿼리를 수행하면서 사전 순으로 K번째로 작은 수열 B의 접미사 번호를 한 줄에 하나씩 출력한다.

• 1 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 10⁹
• 0 ≤ A_i < M
• 1 ≤ Q ≤ 5·10⁵
• 0 ≤ d ≤ 10⁹
• 1 ≤ k ≤ N

첫 번째 쿼리에서 수열 B = [5, 2, 0, 5, 5]이다. 접미사를 모두 사전 순으로 정렬하면 [0, 5, 5], [2, 0, 5, 5], [5], [5, 2, 0, 5, 5], [5, 5] 이다. 사전 순으로 4번째인 접미사의 번호는 1이다.