#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
class ConvexHull {
private:
int head, tail;
long long A[N], B[N];
public:
void init() { head = tail = 0; }
bool bad(int l1, int l2, int l3) {
return (long double) (B[l3] - B[l1]) / (A[l1] - A[l3]) < (long double) (B[l2] - B[l1]) / (A[l1] - A[l2]);
}
void add(long long a, long long b) {
A[tail] = a; B[tail++] = b;
while (tail > 2 && bad(tail - 3, tail - 2, tail - 1)) {
A[tail - 2] = A[tail - 1];
B[tail - 2] = B[tail - 1];
tail--;
}
}
long long query(long long x) {
if (head >= tail) head = tail - 1;
while (head < tail - 1
&& A[head + 1] * x + B[head + 1] >= A[head] * x + B[head]) head++;
return A[head] * x + B[head];
}
} hull;
int n, a, b, c;
long long sum[N];
long long f(long long x) { return a * x * x + b * x + c; }
void load() {
scanf("%d%d%d%d", &n, &a, &b, &c);
for (int i = 1; i <= n; ++i) {
scanf("%lld", sum + i);
sum[i] += sum[i - 1];
}
}
void process() {
hull.init();
long long cost = f(sum[1]);
hull.add(-2 * a * sum[1], cost + a * sum[1] * sum[1] - b * sum[1]);
for (int i = 2; i <= n; ++i) {
cost = f(sum[i]) + max(0ll, hull.query(sum[i]));
hull.add(-2 * a * sum[i], cost + a * sum[i] * sum[i] - b * sum[i]);
}
printf("%lld\n", cost);
}
int main() {
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int test; scanf("%d", &test);
while (test--) {
load();
process();
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTiA9IDFlNiArIDEwOwoKY2xhc3MgQ29udmV4SHVsbCB7CnByaXZhdGU6CiAgICBpbnQgaGVhZCwgdGFpbDsKICAgIGxvbmcgbG9uZyBBW05dLCBCW05dOwpwdWJsaWM6CiAgICB2b2lkIGluaXQoKSB7IGhlYWQgPSB0YWlsID0gMDsgfQogICAgYm9vbCBiYWQoaW50IGwxLCBpbnQgbDIsIGludCBsMykgewogICAgICAgIHJldHVybiAobG9uZyBkb3VibGUpIChCW2wzXSAtIEJbbDFdKSAvIChBW2wxXSAtIEFbbDNdKSA8IChsb25nIGRvdWJsZSkgKEJbbDJdIC0gQltsMV0pIC8gKEFbbDFdIC0gQVtsMl0pOwogICAgfQogICAgdm9pZCBhZGQobG9uZyBsb25nIGEsIGxvbmcgbG9uZyBiKSB7CiAgICAgICAgQVt0YWlsXSA9IGE7IEJbdGFpbCsrXSA9IGI7CiAgICAgICAgd2hpbGUgKHRhaWwgPiAyICYmIGJhZCh0YWlsIC0gMywgdGFpbCAtIDIsIHRhaWwgLSAxKSkgewogICAgICAgICAgICBBW3RhaWwgLSAyXSA9IEFbdGFpbCAtIDFdOwogICAgICAgICAgICBCW3RhaWwgLSAyXSA9IEJbdGFpbCAtIDFdOwogICAgICAgICAgICB0YWlsLS07CiAgICAgICAgfQogICAgfQogICAgbG9uZyBsb25nIHF1ZXJ5KGxvbmcgbG9uZyB4KSB7CiAgICAgICAgaWYgKGhlYWQgPj0gdGFpbCkgaGVhZCA9IHRhaWwgLSAxOwogICAgICAgIHdoaWxlIChoZWFkIDwgdGFpbCAtIDEKICAgICAgICAgICAgICAgJiYgQVtoZWFkICsgMV0gKiB4ICsgQltoZWFkICsgMV0gPj0gQVtoZWFkXSAqIHggKyBCW2hlYWRdKSBoZWFkKys7CiAgICAgICAgcmV0dXJuIEFbaGVhZF0gKiB4ICsgQltoZWFkXTsKICAgIH0KfSBodWxsOwoKaW50IG4sIGEsIGIsIGM7CmxvbmcgbG9uZyBzdW1bTl07Cgpsb25nIGxvbmcgZihsb25nIGxvbmcgeCkgeyByZXR1cm4gYSAqIHggKiB4ICsgYiAqIHggKyBjOyB9Cgp2b2lkIGxvYWQoKSB7CiAgICBzY2FuZigiJWQlZCVkJWQiLCAmbiwgJmEsICZiLCAmYyk7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kpIHsKICAgICAgICBzY2FuZigiJWxsZCIsIHN1bSArIGkpOwogICAgICAgIHN1bVtpXSArPSBzdW1baSAtIDFdOwogICAgfQp9Cgp2b2lkIHByb2Nlc3MoKSB7CiAgICBodWxsLmluaXQoKTsKICAgIGxvbmcgbG9uZyBjb3N0ID0gZihzdW1bMV0pOwogICAgaHVsbC5hZGQoLTIgKiBhICogc3VtWzFdLCBjb3N0ICsgYSAqIHN1bVsxXSAqIHN1bVsxXSAtIGIgKiBzdW1bMV0pOwoKICAgIGZvciAoaW50IGkgPSAyOyBpIDw9IG47ICsraSkgewogICAgICAgIGNvc3QgPSBmKHN1bVtpXSkgKyBtYXgoMGxsLCBodWxsLnF1ZXJ5KHN1bVtpXSkpOwogICAgICAgIGh1bGwuYWRkKC0yICogYSAqIHN1bVtpXSwgY29zdCArIGEgKiBzdW1baV0gKiBzdW1baV0gLSBiICogc3VtW2ldKTsKICAgIH0KICAgIHByaW50ZigiJWxsZFxuIiwgY29zdCk7Cn0KCmludCBtYWluKCkgewogIC8vICBmcmVvcGVuKCJpbnB1dC5pbiIsICJyIiwgc3RkaW4pOwogLy8gICBmcmVvcGVuKCJvdXRwdXQub3V0IiwgInciLCBzdGRvdXQpOwoKICAgIGludCB0ZXN0OyBzY2FuZigiJWQiLCAmdGVzdCk7CiAgICB3aGlsZSAodGVzdC0tKSB7CiAgICAgICAgbG9hZCgpOwogICAgICAgIHByb2Nlc3MoKTsKICAgIH0KCiAgICByZXR1cm4gMDsKfQo=