Аллен и Бесси играют в простую игру с числами. Они оба знают функцию \(f: \{0, 1\}^n \to \mathbb{R}\), т.е. функцию, которая принимает \(n\) бинарных аргументов и возвращает вещественное значение. В начале игры все переменные \(x_1, x_2, \dots, x_n\) равны \(-1\). В каждом раунде независимо с равной вероятностью ходит Аллен или Бесси. Ход состоит из выбора такого \(i\), что \(x_i = -1\) и либо установке \(x_i \to 0\) либо \(x_i \to 1\).
После \(n\) раундов все переменные установлены, и результатом игры становится величина \(f(x_1, x_2, \dots, x_n)\). Аллен хочет максимизировать результат, а Бесси — минимизировать его.
Ваша задача — помочь Аллену и Бесси определить математическое ожидание результата игры! Они сыграют \(r+1\) раз, и между играми будет меняться ровно одно значение \(f\). Другими словами, между играми \(i\) и \(i+1\) для \(1 \le i \le r\), будет изменено значение \(f(z_1, \dots, z_n) \to g_i\) для некоторого набора \((z_1, \dots, z_n) \in \{0, 1\}^n\). Найдите математическое ожидание результата в начале, а также после каждого изменения.
Выходные данные
Выведите \(r+1\) строку, в \(i\)-й строку должно находиться математическое ожидание результата \(f\) в \(i\)-й игре. Ваш ответ должен иметь абсолютную или относительную ошибку не более \(10^{-6}\).
Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет зачтен, если \(\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}\).
Примечание
Рассмотрим второй пример. Если первым сходит Аллен, то он положит \(x_1 \to 1\), поэтому результат будет \(3\). Если сходит Бесси, то она положит \(x_1 \to 0\), и результат будет равен \(2\). Поэтому ответ равен \(2.5\).
В третьем примере результатом игры всегда будет \(1\) независимо от игры Аллен и Бесси.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
0 1 2 3
2 5
0 4
|
1.500000
2.250000
3.250000
|
|
2
|
1 0
2 3
|
2.500000
|
|
3
|
2 0
1 1 1 1
|
1.000000
|