Little Q 的工厂最近购买了 $m$ 件新设备，编号为 $1, 2, \dots, m$。

工厂里有 $n$ 名工人，编号为 $1, 2, \dots, n$。每名工人最多只能分配到一件设备，且每件设备最多只能分配给一名工人。如果 Little Q 将第 $i$ 名工人分配给第 $j$ 件设备，他需要支付 $a_i \times j^2 + b_i \times j + c_i$ 美元。

现在请对于每一个 $k$ ($1 \le k \le n$)，找出 $k$ 对工人和设备的分配方案，使得这 $k$ 名工人的总成本最小。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 50, n \le m \le 10^8$)，分别表示工人的数量和设备的数量。

接下来的 $n$ 行，每行包含三个整数 $a_i, b_i, c_i$ ($1 \le a_i \le 10, -10^8 \le b_i \le 10^8, 0 \le c_i \le 10^{16}, b_i^2 \le 4a_ic_i$)，描述一名工人。

输出格式

对于每个测试用例，输出一行，包含 $n$ 个整数，其中第 $k$ 个整数 ($1 \le k \le n$) 表示分配 $k$ 对工人和设备时的最小总成本。

样例

输入格式 1

1
3 5
2 3 10
2 -3 10
1 -1 4

输出格式 1

4 15 37