페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7059

숫자놀이 5s 1024MB

문제

정올이는 1부터 시작하는 무한히 많은 자연수를 정확히 한 개씩 가지고 있다.

한번의 놀이는 지금 가지고 있는 수 중, A_1번째로 작은 수, A_2번째로 작은 수, ..., A_N번째로 작은 수를 가지고 진행한다.

놀이가 끝난 이후 사용한 숫자들은 사라진다.

놀이를 D회 진행한 이후 정올이는 지금 가지고 있는 수 중 x번째로 작은 수가 무엇인지 궁금해 한다. 정올이의 궁금증을 해소해주자.

물론, 이 문제를 그냥 푸는 것은 너무나 쉽기 때문에 고정된 D에 대해 Q개의 x에 대해 문제를 해결해보도록 하자.

(Challenge) D가 쿼리마다 달라져도 문제를 해결 할 수 있습니다! 채점은 불가능하지만 한번 시도해봅시다!


입력

첫 줄에는 N이 주어진다. (1\leq N\leq 500000)

그 다음 줄에 A_1, A_2, ..., A_N이 주어진다. (1\leq A_i\leq 10^{12}, A_i\neq A_j)

그 다음 줄에 쿼리의 개수 Q와, 놀이를 진행하는 횟수 D가 주어진다. (1\leq Q\leq 500000, 1\leq D\leq 10^{12})

그 다음 Q개의 줄에 걸쳐 x가 주어진다. (1\leq x\leq 10^{12})


출력

Q개의 x에 대해, D회의 놀이 이후 x번째로 작은 수를 한 줄에 하나씩 총 Q개의 줄에 걸쳐 출력하시오.


부분문제

번호 점수 조건
#134점

N\leq 5000, Q\leq 5000

#266점

제한 없음


예제 #1

2
2 5
8 2
1
2
3
4
5
6
7
8
1
4
6
8
9
10
11
12

예제 #2

3
7 1 32
8 5
2
8
7
17
26
19
3
1
8
18
17
27
39
29
10
6

출처

KAIST ICPC Mock Contest 2023

로그인해야 코드를 작성할 수 있어요.