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?
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$$$.
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}$$$.
5 22 5 6 7 104 5 4 5 4
6.000000000000
2 35 105 5
6.666666666667 8.333333333333
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.