Kevin은 최근 분산의 정의를 배웠습니다. 길이가 $n$인 배열 $a$에 대하여, $a$의 분산은 다음과 같이 정의됩니다.

• $x = \frac{1}{n} \sum_{i=1}^{n} a_i$라고 합시다. 즉, $x$는 배열 $a$의 평균입니다.
• 그러면 $a$의 분산은 다음과 같습니다. $$V(a) = \frac{1}{n} \sum_{i=1}^{n} (a_i - x)^2$$

이제 Kevin은 $n$개의 정수로 이루어진 배열 $a$와 정수 $k$를 줍니다. 당신은 $a$에 대해 다음 연산을 수행할 수 있습니다.

• 구간 $[l, r]$ ($1 \le l \le r \le n$)을 선택한 다음, 각 $l \le i \le r$에 대해 $a_i$를 $k$만큼 증가시킵니다.

각 $1 \le p \le m$에 대하여, 정확히 $p$번의 연산을 수행한 후의 최소 분산을 구해야 합니다. 각 $p$는 독립적으로 고려합니다.

단순함을 위해, 결과에 $n^2$을 곱한 값만 출력하면 됩니다. 결과는 항상 정수임이 증명될 수 있습니다.

입력

각 테스트 케이스는 여러 개의 테스트를 포함합니다. 입력의 첫 번째 줄에는 테스트 케이스의 수 $t$ ($1 \le t \le 100$)가 주어집니다. 이어지는 각 테스트 케이스에 대한 설명이 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 세 정수 $n, m, k$ ($1 \le n, m \le 5000, n \cdot m \le 2 \cdot 10^4, 1 \le k \le 10^5$)가 주어지며, 이는 각각 배열 $a$의 길이, 최대 연산 횟수, 그리고 매번 $a_i$에 더하는 수를 의미합니다.

두 번째 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$)이 주어지며, 이는 배열 $a$의 원소들입니다.

모든 테스트 케이스에 대해 $n \cdot m$의 합은 $2 \cdot 10^4$을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 $m$개의 정수를 한 줄에 출력합니다. $p$번째 정수는 정확히 $p$번의 연산을 수행했을 때의 최소 분산에 $n^2$을 곱한 값입니다.

예제

입력 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

출력 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 82623447140

참고

첫 번째 테스트 케이스:

• $p = 1$일 때, $[1, 1]$에 연산을 수행하여 $a$를 $[1, 2, 2]$에서 $[2, 2, 2]$로 바꿀 수 있습니다. 모든 원소가 같으므로 분산은 $0$입니다.
• $p = 2$일 때, $[1, 3]$에 연산을 수행한 후 $[1, 1]$에 연산을 수행하여 $a$를 $[1, 2, 2]$에서 $[2, 3, 3]$으로, 다시 $[3, 3, 3]$으로 바꿀 수 있습니다. 모든 원소가 같으므로 분산은 $0$입니다.

두 번째 테스트 케이스에서 가능한 최적의 선택은 다음과 같습니다:

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

세 번째 테스트 케이스에서 가능한 최적의 선택은 다음과 같습니다:

• $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]$.

네 번째 테스트 케이스에서 가능한 최적의 선택은 다음과 같습니다:

• $p = 1: [1, 1, 4, 5, 1, 3] \to [1, 1, 6, 7, 3, 5]$.

다섯 번째 테스트 케이스에서 가능한 최적의 선택은 다음과 같습니다:

• $p = 1: [20, 43, 24, 2, 4, 3, 20, 43] \to [20, 43, 24, 9, 11, 10, 27, 50]$.

여섯 번째 테스트 케이스에서 가능한 최적의 선택은 다음과 같습니다:

• $p = 1: [20, 43, 24, 2, 4, 3, 20, 43] \to [20, 43, 24, 5, 7, 6, 23, 46]$.

일곱 번째 테스트 케이스에서 가능한 최적의 선택은 다음과 같습니다:

• $p = 1: [5, 3, 3, 5, 4, 1, 8, 1, 1, 1] \to [5, 3, 3, 5, 4, 2, 9, 2, 2, 2]$.

여덟 번째 테스트 케이스에서 가능한 최적의 선택은 다음과 같습니다:

• $p = 1: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 5, 4] \to [100001, 100002, 100003, 100004, 100005, 100006, 100007, 100008, 100009, 100010, 100011, 5, 4]$.

아홉 번째 테스트 케이스에서 모든 $p$에 대한 최적의 선택은 전체 배열에 $p$번 연산을 수행하는 것입니다.