오라클

오라클은 어떤 문제를 한 번의 연산으로 풀어 주는 블랙박스를 가리키는 계산 이론 용어다. 결정 문제를 연구할 때 쓰는 도구다. 이 말의 뿌리는 고대 그리스에 있다. 가장 널리 알려진 오라클은 아폴론을 섬기며 델포이의 신탁을 전한 사제 피티아다. 피티아는 한 사람의 이름이 아니라 델포이 신탁을 맡은 사제에게 주어진 칭호이고, 그리스인은 기원전 7세기부터 서기 4세기까지 델포이에 신탁을 구했다. 이 문제의 주인공은 델포이의 첫 피티아이자 아폴론의 딸이라고도 전해지는 페모노에다.

페모노에 앞에 $n$개의 경기가 순서대로 놓여 있다. 경기는 1번부터 $n$번까지 차례로 열리고, 이미 끝난 경기로 돌아갈 수는 없다. 시간을 되돌리는 일은 아폴론의 권능 밖이다. 마음에 들지 않는 경기는 건너뛸 수 있다. 참가한 경기에서는 돈을 걸고 그 경기의 배율을 곱한 만큼을 받는다. 배율이 음수면 그만큼 잃는다. 보통은 결과를 미리 알 수 없지만 페모노에는 델포이의 신탁이라서 아폴론이 결과를 모두 알려 주었다. 대신 아폴론은 욕심을 부리지 말라고 경고했다. 너무 크게 따면 의심을 사고, 제우스가 알게 되면 아폴론이 곤란해진다. 문제는 질 좋은 그리스 포도주를 몇 잔 걸친 뒤로 페모노에의 판단력이 흐려졌다는 데 있다. 자신감이 붙을수록 판돈을 올려서, $j$번째로 참가하는 경기에는 정확히 $j^2 + aj + b$를 건다. 조언자인 당신의 일은 페모노에의 이익을 최대로 만드는 것이다. 몇 경기에 나갈지와 얼마를 걸지는 당신 말을 듣지 않지만, 어느 경기에 나갈지는 당신 말을 따른다.

$i$번째 경기의 배율을 $p_i$라고 하자. 페모노에가 참가할 경기를 $i_1 < i_2 < \dots < i_k$로 고르면 이익은 $\sum_{j=1}^{k} (j^2 + aj + b) \, p_{i_j}$다. $k = 1, 2, \dots, n$ 각각에 대해 정확히 $k$개의 경기에 참가해서 얻을 수 있는 최대 이익을 구하라.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스의 첫째 줄에 경기 수 $n$ ($1 \le n \le 50000$)이 주어진다. 둘째 줄에 $n$개의 정수 $p_1, p_2, \dots, p_n$ ($|p_i| \le 50000$)이 공백으로 구분되어 주어진다. $p_i$는 $i$번째 경기의 배율이다. 셋째 줄에 음이 아닌 두 정수 $a$와 $b$ ($0 \le a \le 100$, $0 \le b \le 100$, $a^2 \ge 4b$)가 주어진다. 페모노에는 $j$번째로 참가하는 경기에 $j^2 + aj + b$를 건다.

각 테스트 케이스마다 한 줄에 정수 $n$개를 공백 하나로 구분해 출력한다. $i$번째 수는 정확히 $i$개의 경기에 참가할 때 얻을 수 있는 최대 이익이다.