题目描述

现在差不多该为 Whacker Cup 的获胜者颁奖了！在大多数体育项目中，前三名会站上领奖台。不过，组织者认为每一位参加这场精彩赛事的人都是赢家，因此所有 $N$ 名参赛者都应该站上领奖台。

组织者想要用等尺寸的砖块建造一个由 $N$ 个平台组成的领奖台，这些平台排成一排，编号为 $1..N$。对于第 $i$ 个平台，组织者需要决定其高度为 $x_i$ 块砖。为了体现名次高低，平台高度必须是非递增且非负的，即：

$$x_1\ge x_2\ge \cdots \ge x_N\ge 0.$$

虽然砖块尺寸相同，但它们拥有不同的“amazingness”（精彩度）。第 $i$ 个平台只能使用精彩度为 $A_i$ 的砖块建造。最终领奖台的精彩度定义为所有使用砖块的精彩度之和：

$$A_1\cdot x_1+A_2\cdot x_2+\cdots +A_N\cdot x_N.$$

组织者希望这个值至少为 $M$。同时，由于精彩的砖块很昂贵，他们希望最小化使用的砖块总数。

形式化地，一个“精彩”的领奖台由序列 $[x_1,\ldots,x_N]$ 给出，需要满足：

$$x_1\ge x_2\ge \cdots \ge x_N\ge 0,$$ $$A_1\cdot x_1+A_2\cdot x_2+\cdots +A_N\cdot x_N\ge M,$$

并且

$$x_1+x_2+\cdots+x_N$$

尽可能小。

请你找出这样一个精彩的领奖台。若存在多个答案，输出任意一个均可。

数据范围

• $1 \le T \le 100$
• $1 \le N \le 1000$
• $1 \le M \le 10^{12}$
• $1 \le A_i \le 10^{12}$
• 满足 $N>500$ 的测试用例最多有 $11$ 个。

输入格式

输入第一行包含一个整数 $T$，表示测试用例数。

每个测试用例中：

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数 $A_1,\ldots,A_N$。

输出格式

对于第 $i$ 个测试用例，输出：

第一行：

Case #i: ans

其中 $ans$ 是满足要求的最少砖块总数。

第二行输出 $N$ 个空格分隔的整数 $x_1,\ldots,x_N$，表示各平台高度。

若有多个最优答案，输出任意一个即可。

样例输入

6
3 27
3 5 1
3 18
1 9 6
3 28
3 5 1
5 100
7 6 16 9 3
10 45
1 2 4 8 1 2 60 3 5 7
8 230
5 11 12 15 13 7 23 7

样例输出

Case #1: 7
4 3 0
Case #2: 4
2 2 0
Case #3: 8
4 4 0
Case #4: 11
5 3 3 0 0
Case #5: 7
1 1 1 1 1 1 1 0 0 0
Case #6: 20
3 3 3 3 3 3 2 0

样例解释

第一个样例中，$N=3$，$M=27$，砖块类型的精彩度为 $A=[3,5,1]$。一种可行答案是 $x=[4,3,0]$，它满足 $4\ge 3\ge 0$，且

$$3\times 4+5\times 3+1\times 0=27\ge M=27,$$

同时总砖块数 $4+3+0=7$ 最小。

第二个样例中，$N=3$，$M=18$。一种使用最少 $4$ 块砖的答案如下图所示：

第四个样例中，$N=5$，$M=100$。一种使用最少 $11$ 块砖的答案为样例输出中的 $[5,3,3,0,0]$。