U611933 选择

给定一个长度为 $n$ 的整数序列 $p_1,\dots,p_n$，以及两个非负整数 $a,b$. 对于每个 $1\le k\le n$，你需要选出 $p$ 的一个长度为 $k$ 的子序列 $q_1,\dots,q_k$，最大化 $\sum_{i=1}^k q_i(i^2+ai+b)$.

第一行一个正整数 $T$，表示数据组数。每组数据的格式如下： - 第一行一个正整数 $n$. - 第二行 $n$ 个整数 $p_1,\dots,p_n$. - 第三行两个正整数 $a,b$.

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

对于 $30\%$ 的数据，$n\le 3000$. 对于 $60\%$ 的数据，$T\le 4$. 对于 $100\%$ 的数据，$1\le T\le 20,n\le 50000,|p_i|\le 50000,0\le a,b\le 100,a^2\ge 4b$.