“Oracle”（预言机）是计算机科学中的一个概念，它作为一个黑盒，可以在单次操作中解决某种问题。它是一种用于研究判定性问题的工具。预言机的起源可以追溯到古希腊。其中最著名的大概是德尔斐的皮提亚（Pythia），她是阿波罗的女祭司。皮提亚并不是一个人的名字，而是德尔斐预言者的头衔。从公元前 7 世纪到公元 4 世纪，希腊人一直向她们咨询。而德尔斐的第一位预言者费蒙诺（Phemonoe），据说是阿波罗本人的女儿，她是本题的主角。你可能会问，为什么这道题没有出现名字以 I 开头的计算机科学家？好吧，我们实在找不到名字以 I 开头的、与本题有任何关系的计算机科学家，所以请接受这个事实。

费蒙诺参与了一系列共 $n$ 场游戏。这些游戏是按顺序进行的。你不能回到过去玩已经结束的游戏，因为时间旅行不在阿波罗的能力范围内。不过，她可以选择不参加某场游戏。在这些游戏中，她可以对每一场游戏下注，并获得相当于她下注金额若干倍的收益。通常情况下，你不应该知道每场游戏的结果。但由于她是德尔斐的预言者，阿波罗已经准确地告诉了她会发生什么。然而，阿波罗警告她不要太贪心。过于多疑并赢得太多显然不是个好主意。你看，如果宙斯发现阿波罗做了什么，他可能不会太高兴。不幸的是，在喝了几杯优质的希腊葡萄酒后，费蒙诺的判断力不如她所需要的那样好。随着自信心的增长，她也开始提高赌注。作为她的顾问，你的工作是使她的利润最大化。注意，她不会听从你关于她想参加的游戏总数以及她打算下注金额的建议，但她会听从你关于参加哪些游戏的建议。

输入格式

第一行包含一个整数 $T$ ($T \le 20$)，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数，表示游戏总数 $n$ ($n \le 50000$)。第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示每场游戏的乘数。费蒙诺在每场游戏中的收益将是她下注金额与乘数的乘积。负乘数意味着亏损。对于每个 $i \in \{1, \dots, n\}$，你可以假设 $|p_i| \le 50000$。第三行包含两个非负整数 $a$ 和 $b$ ($a, b \le 100$)，表示费蒙诺在她参加的第 $j$ 场游戏中会下注 $j^2 + aj + b$，其中 $a^2 \ge 4b$。

输出格式

对于每个测试用例，在一行中输出 $n$ 个整数，分别表示费蒙诺决定参加 $1, 2, \dots, n$ 场游戏时的最大利润。

样例

样例输入 1

2
3
1 2 3
0 0
5
1 -1 1 -1 1
3 2

样例输出 1

3 14 36
6 18 38 44 26