Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Путешествие
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Кролик Стьюи исследует новую параллельную вселенную. Эта двухмерная вселенная имеет форму прямоугольной сетки, содержащей n строк и m столбцов. Вселенная очень маленькая: в одной ячейке сетки может находится только одна частица. В этой вселенной каждая частица либо статическая, либо динамическая. Всякая статическая частица постоянно находится на одной и той же позиции. Из-за непонятных законов гравитационных искривлений в двухмерной вселенной никакие две статические частицы не могут быть в одном столбце или одной строке, а также не могут находиться в соседних по диагонали ячейках. Динамическая частица появляется в случайной пустой ячейке, случайным образом выбирает ячейку назначения (ячейка назначения может совпадать с начальной, см. примеры), и двигается в неё по кратчайшему пути по незанятым статическими частицами ячейкам. Все пустые ячейки имеют одинаковую вероятность быть выбранными в качестве начала или конца пути. После достижения пункта назначения частица исчезает. В один момент времени может быть только одна динамическая частица. Эта частица может перемещаться между ячейками, если те имеют смежную сторону, и это перемещение занимает ровно одну галактическую секунду. Стьюи стало интересно, какова средняя продолжительность жизни одной частицы в данной вселенной.

Входные данные

Первая строка содержит два целых числа, разделенные пробелами: n, m (2 ≤ n, m ≤ 1000) — размеры вселенной. Следующие n строк по m символов каждая описывают вселенную без динамических частиц — j-ый символ i-ой строки равен 'X' если ячейка занята статической частицей, или '.' если пустая. Гарантируется что описанная вселенная удовлетворяет свойствам, описанным выше, то есть никакие две статические частицы не могут быть в одном столбце или одной строке, а также не могут находиться в соседних по диагонали ячейках.

Выходные данные

Требуется вывести в единственной строке одно число — среднюю длительность жизни одной частицы с точностью хотя бы 6 знаков после запятой.

Ответ будет засчитан, если он отличается от правильного не более чем на 10 - 6 относительной или абсолютной погрешности.

Примеры
Входные данные
2 2
..
.X
Выходные данные
0.888888888889
Входные данные
3 3
...
.X.
...
Выходные данные
2.000000000000