407528: GYM102822 I Invaluable Assets

Lucid waters and lush mountains are invaluable assets. Guided by this conviction, Little Horse starts to plant trees. Little Horse has $$$n$$$ trees. In the beginning, the $$$i$$$-th tree has a height of $$$h_i$$$. To make the trees grow higher, Little Horse needs to buy fertilizers. The fertilizer which can make a tree's height increase by $$$x$$$ has a cost of $$$x^2+c$$$ ($$$c$$$ is a given const, and $$$x$$$ must be an integer).

Now, Little Horse wants to know what's the minimum cost to make all trees' heights no less than $$$k$$$. There are $$$q$$$ queries about it. Please note that buying only one fertilizer for a tree is not necessarily the best solution. For example, to make a tree's height increse by $$$3$$$, one method is to spend $$$3^2+c$$$, another method is to spend $$$(1^2+c)+(2^2+c)$$$.

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10$$$) — the number of test cases.

The first line of each test case contains three integers $$$n,c,q$$$ ($$$1 \le n,q \le 10^5$$$, $$$1 \le c \le 10^4$$$) — the number of trees, the given const, and the number of queries.

Then the next line contains $$$n$$$ integers $$$h_1,h_2,\dots,h_n$$$ ($$$0 \le h_1,h_2,\dots,h_n \le 10^9$$$) — the height of each tree in the beginning.

Then in the next $$$q$$$ lines, each line contains an integer $$$k$$$ ($$$0 \le k \le 10^9$$$), indicating the query.

It's guaranteed that $$$h_1,h_2,\dots,h_n$$$ and $$$k$$$ are generated uniformly and randomly within $$$[0,10^9]$$$.

The output of the $$$x$$$-th test case begins with $$$Case$$$ #$$$x$$$: in a single line.

Then in the next $$$q$$$ lines, each line contains an integer, indicating the answer to each query.

2
3 2 3
3 0 2
1
2
3
4 3 5
0 2 3 4
1
2
3
4
5

Case #1:
3
6
12
Case #2:
4
7
15
25
40