Oracle

In computing theory, an oracle is a black box that solves some problem in a single operation, and it is a tool for studying decision problems. The word comes from ancient Greece. The best known oracle is Pythia, the priestess of Apollo who delivered the oracles of Delphi. Pythia is not one person's name but the title given to the priestess in charge of the Delphic oracle, and Greeks consulted Delphi from the 7th century BC to the 4th century AD. The character of this problem is Phemonoe, the first Pythia of Delphi, said by some to be a daughter of Apollo herself.

Phemonoe faces $n$ games in order. Game 1 through game $n$ take place one after another, and she cannot go back to a game that is already finished, because turning back time is outside Apollo's powers. She may skip any game she does not like. In a game she enters she places a bet and receives her bet multiplied by that game's multiplier. A negative multiplier means she loses that much. Normally nobody knows the results in advance, but Apollo told Phemonoe every result because she is the oracle of Delphi. He did warn her not to be greedy. Winning too much draws suspicion, and Apollo would be in trouble if Zeus found out. The trouble is that after a few glasses of good Greek wine her judgment is not what it should be. Her confidence grows and so do her bets: on the $j$-th game she enters she bets exactly $j^2 + aj + b$. As her adviser, your job is to maximize her profit. She will not listen to you about how many games she plays or how much she bets, but she will follow your advice about which games to enter.

Let $p_i$ be the multiplier of the $i$-th game. If Phemonoe enters the games $i_1 < i_2 < \dots < i_k$, her profit is $\sum_{j=1}^{k} (j^2 + aj + b) \, p_{i_j}$. For each $k = 1, 2, \dots, n$, find the maximum profit she can make by entering exactly $k$ games.

The first line contains the number of test cases $T$ ($1 \le T \le 20$).

The first line of each test case contains the number of games $n$ ($1 \le n \le 50000$). The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($|p_i| \le 50000$) separated by spaces, where $p_i$ is the multiplier of the $i$-th game. The third line contains two non-negative integers $a$ and $b$ ($0 \le a \le 100$, $0 \le b \le 100$, $a^2 \ge 4b$). Phemonoe bets $j^2 + aj + b$ on the $j$-th game she enters.

For each test case, print $n$ integers on one line, separated by single spaces. The $i$-th number is the maximum profit she can make by entering exactly $i$ games.