Джонни участвует в карнавале, на котором проводится n лотерей. В ходе лотереи с номером i разыгрывается приз ценностью pi. Каждый участник покупает сколько-то лотерейных билетов, а затем произвольным образом распределяет их между n лототронами. В конце карнавала из каждого лототрона случайным образом достают один билет, и его обладатель выигрывает соответствующий приз. Один человек вполне может выиграть и несколько призов с разных лототронов.
Правила карнавальных лотерей запрещают одному участнику владеть более чем половиной билетов в лототроне, то есть никто не может положить в один лототрон больше билетов, чем все остальные участники вместе взятые. В начале лотереи организаторы кладут в каждый лототрон один билет и не извлекают его оттуда до конца карнавала.
Джонни купил t лотерейных билетов и теперь думает, как же распределить их по лототронам. Сейчас в i-м лототроне находится li билетов. Джонни наблюдает, как остальные участники лотереи время от времени меняют свои решения и перемещают по одному билету. После каждого такого перемещения Джонни хочет знать максимальное математическое ожидание выигрыша, которого он может добиться, разместив билеты оптимальным способом. Разумеется, Джонни не может использовать больше чем t билетов и нарушать правила лотереи, помещая в один лототрон больше билетов, чем все остальные участники лотереи вместе взятые.
Выходные данные
Выведите q строк, каждая строка должна содержать одно вещественное число — максимально возможное математическое ожидание выигрыша Джонни после выполнения первых k изменений. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.
А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если 
.
Примечание
В первом примере у Джонни есть только один билет. Призы имеют ценность 4 и 5, а в лототронах изначально находятся 1 и 2 билета соответственно. После первого изменения в каждом лототроне лежит по 2 билета, так что если Джонни поместит свой билет во второй лототрон, то математическое ожидание выигрыша будет равно 
. После второго изменения во втором лототроне находится три билета, так что наиболее выгодной стратегией будет положить билет в первый лототрон — математическое ожидание выигрыша равно 
. После третьего изменения Джонни должен положить свой билет в первый лототрон, тогда математическое ожидание выигрыша равно 
.
Во втором примере у Джонни больше билетов, чем он может использовать по правилам карнавальной лотереи. Например, после первого изменения, в лототронах лежат 7, 6 и 6 билетов соответственно, так что Джонни может использовать только 19 своих билетов и выиграть каждый приз с вероятностью 
.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1 3
4 5
1 2
1 1
1 2
2 1
|
1.666666667
1.333333333
2.000000000
|
|
2
|
3 20 5
6 8 10
6 6 6
1 1
1 2
1 3
2 3
2 3
|
12.000000000
12.000000000
11.769230769
12.000000000
12.000000000
|