题目描述

罗马尼亚国家队教练正在从 $N$ 名球员中挑选若干人组成一个非空队伍。第 $i$ 名球员有一个价值 $a_i$。

一个队伍的总价值定义为队伍中所有球员价值之和。一个队伍的傲慢系数定义为队伍中最大球员价值与最小球员价值之差，即

特别地，如果队伍只有一名球员，则傲慢系数为 $0$。

给定最大允许总价值 $V_{\max}$。对于每个 $X\in[1,V_{\max}]$，你需要求出是否存在一个非空球员集合，使其总价值恰好为 $X$；若存在，输出所有这类队伍中最小可能的傲慢系数；若不存在，输出 -1。

输入格式

第一行包含一个整数 $T$，表示测试组数。

接下来有 $T$ 组数据。每组数据格式如下：

第一行包含两个整数 $N,V_{\max}$。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$，表示每名球员的价值。

输出格式

对于每组数据输出一行，包含 $V_{\max}$ 个整数。

第 $i$ 个整数表示总价值恰好为 $i$ 的队伍的最小傲慢系数；若不存在这样的队伍，则输出 -1。

数据范围

• $1\le T\le 2$；
• $1\le N\le 4000$；
• $1\le V_{\max}\le 8000$；
• $1\le a_i\le V_{\max}$。

子任务性质：

• 约 $20\%$ 的测试满足 $N\le 20$；
• 约 $40\%$ 的测试满足 $N\le 100$ 且 $V_{\max}\le 100$；
• 约 $50\%$ 的测试满足 $N\le 300$ 且 $V_{\max}\le 300$。

样例

输入

2
4 7
5 2 3 4
5 15
1 8 2 3 6

输出

-1 0 0 0 0 2 1
0 0 0 2 1 0 5 0 3 5 4 5 6 2 7

样例解释

第一组数据中：

• 总价值 $1$ 无法得到，所以答案为 -1；
• 总价值 $2,3,4,5$ 可以由单个球员得到，所以傲慢系数为 $0$；
• 总价值 $6$ 可以由价值 $2$ 和 $4$ 的球员得到，傲慢系数为 $2$；
• 总价值 $7$ 可以由 $(2,5)$ 或 $(3,4)$ 得到，其中 $(3,4)$ 的傲慢系数更小，为 $1$。