Kevin vừa mới học về định nghĩa phương sai. Với một mảng $a$ có độ dài $n$, phương sai của $a$ được định nghĩa như sau:

• Gọi $x = \frac{1}{n} \sum_{i=1}^{n} a_i$, tức là $x$ là giá trị trung bình của mảng $a$;
• Khi đó, phương sai của $a$ là $$V(a) = \frac{1}{n} \sum_{i=1}^{n} (a_i - x)^2.$$

Bây giờ, Kevin cho bạn một mảng $a$ gồm $n$ số nguyên, cùng với một số nguyên $k$. Bạn có thể thực hiện thao tác sau trên $a$:

• Chọn một đoạn $[l, r]$ ($1 \le l \le r \le n$), sau đó với mỗi $l \le i \le r$, tăng $a_i$ thêm $k$.

Với mỗi $1 \le p \le m$, bạn cần tìm phương sai nhỏ nhất có thể của $a$ sau khi thực hiện đúng $p$ thao tác, độc lập cho từng giá trị $p$.

Để đơn giản, bạn chỉ cần in ra các kết quả đã nhân với $n^2$. Có thể chứng minh rằng các kết quả này luôn là số nguyên.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $t$ ($1 \le t \le 100$) — số lượng bộ dữ liệu. Mô tả các bộ dữ liệu như sau:

Dòng đầu tiên của mỗi bộ dữ liệu chứa ba số nguyên $n, m$ và $k$ ($1 \le n, m \le 5000, n \cdot m \le 2 \cdot 10^4, 1 \le k \le 10^5$) — độ dài của mảng $a$, số lượng thao tác tối đa, và số được cộng vào $a_i$ mỗi lần, tương ứng.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — các phần tử của mảng $a$.

Đảm bảo rằng tổng của $n \cdot m$ trên tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^4$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra $m$ số nguyên trên một dòng, số thứ $p$ biểu thị phương sai nhỏ nhất có thể của $a$ khi thực hiện đúng $p$ thao tác, đã nhân với $n^2$.

Ví dụ

Dữ liệu vào 1

9
3 2 1
1 2 2
3 2 2
1 2 2
10 2 1
10 1 1 1 1 10 1 1 1 1
6 8 2
1 1 4 5 1 3
8 8 7
20 43 24 2 4 3 20 43
8 8 3
20 43 24 2 4 3 20 43
10 12 1
5 3 3 5 4 1 8 1 1 1
13 10 100000
1 2 3 4 5 6 7 8 9 10 11 5 4
10 5 10000
2308 9982 4435 3310 100000 9 7 8100 1919 100000

Dữ liệu ra 1

0 0
2 2
1161 1024
53 21 21 5 5 5 5 5
10608 6912 4448 3104 1991 1312 535 304
13248 11184 9375 7815 6447 5319 4383 3687
385 316 269 224 181 156 124 101 80 56 41 29
1486 1486 1486 1486 1486 1486 1486 1486 1486 1486
134618047140 119919447140 107020847140 93922247140 82623000000

Ghi chú

Trong bộ dữ liệu đầu tiên:

• Với $p = 1$, bạn có thể thực hiện thao tác trên $[1, 1]$, thay đổi $a$ từ $[1, 2, 2]$ thành $[2, 2, 2]$. Vì tất cả các phần tử đều bằng nhau, phương sai bằng $0$.
• Với $p = 2$, bạn có thể thực hiện thao tác trên $[1, 3]$ và sau đó là $[1, 1]$, thay đổi $a$ từ $[1, 2, 2]$ thành $[2, 3, 3]$ rồi thành $[3, 3, 3]$. Vì tất cả các phần tử đều bằng nhau, phương sai bằng $0$.

Trong bộ dữ liệu thứ hai, một số lựa chọn tối ưu có thể là:

• $p = 1: [1, 2, 2] \to [3, 2, 2]$;
• $p = 2: [1, 2, 2] \to [1, 4, 4] \to [3, 4, 4]$.

Trong bộ dữ liệu thứ ba, một số lựa chọn tối ưu có thể là:

• $p = 1: [10, 1, 1, 1, 1, 10, 1, 1, 1, 1] \to [10, 2, 2, 2, 2, 11, 2, 2, 2, 2]$;
• $p = 2: [10, 1, 1, 1, 1, 10, 1, 1, 1, 1] \to [10, 1, 1, 1, 1, 10, 2, 2, 2, 2] \to [10, 2, 2, 2, 2, 10, 2, 2, 2, 2]$.

Trong bộ dữ liệu thứ tám, lựa chọn tối ưu cho mọi $p$ là thực hiện thao tác trên toàn bộ mảng $p$ lần.