¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#7059

숫자놀이 5s 1024MB

Problemas

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

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

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

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

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

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


Entrada

첫 줄에는 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})


Salida

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


Subtarea

# Puntaje Condición
#134

N\leq 5000, Q\leq 5000

#266

제한 없음


Ejemplo #1

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

Ejemplo #2

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

Fuente

KAIST ICPC Mock Contest 2023

Debes iniciar sesión para escribir código.