题目描述

实验室里实现了一个队列。正常队列支持两种操作：

1. 在队尾插入一个元素；
2. 从队首删除一个元素。

然而，这个队列的删除函数写错了。每次执行删除操作时，它并不会只删除队首一个元素，而是会同时删除当前队列中若干个指定位置上的元素。

具体地，有 $n$ 个互不相同的位置 $a_1,a_2,\ldots,a_n$。队列从队首开始按 $1$ 编号；每次删除操作会删除当前编号为这些位置的元素。删除后，剩下的元素会重新从 $1$ 开始编号。

为了观察这个错误队列的行为，实验员先向队列中依次加入了无限多个整数 $1,2,3,4,\ldots$，之后不再插入任何元素，只连续执行 $d$ 次错误删除操作。

例如，若当前队列为 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$ 次删除操作后，队列中第 $x$ 个位置上的数是多少。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$，表示每次删除操作要删除的位置。

第三行包含两个整数 $q,d$，分别表示询问数和删除操作次数。

接下来 $q$ 行，每行包含一个整数 $x$，表示一个询问。

输出格式

输出 $q$ 行，第 $i$ 行输出第 $i$ 个询问的答案。

数据范围

• $1\le n\le 5\cdot 10^5$；
• $1\le a_i\le 10^{12}$；
• 所有 $a_i$ 互不相同；
• $1\le q\le 5\cdot 10^5$；
• $1\le d\le 10^{12}$；
• $1\le x\le 10^{12}$。

样例 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