G. Chocolate Volcano
time limit per test
1 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Jolany is having her birthday again and this time she'll finally get her favorite cake to share with her friends and family: Chocolate Volcano!

A Chocolate Volcano can be represented as a set of $$$n$$$ points on the plane with increasing coordinates over the $$$X$$$-axis, which when connected form the upper hill shape of the Volcano. The first point and the last point are vertically connected to the base of where the cake lays ( corresponding to the $$$Y$$$-axis ).

Since Jolany is planning on hosting $$$m$$$ attendees at her party, she wants to cut her cake into exactly $$$m$$$ pieces of the same area so that each attendee receives the same amount of cake. For this, she'll do $$$m-1$$$ vertical cuts, as this will guarantee that each guest receives a mini Chocolate Volcano on their own.

Can you help Jolany to find where these cutting points must be performed?

Input

The first line of the input contains two integers $$$n,m$$$ ( $$$2$$$ $$$\leq$$$ $$$n,m$$$ $$$\leq$$$ $$$2$$$x$$$10^5$$$ ).

The second line contains $$$n$$$ integers, the $$$i-th$$$ of them corresponding to $$$x_i$$$, which is the $$$x$$$ coordinate of the $$$i-th$$$ point. The third line contains $$$y$$$ coordinates of the $$$n$$$ points in the same format. The coordinates of the points are positive integers up to $$$10^9$$$. For $$$2$$$ $$$\leq$$$ $$$i$$$ $$$\leq$$$ $$$n$$$, it's guaranteed that $$$x_{i-1}$$$ $$$ \lt $$$ $$$x_i$$$.

Output

Print $$$m-1$$$ integers in increasing order representing the $$$x$$$ coordinates of where the cuts must be performed. Your answer will be considered correct if the absolute or relative error is at most $$$10^{-6}$$$.

Examples
Input
5 2
2 5 6 7 10
4 5 4 5 4
Output
6.000000000000
Input
2 3
5 10
5 5
Output
6.666666666667 8.333333333333
Note

Illustration of the first sample; the red line shows where the cut must be performed in order to divide the cake into two equal parts.