Given an integer sequence $p_1, \dots, p_n$ of length $n$, and two non-negative integers $a$ and $b$.

For each $1 \le k \le n$, you need to choose a subsequence $q_1, \dots, q_k$ of $p$ to maximize $\sum_{i=1}^k q_i(i^2+ai+b)$.

Input

The first line contains a positive integer $T$, representing the number of test cases. The format for each test case is as follows:

• The first line contains a positive integer $n$.
• The second line contains $n$ integers $p_1, \dots, p_n$.
• The third line contains two non-negative integers $a, b$.

Output

For each test case, output a single line containing $n$ integers, representing the answers for $k=1, \dots, k=n$ respectively.

Examples

Input 1

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

Output 1

3 14 36
6 18 38 44 26

Input 2

See provided files.

Constraints

For all test cases, it is guaranteed that $1 \le T \le 20$, $n \le 50000$, $|p_i| \le 50000$, $0 \le a, b \le 100$, and $a^2 \ge 4b$.