409786: GYM103743 C Jump and Treasure

Tom likes playing a video game recently. The rules of this game are as follows. The game is played on an $$$x$$$-axis. There are a total of $$$n+1$$$ pillars in the game, which are arranged in a row from left to right. The pillars are numbered from $$$0$$$ to $$$n$$$. The coordinate of the pillar numbered $$$i$$$ is $$$x=i$$$. There is also an infinite platform in the game in the range of $$$[n+1,+\infty)$$$. Players can win by jumping to any position within this range.

Players start from the pillar numbered $$$0$$$ and can only jump from left to right, i.e. the coordinates must increase. And he can only jump on the pillars or the platform, otherwise, he will fall into the void and fail the game. In addition, his jumping ability is limited, and the distance of each jump does not exceed $$$p$$$.

Except for the pillar numbered $$$0$$$, there will be a treasure chest on each remaining pillar. The treasure chest on the pillar numbered $$$i$$$ will have $$$a_{i} $$$ gold coins. However, there are some trap chests ($$$a_{i}<0$$$) where he will lose $$$|a_{i}|$$$ gold coins.

This game has $$$n$$$ levels. Tom can only jump to the pillars numbered with multiples of $$$i$$$ in the $$$i$$$-th level. Now there are $$$q$$$ queries, each of which contains a number $$$x$$$, asking the maximum number of gold coins Tom can get when he wins at level $$$x$$$. It's possible that Tom opens too many trap chests on the way and gets negative gold coins.

The first line contains three integers $$$n$$$, $$$q$$$, and $$$p$$$ ($$$2\le p\le n\le 10^{6}$$$, $$$1\le q\le 10^{6}$$$), indicating the number of pillars, the number of queries, and the longest jump distance.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$|a_{i}|\le 10^{9}$$$), indicating the number of gold coins in the treasure chest on the pillar numbered $$$i$$$.

In the next $$$q$$$ lines, each line contains an integer $$$x$$$ ($$$1\le x\le n$$$), indicating a query of the maximum number of gold coins he can obtain in level $$$x$$$.

Output one integer in a single line for each query, representing the answer. If it is impossible to win, output Noob in a single line.

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

10
5
-6

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

29
24
12
5
4
Noob