Кролик Стьюи исследует новую параллельную вселенную. Эта двухмерная вселенная имеет форму прямоугольной сетки, содержащей n строк и m столбцов. Вселенная очень маленькая: в одной ячейке сетки может находится только одна частица. В этой вселенной каждая частица либо статическая, либо динамическая. Всякая статическая частица постоянно находится на одной и той же позиции. Из-за непонятных законов гравитационных искривлений в двухмерной вселенной никакие две статические частицы не могут быть в одном столбце или одной строке, а также не могут находиться в соседних по диагонали ячейках. Динамическая частица появляется в случайной пустой ячейке, случайным образом выбирает ячейку назначения (ячейка назначения может совпадать с начальной, см. примеры), и двигается в неё по кратчайшему пути по незанятым статическими частицами ячейкам. Все пустые ячейки имеют одинаковую вероятность быть выбранными в качестве начала или конца пути. После достижения пункта назначения частица исчезает. В один момент времени может быть только одна динамическая частица. Эта частица может перемещаться между ячейками, если те имеют смежную сторону, и это перемещение занимает ровно одну галактическую секунду. Стьюи стало интересно, какова средняя продолжительность жизни одной частицы в данной вселенной.
Выходные данные
Требуется вывести в единственной строке одно число — среднюю длительность жизни одной частицы с точностью хотя бы 6 знаков после запятой.
Ответ будет засчитан, если он отличается от правильного не более чем на 10 - 6 относительной или абсолютной погрешности.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
..
.X
|
0.888888888889
|
|
2
|
3 3
...
.X.
...
|
2.000000000000
|