给定一个长度为 $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$ 。
| 子任务编号 | 特殊限制 | 分值 |
|---|---|---|
| $1$ | $n\le 3000$ | $20$ |
| $2$ | $p_i$ 在 $[-50000,50000]$ 均匀随机 | $30$ |
| $3$ | $T\le 4$ | $30$ |
| $4$ | $ $ | $20$ |
时间限制：$\texttt{3s}$
空间限制：$\texttt{1024MB}$