CF2161C.Loyalty

No Loyalty No Royalty (c)

You are a customer in a store and want to buy $n$ items. Each item $i$ has a price $a_i$ such that $1 \leq a_i \leq X$, where $X$ is a loyalty factor.

Your loyalty level in the store is defined as $\lfloor {S \over X} \rfloor$, where $S$ is the total cost of items purchased so far. Initially, $S = 0$.

If you buy an item with price $p$ and your loyalty level increases as a result of this purchase, you earn $p$ bonus points.

Your task is to find the maximum number of bonus points you can earn by choosing an optimal order of purchase for the items.

无忠诚，无特权（c）

你是一家商店的顾客，想要购买 $n$ 件商品。每件商品 $i$ 的价格为 $a_i$，满足 $1 \leq a_i \leq X$，其中 $X$ 是忠诚度因子。

你在该商店的忠诚度定义为 $\lfloor {S \over X} \rfloor$，其中 $S$ 是截至目前已购商品的总花费。初始时，$S = 0$。

若你购买一件价格为 $p$ 的商品，且此次购买导致你的忠诚度提升，则你将获得 $p$ 点奖励积分。

你的任务是：通过选择商品购买顺序，使得所获奖励积分总数最大。请计算该最大值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2 \cdot 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ ($1 \leq n \leq 10^5$) and $X$ ($1 \leq X \leq 10^9$) — the number of items and the loyalty factor.

The second line of each test case contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \leq a_i \leq X$) — the prices of the items.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 2 \cdot 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$（$1 \leq n \leq 10^5$）和 $X$（$1 \leq X \leq 10^9$）——分别表示物品数量和忠诚度因子。

每个测试用例的第二行包含 $n$ 个整数 $a_1$, $a_2$, $\ldots$, $a_n$（$1 \leq a_i \leq X$）——表示各物品的价格。

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

For each test case, output two lines.

The first line should contain a single integer — the maximum number of bonus points that can be earned.

The second line should contain $n$ integers — the prices of the items in an order of purchase that maximizes the number of bonus points.

If there are several orders that maximize the number of bonus points, you can output any of them.

对于每个测试用例，输出两行。

第一行应包含一个整数——能够获得的最大奖励积分数量。

第二行应包含 $n$ 个整数——一种能最大化奖励积分数量的商品购买顺序对应的价格。

如果存在多种能最大化奖励积分数量的购买顺序，输出其中任意一种即可。

In the first test case:

1. After buying the first item $S = 1$, loyalty level is 0;
2. After buying the second item $S = 3$, this increases loyalty level to $1$ and earns $2$ bonus points;
3. After buying the third item $S = 5$, this increases loyalty level to $2$ and earns $2$ bonus points;
4. After buying the fourth item $S = 7$, this increases loyalty level to $3$ and earns $2$ bonus points;
5. After buying the fifth item $S = 9$, this increases loyalty level to $4$ and earns $2$ bonus points;
6. After buying the sixth item $S = 11$, this increases loyalty level to $5$ and earns $2$ bonus points;
7. After buying the seventh item $S = 12$, this increases loyalty level to $6$ and earns $1$ bonus point;
8. After buying the eighth item $S = 13$;
9. After buying the ninth item $S = 14$, this increases loyalty level to $7$ and earns $1$ bonus point;
10. After buying the tenth item $S = 15$.

Overall we got $12$ bonus points.

In the second test case:

1. After buying the first four items $S = 8$, loyalty level is 0;
2. After buying the last item $S = 13$, this increases loyalty level to $1$ and earns $5$ bonus points.

In the third test case:

1. After buying the first eight items $S = 20$, loyalty level is 0;
2. After buying the ninth item $S = 30$, this increases loyalty level to $1$ and earns $10$ bonus points;
3. After buying the tenth item $S = 51$, this increases loyalty level to $2$ and earns $21$ bonus points;
4. After buying the eleventh item $S = 73$, this increases loyalty level to $3$ and earns $22$ bonus points.

在第一个测试用例中：

1. 购买第一件商品后，$S = 1$，忠诚度等级为 $0$；
2. 购买第二件商品后，$S = 3$，忠诚度等级提升至 $1$，并获得 $2$ 点奖励积分；
3. 购买第三件商品后，$S = 5$，忠诚度等级提升至 $2$，并获得 $2$ 点奖励积分；
4. 购买第四件商品后，$S = 7$，忠诚度等级提升至 $3$，并获得 $2$ 点奖励积分；
5. 购买第五件商品后，$S = 9$，忠诚度等级提升至 $4$，并获得 $2$ 点奖励积分；
6. 购买第六件商品后，$S = 11$，忠诚度等级提升至 $5$，并获得 $2$ 点奖励积分；
7. 购买第七件商品后，$S = 12$，忠诚度等级提升至 $6$，并获得 $1$ 点奖励积分；
8. 购买第八件商品后，$S = 13$；
9. 购买第九件商品后，$S = 14$，忠诚度等级提升至 $7$，并获得 $1$ 点奖励积分；
10. 购买第十件商品后，$S = 15$。

总计获得 $12$ 点奖励积分。

在第二个测试用例中：

1. 购买前四件商品后，$S = 8$，忠诚度等级为 $0$；
2. 购买最后一件商品后，$S = 13$，忠诚度等级提升至 $1$，并获得 $5$ 点奖励积分。

在第三个测试用例中：

1. 购买前八件商品后，$S = 20$，忠诚度等级为 $0$；
2. 购买第九件商品后，$S = 30$，忠诚度等级提升至 $1$，并获得 $10$ 点奖励积分；
3. 购买第十件商品后，$S = 51$，忠诚度等级提升至 $2$，并获得 $21$ 点奖励积分；
4. 购买第十一商品后，$S = 73$，忠诚度等级提升至 $3$，并获得 $22$ 点奖励积分。