В межгалактической империи Баблдом \(N\) планет, некоторые пары которых напрямую соединены двусторонними кротовыми норами. Всего есть \(N-1\) кротовых нор. Кротовые норы имеют чрезвычайно важное значение в Баблдоме: множество планет в Баблдоме считается межгалактическим королевством, если и только если между любыми двумя планетами в этом множестве есть путь, использующий только кротовые норы. Известно, что весь Баблдом является королевством. Другими словами, сеть планет и кротовых нор является деревом.
На Баблдом напал мощный противник, владеющий технологией телепортации. Враг атакует каждую ночь, а правительство Баблдома возвращает все планеты под свой контроль днем. В течение одной ночи враг атакует каждую планету Баблдома один раз, но некоторые планеты более стойкие, чем другие. Планеты пронумерованы \(0,1,…,N-1\), и планета номер \(i\) будет захвачена врагом в вероятностью \(p_i\). Перед каждой атакой (в том числе перед первой) правительство меняет вероятность захвата одной планеты (возможно как в большую, так и в меньшую сторону).
Правительство Баблдома заинтересовано в следующем вопросе: каково математическое ожидание межгалактических королевств, на которые Баблдом распадется после каждой из атак врага (и до того, как правительство вернет планеты под свой контроль)? Другими словами, найдите математическое ожидание количества компонент связности после каждой атаки.
Выходные данные
Выведите \(Q\) чисел, каждое из которых означает математическое ожидание числа королевств, которые могут получиться после каждой из атак противника. Ваш ответ будет зачтен, если его абсолютная или относительная ошибка не превосходит \(10^{-4}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
0.50 0.29 0.49 0.95 0.83
2 3
0 3
3 4
2 1
3
4 0.66
1 0.69
0 0.36
|
1.68040
1.48440
1.61740
|