Farmer John 正在和他的挚友奶牛 Bessie 玩一款著名的策略卡牌游戏。FJ 有 $N$ ($2\le N\le 2\cdot 10^5$) 张牌，编号依次为 $1$ 到 $N$。如果 FJ 想要打出第 $i$ 张牌，需要花费 $a_i$ ($1 \leq a_i \leq 10^9$) 点 moolixir。

他的手牌中始终持有 $H$ 张牌 ($1\le H< N$)。初始时，他的手牌是 $1$ 到 $H$ 号牌。其余的牌在抽牌队列中。每当 FJ 打出一张手牌，他就会从抽牌队列的队首抽一张牌补充到手牌中。然后，FJ 会将刚才打出的那张牌放到抽牌队列的队尾。初始时，牌 $H+1$ 到 $N$ 按顺序排列在抽牌队列中（从队首到队尾）。

在这个游戏中，时间以整数秒为单位。游戏初始时间为 $0$，FJ 拥有 $0$ 点 moolixir。在每个整数时间点 $t=1, 2, 3, \dots$ 之前，moolixir 会增加 $1$ 点。在每个整数时间点，如果 FJ 手中某张牌的费用不超过他当前拥有的 moolixir，他可以选择打出该牌，这会消耗掉相应的 moolixir。

FJ 将他的一些牌 $s_1, s_2, \ldots, s_k$ 标记为获胜条件牌 ($1\le k\le N$, $1\le s_i\le N$)。如果 FJ 的手牌中至少有一张获胜条件牌，那么他接下来打出的牌必须是获胜条件牌。

他向你提出了 $Q$ ($1 \leq Q \leq 2 \cdot 10^5$) 个询问。每个询问的形式如下：在 $t$ 时间内 ($1 \leq t \leq 10^{18}$)，他最多能打出多少张获胜条件牌？

输入格式

第一行包含 $N$ 和 $H$。

第二行包含 $N$ 个整数 $a_1, a_2, \ldots, a_N$。

第三行包含一个整数 $k$，表示获胜条件牌的数量。

第四行包含 $k$ 个不同的整数 $s_1, s_2, \ldots, s_k$。

第五行包含一个整数 $Q$。

接下来的 $Q$ 行，每行包含一个整数 $t$，表示每个询问的时间。

输出格式

对于每个询问，输出在 $t$ 时间内 FJ 最多能打出的获胜条件牌数量。

样例

输入 1

6 3
2 4 3 5 7 6
2
1 4
6
1
2
3
7
10
1000000000000000

输出 1

0
1
1
2
2
142857142857143

说明 1

在此例中，初始手牌包含 1 号牌，这是一张获胜条件牌。你可以在积累了 2 点 moolixir（即 2 秒后）打出它。这意味着在 $t=1$ 时你无法打出任何牌，但在 $t=2$ 时你可以打出第一张牌，且该牌必须是获胜条件牌。

在 $t=3$ 后，最优策略仍然是打出 1 号牌并剩余 1 点 moolixir，因此此时答案仍为 1。

随后你抽到了 4 号牌，这也是一张获胜条件牌。你在 $t=7$ 后立即打出它，此时你总共打出了 2 张获胜条件牌。

接着你抽到了 5 号牌，此时手牌中没有获胜条件牌。在 $t=10$ 后，即使你花费 3 点 moolixir 打出 3 号牌，你打出的获胜条件牌数量也不会增加。

子任务

• 测试点 2-3：$N,Q\le 100$
• 测试点 4-5：$H=1$
• 测试点 6-11：无额外限制。