给定一个长度为 $n$ 的整数序列 $p_1,\cdots,p_n$ ，以及两个非负整数 $a,b$ 。

对于每个 $1\le k\le n$ ，你需要选出 $p$ 的一个长度为 $k$ 的子序列 $q_1,\cdots,q_k$ ，最大化 $\sum_{i=1}^k q_i(i^2+ai+b)$ 。

输入格式

第一行一个正整数 $T$ ，表示数据组数。每组数据的格式如下：

• 第一行一个正整数 $n$ 。
• 第二行 $n$ 个整数 $p_1,\cdots,p_3$ 。
• 第三行两个正整数 $a,b$ 。

输出格式

对每组数据输出一行 $n$ 个整数，分别表示 $k=1,\cdots,k=n$ 的答案。

样例一

input

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

output

3 14 36
6 18 38 44 26

样例二

见下发文件。

数据范围

对于所有数据，保证 $1\le T\le 20,n\le 50000,|p_i|\le 50000,0\le a,b\le 100,a^2\ge 4b$ 。

时间限制：$\texttt{3s}$

空间限制：$\texttt{1024MB}$