C. Loyalty
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
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.

Input

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

Output

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.

Example
Input
7
10 2
1 2 1 2 1 2 1 2 1 2
5 10
2 2 2 2 5
11 23
5 5 22 1 21 2 10 3 1 1 2
1 1
1
1 17
11
3 100
44 32 1
16 100500
42801 73112 95296 68791 42217 21871 29316 84405 24273 42894 63370 53473 57156 61369 80 27290
Output
12
1 2 2 2 2 2 1 1 1 1
5
2 2 2 2 5
53
1 1 5 2 1 2 5 3 10 21 22
1
1
0
11
0
44 32 1
503499
53473 42894 80 57156 42801 61369 42217 63370 29316 68791 27290 73112 24273 84405 21871 95296
Note

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.