最近，Tom 喜欢玩一款电子游戏。游戏规则如下：游戏在 $x$ 轴上进行。游戏中共有 $n+1$ 根柱子，从左到右依次排列。柱子编号从 $0$ 到 $n$，编号为 $i$ 的柱子坐标为 $x=i$。游戏中还有一个范围在 $[n+1, +\infty)$ 的无限平台。玩家跳到该范围内的任意位置即可获胜。

玩家从编号为 $0$ 的柱子出发，只能从左向右跳跃，即坐标必须增加。玩家只能跳到柱子或平台上，否则会掉入虚空并导致游戏失败。此外，玩家的跳跃能力有限，每次跳跃的距离不能超过 $p$。

除了编号为 $0$ 的柱子外，其余每根柱子上都有一个宝箱。编号为 $i$ 的柱子上的宝箱里有 $a_i$ 枚金币。然而，其中一些是陷阱宝箱（$a_i < 0$），玩家会损失 $|a_i|$ 枚金币。

该游戏共有 $n$ 个关卡。在第 $x$ 关中，Tom 只能跳到编号为 $x$ 的倍数的柱子上。现在有 $q$ 次询问，每次给出一个数字 $x$，询问 Tom 在第 $x$ 关获胜时能获得的最大金币数。Tom 在途中可能会打开过多的陷阱宝箱，导致获得负数的金币。

输入格式

第一行包含三个整数 $n, q$ 和 $p$ ($2 \le p \le n \le 10^6, 1 \le q \le 10^6$)，分别表示柱子的数量、询问次数以及最长跳跃距离。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($|a_i| \le 10^9$)，表示编号为 $i$ 的柱子上宝箱的金币数量。

接下来的 $q$ 行，每行包含一个整数 $x$ ($1 \le x \le n$)，表示对第 $x$ 关能获得的最大金币数的询问。

输出格式

对于每次询问，输出一行一个整数，表示答案。如果无法获胜，则输出 Noob。

样例

样例输入 1

5 3 4
2 5 -6 -4 3
1
2
3

样例输出 1

10
5
-6

样例输入 2

10 6 8
5 4 -6 8 -11 5 -6 4 -7 3
1
2
4
6
8
10

样例输出 2

29
24
12
5
4
Noob