由于苏联过去奉行无神论,二十世纪的大部分时间俄罗斯都没有正式庆祝圣诞节。结果,俄罗斯圣诞节和新年的传统融入了一项庆祝新年的活动,但包括圣诞树、圣诞老人般的“霜爷爷”、礼物以及全国各地的大型家庭聚会和晚宴。新年时栽一棵树并将其安装在房子里是一种传统。通常全家人都会在除夕夜装饰圣诞树。我们希望Codeforces是一个充满爱的大家庭,所以在这个问题中我们也将装饰一棵树。
那么,我们的装饰由n块组成,每块都是一张彩纸,它的边框是一条特殊形状的闭合折线。如图所示,这些碎片一件接一件地排列。第 i 段是一条经过以下点的折线:(0, 0)、(0, y0)、(1, y1)、(2, y2)、...、(k, yk)、(k, 0)。每块的宽度等于k。
左图显示了装饰,右图显示了其组成的各个部分。
编号 1 的部件(图中红色显示)是外部部件(我们完全看到它),编号 2 的部件(显示黄色)紧随其后(我们看不到它完全,因为它被第一块部分封闭),依此类推。程序员们都是好奇心很强的人,所以当我们在新年树上挂上装饰品的那一刻,我们就开始想:人们能看到每件装饰品的哪些区域?
输入
第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 300)。以下 n 行中的每一行都包含 k + 1 个整数——折线的描述。如果第 i 条线包含整数 yi, 0, yi, 1, ..., yi, k,则表示第 i 条折线经过点 (0, 0)、(0, yi, 0)、(1, yi, 1)、(2, yi, 2)、...、(k, yi, k)、(k, 0) (1 ≤ yi, j ≤ 1000)。
输出
打印 n 个实数 — 对于每条折线,其可见部分的面积。
如果答案的相对或绝对误差不超过 10 - 4,则认为答案是正确的。
示例
输入 #1
2 2 2 1 2 1 2 1
输出 #1
3.000000000000 0.500000000000
输入 #2
1 1 1 1
输出 #2
1.000000000000
输入 #3
4 1 2 7 7 2 5 5 6 4
输出 #3
4.500000000000 1.250000000000 0.050000000000 0.016666666667