CF1471A.Strange Partition

You are given an array $a$ of length $n$, and an integer $x$. You can perform the following operation as many times as you would like (possibly zero): replace two adjacent elements of the array by their sum. For example, if the initial array was $[3, 6, 9]$, in a single operation one can replace the last two elements by their sum, yielding an array $[3, 15]$, or replace the first two elements to get an array $[9, 9]$. Note that the size of the array decreases after each operation.

The beauty of an array $b=[b_1, \ldots, b_k]$ is defined as $\sum_{i=1}^k \left\lceil \frac{b_i}{x} \right\rceil$, which means that we divide each element by $x$, round it up to the nearest integer, and sum up the resulting values. For example, if $x = 3$, and the array is $[4, 11, 6]$, the beauty of the array is equal to $\left\lceil \frac{4}{3} \right\rceil + \left\lceil \frac{11}{3} \right\rceil + \left\lceil \frac{6}{3} \right\rceil = 2 + 4 + 2 = 8$.

Please determine the minimum and the maximum beauty you can get by performing some operations on the original array.

给你一个长度为 $n$ 的数组 $a$ 和一个整数 $x$。你可以执行以下操作任意多次（包括零次）：将数组中两个相邻的元素替换为它们的和。例如，若初始数组为 $[3, 6, 9]$，则一次操作可以将后两个元素替换为其和，得到数组 $[3, 15]$；也可以将前两个元素替换为其和，得到数组 $[9, 9]$。注意：每次操作后，数组长度都会减小。

数组 $b=[b_1, \ldots, b_k]$ 的**美观度（beauty）**定义为 $\sum_{i=1}^k \left\lceil \frac{b_i}{x} \right\rceil$，即对每个元素除以 $x$ 后向上取整，再将所有结果相加。例如，当 $x = 3$、数组为 $[4, 11, 6]$ 时，该数组的美观度为 $\left\lceil \frac{4}{3} \right\rceil + \left\lceil \frac{11}{3} \right\rceil + \left\lceil \frac{6}{3} \right\rceil = 2 + 4 + 2 = 8$。

请确定：对原始数组执行若干次上述操作后，所能得到的最小和最大美观度分别是多少。

The first input line contains a single integer $t$ — the number of test cases ($1 \le t \le 1000$).

The first line of each test case contains two integers $n$ and $x$ ($1 \leq n \leq 10^5$, $1 \leq x \leq 10^9$).

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$), the elements of the array $a$.

It is guaranteed that the sum of values of $n$ over all test cases does not exceed $10^5$.

第一行输入包含一个整数 $t$ —— 测试用例的数量（$1 \le t \le 1000$）。

每个测试用例的第一行包含两个整数 $n$ 和 $x$（$1 \leq n \leq 10^5$，$1 \leq x \leq 10^9$）。

接下来的一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），即数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

For each test case output two integers — the minimal and the maximal possible beauty.

对于每个测试用例，输出两个整数——最小和最大的可能美观度。

In the first test case the beauty of the array does not change if we perform any operations.

In the second example we can leave the array unchanged to attain the maximum beauty, and to get the minimum beauty one can replace two elements $4$ and $11$ with their sum, yielding an array $[6, 15]$, which has its beauty equal to $7$.

在第一个测试用例中，无论执行任何操作，数组的“美观度”均保持不变。

在第二个示例中，我们可以保持数组不变以获得最大美观度；而为了获得最小美观度，可将两个元素 $4$ 和 $11$ 替换为它们的和，得到数组 $[6, 15]$，其美观度为 $7$。