407528: GYM102822 I Invaluable Assets

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Invaluable Assetstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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)$$$.

Input

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]$$$.

Output

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.

ExampleInput
2
3 2 3
3 0 2
1
2
3
4 3 5
0 2 3 4
1
2
3
4
5
Output
Case #1:
3
6
12
Case #2:
4
7
15
25
40

加入题单

上一题 下一题 算法标签: