队列是一种线性数据结构，可以进行以下两种操作：

1. 在队尾插入一个元素（push），或者
2. 删除队头的一个元素（pop）。

然而，我们错误地实现了 pop 函数。对于每次 pop 查询，我们不是只删除队头的一个元素，而是同时删除不同下标处的 $n$ 个特定元素。

具体来说，我们的 pop 函数会在 $n$ 个不同的位置删除元素：$a_1, a_2, \dots, a_n$。队列从队头开始以 1 为索引，每次 pop 操作后，剩余元素会重新从 1 开始编号。

我们很好奇在经过 $d$ 次 pop 操作后，这个错误的队列会变成什么样。

为了进行实验，我们首先向队列中推入了无限多个数字，从 1 开始。因此，初始队列看起来是 “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$ ($1 \le n \le 5 \cdot 10^5$)。

第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$，表示每次 pop 操作中我们要删除的位置 ($1 \le a_i \le 10^{12}$；所有 $a_i$ 互不相同)。

第三行包含两个空格分隔的整数 $q$ 和 $d$，分别表示查询次数和 pop 操作次数 ($1 \le q \le 5 \cdot 10^5$；$1 \le d \le 10^{12}$)。

接下来的 $q$ 行，每行包含一个整数 $x$，表示一个查询 ($1 \le x \le 10^{12}$)。

输出格式

输出 $q$ 行，其中第 $i$ 行包含一个整数，表示第 $i$ 个查询的答案。

样例

输入 1

2
2 5
8 2
1
2
3
4
5
6
7
8

输出 1

1
4
6
8
9
10
11
12

输入 2

3
7 1 32
8 5
2
8
7
17
26
19
3
1

输出 2

8
18
17
27
39
29
10
6