20605번 - New Equipments 다국어

문제

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.

입력

The first line contains a single integer $T$ (1ドル \leq T \leq 10$), the number of test cases. For each test case:

The first line 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,ドル $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$) describing a worker.

출력

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

제한

힌트