На столе стоит \(n\) стаканов, пронумерованных \(1, \ldots, n\). В стакан \(i\) может поместиться до \(a_i\) единиц объёма воды, и сейчас этот стакан содержит \(b_i\) единиц воды.
Вы хотите выбрать \(k\) стаканов и собрать в них как можно больше воды. Для этого вы можете сколько угодно раз переливать воду из одного стакана в другой. Однако, из-за очень неудобной формы стаканов (а вовсе не из-за вашей неуклюжести), каждый раз, когда вы пытаетесь перелить любой объём воды, половина этого объёма проливается на пол.
Формально, пусть стакан \(i\) сейчас содержит \(c_i\) единиц воды, а стакан \(j\) содержит \(c_j\) единиц воды. Пускай вы пытаетесь переместить \(x\) единиц из стакана \(i\) в стакан \(j\) (разумеется, \(x\) не может превосходить \(c_i\)). Тогда \(x / 2\) единиц воды проливается на пол. После переливания стакан \(i\) будет содержать \(c_i - x\) единиц воды, а стакан \(j\) будет содержать \(\min(a_j, c_j + x / 2)\) единиц (лишняя вода, которая не помещается в стакан, также проливается).
Для каждого переливания вы можете произвольно выбрать, из какого стакана \(i\) в какой стакан \(j\) надо переливать, а также переливаемый объём \(x\) может быть произвольным вещественным числом.
Для каждого \(k = 1, \ldots, n\) определите максимально возможный объём воды, который можно собрать в \(k\) произвольно выбранных стаканах после нуля или более переливаний между стаканами.
Выходные данные
Выведите \(n\) вещественных чисел — наибольший объём воды, который можно собрать в \(1, \ldots, n\) стаканах соответственно. Ваш ответ будет принят, если каждое число находится в пределах \(10^{-9}\) абсолютной или относительной погрешности от точного ответа.