CF57D.Journey

Stewie the Rabbit explores a new parallel universe. This two dimensional universe has the shape of a rectangular grid, containing n lines and m columns. The universe is very small: one cell of the grid can only contain one particle. Each particle in this universe is either static or dynamic. Each static particle always remains in one and the same position. Due to unintelligible gravitation laws no two static particles in the parallel universe can be present in one column or row, and they also can't be present in the diagonally adjacent cells. A dynamic particle appears in a random empty cell, randomly chooses the destination cell (destination cell may coincide with the start cell, see the samples) and moves there along the shortest path through the cells, unoccupied by the static particles. All empty cells have the same probability of being selected as the beginning or end of the path. Having reached the destination cell, the particle disappears. Only one dynamic particle can exist at one moment of time. This particle can move from a cell to a cell if they have an adjacent side, and this transition takes exactly one galactic second. Stewie got interested in what is the average lifespan of one particle in the given universe.

兔子斯图伊（Stewie）探索了一个新的平行宇宙。这个二维宇宙呈矩形网格状，包含 $n$ 行和 $m$ 列。该宇宙非常微小：网格中的每个单元格最多只能容纳一个粒子。该宇宙中的每个粒子要么是静态的，要么是动态的。每个静态粒子始终固定在同一个位置上。由于难以理解的引力定律，在该平行宇宙中，任意两颗静态粒子不能位于同一行或同一列，也不能位于对角相邻的单元格中。一颗动态粒子会随机出现在某个空单元格中，然后随机选择一个目标单元格（目标单元格可以与起始单元格相同，参见样例），并沿穿过未被静态粒子占据的单元格的最短路径移动至该目标单元格。所有空单元格被选为路径起点或终点的概率均相等。粒子抵达目标单元格后即消失。任意时刻至多只存在一颗动态粒子。粒子每次只能从一个单元格移动到与其有一条公共边的相邻单元格，且每次移动恰好耗时 1 个银河秒。斯图伊很想知道：在此给定宇宙中，单颗粒子的平均寿命是多少？

The first line contains two space-separated integers: n, m (2 ≤ n, m ≤ 1000) which represent the sizes of the universe. The next n lines containing m symbols each describe the universe without dynamic particles — the j-th symbol of the i-th line equals to 'X' if the cell is occupied by a static particle, and to '.' if it is empty. It is guaranteed that the described universe satisfies the properties described above, that is no two static particles can be in one column or in one row, besides, they can't be positioned in the diagonally adjacent cells.

第一行包含两个以空格分隔的整数：$n$、$m$（$2 \leq n, m \leq 1000$），表示宇宙的尺寸。接下来的 $n$ 行，每行包含 $m$ 个字符，描述不含动态粒子的宇宙——第 $i$ 行的第 $j$ 个字符为 'X' 表示该格子被一个静态粒子占据，为 '.' 表示该格子为空。题目保证所描述的宇宙满足上述性质，即：任意两颗静态粒子不能位于同一行或同一列，且也不能位于对角线相邻的格子中。

You have to print on a single line a single number which is the average life span of a particle with an accuracy of at least 6 decimal places.

The answer will be accepted if it is within 10 - 6 of absolute or relative error from the correct answer.

你需要在一行中输出一个数字，即粒子的平均寿命，精度至少为小数点后 6 位。

若输出结果与正确答案的绝对误差或相对误差不超过 $10^{-6}$，则该答案将被接受。