Problem9831--魔法学院

9831: 魔法学院

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 512 MiB

Description

在一个虚拟现实世界中,有 $n$ 个魔法师,每个魔法师都能施展一种特殊的魔法。这种魔法的威力可以用一个数学公式来表示:$P_i(x)=A_ix^2+B_ix+C_i$,其中 $x$ 是施法者的能量水平,一个正整数。每个魔法师的魔法公式都有特定的系数 $A_i,B_i,C_i$。
你作为魔法学院的管理员,需要计算这些魔法师施展魔法的威力。
你的任务是找出所有魔法公式在所有可能的能量水平下产生的威力值中最小的 $m$ 个值。

Input

第一行输入两个正整数 $n,m\ (1≤n,m≤10^5)$。
以下 $n$ 行,每行三个正整数,分别表示 $A_i,B_i,C_i$。输入数据保证 $1≤A_i≤10,\ 1≤B_i≤100,\ 1 \leq C_i≤10000$。

Output

输出一行,包含 $n$ 个魔法公式在所有可能的能量水平下产生的威力值中最小的 $m$ 个值。这些值应该按升序排列,用空格隔开。

Sample 1 Input

3 10
4 5 3
3 4 5
1 7 1

Sample 1 Output

9 12 12 19 25 29 31 44 45 54

HINT

相同题目:ZMOJ

Source/Category