New Equipments

Problem Description

Little Q's factory recently purchased $m$ pieces of new equipment, labeled by $1,2,\dots,m$. There are $n$ workers in the factory, labeled by $1,2,\dots,n$. Each worker can be assigned to no more than one piece of equipment, and no piece of equipment can be assigned to multiple workers. If Little Q assigns the $i$-th worker to the $j$-th piece of equipment, he will need to pay $a_i\times j^2+b_i\times j+c_i$ dollars. Now please for every $k$ ($1\leq k\leq n$) find $k$ pairs of workers and pieces of equipment, then assign workers to these pieces of equipment, such that the total cost for these $k$ workers is minimized.

Input

The first line of the input contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each case, the first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 50$, $n\leq m\leq 10^8$), denoting the number of workers and the number of pieces of equipment. Each of the following $n$ lines contains three integers $a_i,b_i$ and $c_i$ ($1\leq a_i\leq 10$, $-10^8\leq b_i\leq 10^8$, $0\leq c_i\leq 10^{16}$, $b_i^2\leq 4a_ic_i$), denoting a worker.

Output

For each test case, output a single line containing $n$ integers, the $k$-th ($1\leq k\leq n$) of which denoting the minimum possible total cost for $k$ pairs of workers and pieces of equipment.

Sample Input

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

Sample Output

4 15 37

Source

2020 Multi-University Training Contest 2