잘못 구현한 큐

큐는 다음 두 연산을 할 수 있는 선형 자료구조이다.

1. 뒤에 원소를 삽입한다 (push).
2. 앞에서 원소를 삭제한다 (pop).

그런데 pop 함수를 잘못 구현했다. pop 질의마다 맨 앞의 원소 하나만 지우는 것이 아니라, 서로 다른 위치에 있는 $N$개의 원소를 동시에 삭제한다.

구체적으로, pop 함수가 원소를 삭제하는 위치는 $N$개이며 $A_1, A_2, \ldots, A_N$으로 표시한다. 큐의 인덱스는 맨 앞부터 1에서 시작한다. 삭제한 뒤에는 위와 같은 규칙으로 인덱스를 다시 매긴다.

이렇게 잘못 구현된 큐를 $D$번 pop한 뒤의 모습을 알아보려 한다. 실험을 위해 먼저 1부터 시작하는 정수를 무한히 push한다. 초기 큐는 "1 2 3 4 5 6 7 8..."이다. 이후 push 없이 큐를 $D$번 pop한다.

예를 들어 큐가 "1 2 3 4 5 6 7 8..."일 때 2번째와 5번째 원소를 삭제하면 큐는 "1 3 4 6 7 8 9 10..."이 된다. 한 번 더 삭제하면 "1 4 6 8 9 10 11 12..."가 되며, 이런 식으로 계속된다.

$Q$개의 질의를 처리한다. 각 질의는 정수 $x$ 하나로 이루어진다. 각 질의마다 $D$번 pop한 뒤 큐의 $x$번째 인덱스에 있는 수를 구한다.

첫 번째 줄에 $N$이 주어진다.

두 번째 줄에는 각 pop 연산에서 삭제할 인덱스 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어진다.

세 번째 줄에는 질의의 개수 $Q$와 pop 연산의 횟수 $D$가 공백으로 구분되어 주어진다.

이어지는 $Q$개의 줄에는 각각 질의 정수 $x$가 하나씩 주어진다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답을 정수 하나로 출력한다.

• $1 \leq N \leq 500\,000$
• $1 \leq A_i \leq 10^{12}$
• 모든 $A_i$는 서로 다르다.
• $1 \leq Q \leq 500\,000$
• $1 \leq D \leq 10^{12}$
• 모든 질의에 대해 $1 \leq x \leq 10^{12}$이다.