시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 4 MB (언어별 추가 메모리 없음) 94 35 21 56.757%

문제

N개의 정수로 구성된 배열 X에 대한 정보가 주어집니다. 그리고 몇 개의 쿼리가 주어집니다. 각 쿼리는 하나의 정수 q로 표현됩니다. 해당 쿼리에 대해서 배열 X에서 q번째로 작은 원소를 구해야 합니다. 여기서 q는 0-based index입니다. 즉, q=0이면 가장 작은 원소, q=1이면 두 번째로 가장 작은 원소를 구해야 합니다.

이 문제는 너무 쉬워 보일 수 있습니다. 단순히 정렬 후, 쿼리에 대한 답을 출력하면 되기 때문입니다. 이 방법을 막기 위해서 이 문제는 메모리 제한이 너무 작습니다. 배열 X에 대한 정보 전체를 저장할 수 없습니다. 하지만 쿼리의 수는 적어서 쿼리에 대한 정보 전체는 저장할 수 있습니다.

N, x0, a, b가 주어지고 쿼리의 정보가 담긴 배열이 주어집니다. 배열 X를 생성하는 pseudocode는 다음과 같습니다.

X[0] = x0
for i = 1 to n-1:
        X[i] = (X[i-1] * a + b) % (1000000007).

Integer overflow에 주의하세요.

모든 쿼리에 대한 답을 모두 더한 값을 출력하는 프로그램을 작성하세요.

입력

첫째 줄에는 4개의 정수 N, x0, a, b가 주어집니다. (1≤N≤2000000, 0≤x0,a,b≤1000000006)

둘째 줄에는 쿼리의 개수 m이 주어집니다. (1≤m≤1000)

셋째 줄에는 쿼리의 각 원소를 나타내는 m개의 정수가 주어집니다. (0≤q≤N-1)

출력

문제의 답을 나타내는 정수를 출력합니다.

예제 입력 1

5 100 1 5
2
0 3

예제 출력 1

215

출처

  • 데이터를 추가한 사람: yclock