시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 62 7 2 40.000%

문제

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

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

입력

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

둘째 줄에는 A1, A2, ..., AN이 주어진다.

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

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

출력

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

제한

  • 1 ≤ N ≤ 105
  • 1 ≤ M ≤ 109
  • 0 ≤ Ai < M
  • 1 ≤ Q ≤ 5·105
  • 0 ≤ d ≤ 109
  • 1 ≤ k ≤ N

예제 입력 1

5 6
1 4 2 1 1
3
4 4
2 3
1 1

예제 출력 1

1
1
5

힌트

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

출처