Problem: 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.

Input

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.

Output

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.

Examples

Input

2 2
..
.X


Output

0.888888888889


Input

3 3
...
.X.
...


Output

2.000000000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:66777216")
#pragma warning(disable : 4996)
#pragma hdrstop
template <bool... Bools>
struct Disjunction : std::false_type {};
template <bool First, bool... Others>
struct Disjunction<First, Others...>
    : std::integral_constant<bool, First || Disjunction<Others...>::value> {};
template <typename T>
constexpr auto has_begin(int) -> decltype(std::begin(std::declval<T>()), true) {
  return true;
}
template <typename T>
constexpr bool has_begin(...) {
  return false;
}
template <typename T>
using is_container = std::integral_constant<bool, has_begin<T>(0)>;
template <typename T, typename... Types>
using is_one_of = Disjunction<std::is_same<T, Types>::value...>;
template <typename T>
using is_sane_integer = std::integral_constant<
    bool,
    std::is_integral<T>::value &&
        !is_one_of<typename std::remove_cv<T>::type, char, signed char,
                   unsigned char, bool, char16_t, char32_t, wchar_t>::value>;
std::string to_string(const std::string& s) { return '"' + s + '"'; }
std::string to_string(const char* s) { return to_string(std::string(s)); }
std::string to_string(const char ch) { return {'\'', ch, '\''}; }
std::string to_string(const bool b) { return (b ? "true" : "false"); }
template <typename T,
          typename std::enable_if<Disjunction<
              is_sane_integer<T>::value,
              std::is_floating_point<T>::value>::value>::type* = nullptr>
std::string to_string(const T value) {
  return std::to_string(value);
}
template <typename A, typename B>
std::string to_string(const std::pair<A, B>&);
template <typename T,
          typename std::enable_if<is_container<T>::value>::type* = nullptr>
std::string to_string(const T& container) {
  bool is_first = true;
  std::string res = "{";
  for (const auto& x : container) {
    if (!is_first) {
      res += ", ";
    }
    is_first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
std::string to_string(const std::pair<A, B>& p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
std::vector<std::string> vec_splitter(std::string s) {
  s += ',';
  std::vector<std::string> res;
  while (!s.empty()) {
    const size_t pos = s.find(',');
    res.emplace_back(s.substr(0, pos));
    s = s.substr(pos + 1);
  }
  return res;
}
void debug_out(std::vector<std::string> __attribute__((unused)) args,
               __attribute__((unused)) int idx,
               __attribute__((unused)) int LINE_NUM) {
  std::cerr << std::endl;
}
template <typename Head, typename... Tail>
void debug_out(std::vector<std::string> args, int idx, int LINE_NUM, Head H,
               Tail... T) {
  std::stringstream ss;
  ss << to_string(H);
  if (idx > 0) {
    std::cerr << ", ";
  } else {
    std::cerr << "Line(" << LINE_NUM << ") ";
  }
  const std::string& arg = args[idx];
  const std::string value = ss.str();
  if (arg == value) {
    std::cerr << arg;
  } else {
    std::cerr << arg << " = " << value;
  }
  debug_out(args, idx + 1, LINE_NUM, T...);
}
namespace std {
template <typename T>
std::istream& operator>>(std::istream& in, std::vector<T>& vec) {
  for (auto& it : vec) {
    in >> it;
  }
  return in;
}
template <typename T, typename U>
std::istream& operator>>(std::istream& in, std::pair<T, U>& rhs) {
  in >> rhs.first >> rhs.second;
  return in;
}
}  // namespace std
void assign_files_input_txt() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
template <typename T>
class IntegerIterator
    : public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
 public:
  using value_type = T;
  constexpr explicit IntegerIterator(const value_type value) : value_(value) {}
  IntegerIterator& operator++() {
    ++value_;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value_;
    return copy;
  }
  IntegerIterator& operator--() {
    --value_;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value_;
    return copy;
  }
  constexpr value_type operator*() const { return value_; }
  constexpr bool operator==(const IntegerIterator rhs) const {
    return value_ == rhs.value_;
  }
  constexpr bool operator!=(const IntegerIterator rhs) const {
    return !(*this == rhs);
  }
  constexpr value_type operator+(const IntegerIterator rhs) const {
    return value_ + rhs.value_;
  }
  IntegerIterator& operator+=(const IntegerIterator rhs) const {
    value_ += rhs.value_;
    return *this;
  }
  constexpr value_type operator-(const IntegerIterator rhs) const {
    return value_ - rhs.value_;
  }
  IntegerIterator& operator-=(const IntegerIterator rhs) const {
    value_ -= rhs.value_;
    return *this;
  }

 private:
  value_type value_;
};
template <typename T>
class IntegerRange {
 public:
  using const_iterator = IntegerIterator<T>;
  constexpr IntegerRange(const T begin, const T end)
      : begin_(begin), end_(end) {}
  constexpr const_iterator begin() const { return const_iterator(begin_); }
  constexpr const_iterator end() const { return const_iterator(end_); }
  constexpr T size() const { return end_ - begin_; }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedRange {
 public:
  using const_iterator = typename std::decay<T>::type::const_iterator;
  using reverse_iterator = std::reverse_iterator<const_iterator>;
  explicit constexpr ReversedRange(const T& iterable)
      : begin_(iterable.begin()), end_(iterable.end()) {}
  constexpr reverse_iterator begin() const { return reverse_iterator(end_); }
  constexpr reverse_iterator end() const { return reverse_iterator(begin_); }

 private:
  const_iterator begin_;
  const_iterator end_;
};
template <typename T>
ReversedRange<T> reversed(T&& iterable) {
  return ReversedRange<T>{iterable};
}
template <typename T>
constexpr IntegerRange<T> range(const T to) {
  return IntegerRange<T>(0, to);
}
template <typename T>
constexpr IntegerRange<T> range(const T from, const T to) {
  return IntegerRange<T>(from, to);
}
template <typename T>
constexpr IntegerRange<T> inclusiveRange(const T to) {
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
constexpr IntegerRange<T> inclusiveRange(const T from, const T to) {
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> downrange(const T from) {
  return reversed(range(from));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> downrange(const T from, const T to) {
  return reversed(range(to, from));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> inclusiveDownrange(const T from) {
  return reversed(range(from + 1));
}
template <typename T>
constexpr ReversedRange<IntegerRange<T>> inclusiveDownrange(const T from,
                                                            const T to) {
  return reversed(range(to, from + 1));
}
template <typename R>
void sort(R& range) {
  std::sort(range.begin(), range.end());
}
template <typename R, typename Comp>
void sort(R& range, Comp comp) {
  std::sort(range.begin(), range.end(), comp);
}
template <typename R>
void reverse(R& range) {
  std::reverse(range.begin(), range.end());
}
template <typename R, typename T>
auto lower_bound(const R& range, const T& value) -> decltype(range.begin()) {
  return std::lower_bound(range.begin(), range.end(), value);
}
template <typename R, typename T, typename Comp>
auto lower_bound(const R& range, const T& value, Comp comp)
    -> decltype(range.begin()) {
  return std::lower_bound(range.begin(), range.end(), value, comp);
}
template <typename R, typename T>
auto upper_bound(const R& range, const T& value) -> decltype(range.begin()) {
  return std::upper_bound(range.begin(), range.end(), value);
}
template <typename R, typename T, typename Comp>
auto upper_bound(const R& range, const T& value, Comp comp)
    -> decltype(range.begin()) {
  return std::upper_bound(range.begin(), range.end(), value, comp);
}
template <typename R>
auto min_element(const R& range) -> decltype(range.begin()) {
  return std::min_element(range.begin(), range.end());
}
template <typename R>
auto max_element(const R& range) -> decltype(range.begin()) {
  return std::max_element(range.begin(), range.end());
}
template <typename R>
bool next_permutation(R& range) {
  return std::next_permutation(range.begin(), range.end());
}
template <typename T>
void unique(std::vector<T>& range) {
  range.erase(std::unique(range.begin(), range.end()), range.end());
}
template <typename T>
void dedup(std::vector<T>& range) {
  sort(range);
  unique(range);
}
template <typename R>
R sorted(R range) {
  sort(range);
  return range;
}
template <typename R, typename Comp>
R sorted(R range, Comp comp) {
  sort(range, comp);
  return range;
}
static constexpr long double PI = 3.14159265358979323846;
static constexpr long double EPS = 1e-9;
static constexpr int32_t INF = 0x3f3f3f3f;
static constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr int32_t DX[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
static constexpr int32_t DY[8] = {0, 1, 0, -1, -1, 1, 1, -1};
static constexpr uint32_t kDayMonth[12] = {31, 28, 31, 30, 31, 30,
                                           31, 31, 30, 31, 30, 31};
enum Direction : uint8_t {
  Up,
  Right,
  Down,
  Left,
  UpLeft,
  UpRight,
  DownRight,
  DownLeft,
  North = Up,
  East = Right,
  South = Down,
  West = Left,
  NorthWest = UpLeft,
  NorthEast = UpRight,
  SouthEast = DownRight,
  SouthWest = DownLeft,
  Unknown = 255
};
namespace Random {
inline std::chrono::system_clock::rep current_timestamp() {
  return std::chrono::system_clock::now().time_since_epoch().count();
}
inline uint64_t get_new_rand_seed() {
  return static_cast<uint64_t>(current_timestamp());
}
inline uint64_t get_rand_seed() {
  static const uint64_t kRandSeed = get_new_rand_seed();
  return kRandSeed;
}
using Engine = std::mt19937_64;
template <typename T>
using Distribution = std::uniform_int_distribution<T>;
inline Engine& random_engine() {
  static Engine engine(get_rand_seed());
  return engine;
}
template <typename T>
inline T get(const T to) {
  Distribution<T> distribution(0, to);
  return distribution(random_engine());
}
template <typename T>
inline T get(const T from, const T to) {
  return get(to - from) + from;
}
template <typename T = int32_t>
inline T get() {
  return get(static_cast<T>(0), std::numeric_limits<T>::max());
}
}  // namespace Random
template <typename T,
          typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
class SafeIntegralHash {
 public:
  const T kRandomValue = static_cast<T>(Random::current_timestamp());
  T operator()(const T& value) const { return value ^ kRandomValue; }
};
template <typename Key, typename Value,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMap = std::unordered_map<Key, Value, SafeIntegralHash<Key>>;
template <typename Key, typename Value,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMultiMap =
    std::unordered_multimap<Key, Value, SafeIntegralHash<Key>>;
template <typename Key,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedSet = std::unordered_set<Key, SafeIntegralHash<Key>>;
template <typename Key,
          typename std::enable_if<std::is_integral<Key>::value>::type* =
              nullptr>
using SafeUnorderedMultiSet =
    std::unordered_multiset<Key, SafeIntegralHash<Key>>;
namespace std {
template <typename T, typename U>
struct hash<std::pair<T, U>> {
  std::size_t operator()(const std::pair<T, U>& pair) const {
    return pair.first * 877117 + pair.second;
  }
};
}  // namespace std
template <typename T, typename std::enable_if<
                          std::is_floating_point<T>::value>::type* = nullptr>
inline bool is_equal_to_zero(const T& a) {
  return abs(a) < EPS;
}
template <typename T, typename std::enable_if<
                          !std::is_floating_point<T>::value>::type* = nullptr>
inline bool is_equal_to_zero(const T& a) {
  return a == 0;
}
template <typename T>
inline bool umin(T& a, const T& b) {
  return (b < a ? a = b, true : false);
}
template <typename T>
inline bool umax(T& a, const T& b) {
  return (a < b ? a = b, true : false);
}
template <typename T, size_t N>
struct MakeVector {
  template <typename... Args,
            typename R = std::vector<decltype(MakeVector<T, N - 1>::make_vector(
                std::declval<Args>()...))>>
  static R make_vector(size_t first, Args... sizes) {
    auto inner = MakeVector<T, N - 1>::make_vector(sizes...);
    return R(first, inner);
  }
};
template <typename T>
struct MakeVector<T, 1> {
  template <typename R = std::vector<T>>
  static R make_vector(std::size_t size, const T& value) {
    return R(size, value);
  }
};
template <typename T, typename... Args>
auto make_vector(Args... args)
    -> decltype(MakeVector<T, sizeof...(Args) - 1>::make_vector(args...)) {
  return MakeVector<T, sizeof...(Args) - 1>::make_vector(args...);
}
template <typename T>
inline bool is_leap_year(const T year) {
  return year % 400 == 0 || (year % 100 != 0 && (year & 3) == 0);
}
inline size_t get_days_in_month(const size_t month, const size_t year) {
  return kDayMonth[month] + (month == 1 && is_leap_year(year) ? 1 : 0);
}
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using pli = std::pair<ll, int>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vp = std::vector<pii>;
template <typename T>
inline T gcd(T a, T b) {
  while (b != 0) {
    a %= b;
    std::swap(a, b);
  }
  return a;
}
template <typename T>
inline T lcm(const T& a, const T& b) {
  return a / gcd(a, b) * b;
}
template <typename T>
constexpr inline T sqr(const T& x) {
  return x * x;
}
template <typename T>
T extended_gcd(const T a, const T b, T& x, T& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  const T p = b / a;
  const T g = extended_gcd(b - p * a, a, y, x);
  x -= p * y;
  return g;
}
template <typename T>
bool solve_diophantine(const T a, const T b, const T c, T& x, T& y, T& g) {
  if (a == 0 && b == 0) {
    if (c == 0) {
      x = 0;
      y = 0;
      g = 0;
      return true;
    }
    return false;
  }
  if (a == 0) {
    if (c % b == 0) {
      x = 0;
      y = c / b;
      g = std::abs(b);
      return true;
    }
    return false;
  }
  if (b == 0) {
    if (c % a == 0) {
      x = c / a;
      y = 0;
      g = std::abs(a);
      return true;
    }
    return false;
  }
  g = extended_gcd(a, b, x, y);
  if (c % g != 0) {
    return false;
  }
  T adjusted_c = c;
  const T dx = adjusted_c / a;
  adjusted_c -= dx * a;
  const T dy = adjusted_c / b;
  adjusted_c -= dy * b;
  x = dx + static_cast<T>(static_cast<__int128>(x) * (adjusted_c / g) % b);
  y = dy + static_cast<T>(static_cast<__int128>(y) * (adjusted_c / g) % a);
  g = std::abs(g);
  return true;
}
template <typename T, typename std::enable_if<
                          std::is_floating_point<T>::value>::type* = nullptr>
size_t solve_quadratic_equation(const T a, const T b, const T c, T& x1, T& x2) {
  const T D = sqr(b) - 4 * a * c;
  if (D < -EPS) {
    return 0;
  }
  if (is_equal_to_zero(D)) {
    const T x = -b / (a * 2);
    x1 = x;
    return 1;
  }
  x1 = (-b + std::sqrt(D)) / (a * 2);
  x2 = (-b - std::sqrt(D)) / (a * 2);
  return 2;
}
template <typename T>
T factorial(const size_t n) {
  T ret = 1;
  for (size_t i = 2; i <= n; ++i) {
    ret *= i;
  }
  return ret;
}
template <typename T, typename U>
inline T binpow(T a, U b) {
  static_assert(std::is_integral<U>::value,
                "Degree must be integral. For real degree use pow().");
  T ret = 1;
  while (b != 0) {
    if ((b & 1) != 0) {
      ret *= a;
    }
    a *= a;
    b >>= 1;
  }
  return ret;
}
template <typename T, typename U, typename Q>
inline T binpow(T a, U b, Q mod) {
  static_assert(std::is_integral<U>::value,
                "Degree must be integral. For real degree use pow().");
  long long ret = 1;
  a %= mod;
  while (b != 0) {
    if ((b & 1) != 0) {
      ret = ret * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return ret % mod;
}
template <typename T>
T digit_sum(const T n) {
  T res = 0;
  T tmp = abs(n);
  while (tmp > 0) {
    res += tmp % 10;
    tmp /= 10;
  }
  return res;
}
template <typename T>
std::vector<size_t> digits(const T n) {
  if (n == 0) {
    return {0};
  }
  std::vector<size_t> res;
  T tmp = abs(n);
  while (tmp > 0) {
    res.emplace_back(tmp % 10);
    tmp /= 10;
  }
  return res;
}
template <typename T>
size_t digit_count(const T n) {
  return digits(n).size();
}
template <typename T>
std::vector<T> divisors_vector(const T n) {
  const auto approximate_divisors_count = static_cast<size_t>(std::cbrt(n));
  std::vector<T> ans;
  ans.reserve(approximate_divisors_count);
  const auto floored_square_root = static_cast<T>(sqrt(n));
  for (T i = 1; i <= floored_square_root; ++i) {
    if (n % i == 0) {
      ans.emplace_back(i);
      if (n / i != i) {
        ans.emplace_back(n / i);
      }
    }
  }
  return ans;
}
template <typename T, typename size_type = std::size_t>
std::vector<T> divisors_vector(
    const std::vector<std::pair<T, size_type>>& prime_divisors,
    const bool sorted = false) {
  static std::vector<T> buffer;
  size_t divisors_count = 1;
  for (const auto& prime_divisor : prime_divisors) {
    divisors_count *= prime_divisor.second + 1;
  }
  std::vector<T> factors = {1};
  factors.reserve(divisors_count);
  if (sorted) {
    buffer.resize(divisors_count);
  }
  for (const auto& prime_divisor : prime_divisors) {
    const T prime_div = prime_divisor.first;
    const size_t exponent = prime_divisor.second;
    const size_t prev_size = factors.size();
    for (size_t i = 0; i < exponent * prev_size; ++i) {
      factors.emplace_back(factors[factors.size() - prev_size] * prime_div);
    }
    if (sorted && factors[prev_size - 1] > prime_div) {
      for (size_t section = prev_size; section < factors.size(); section *= 2) {
        for (size_t i = 0; i + section < factors.size(); i += 2 * section) {
          const size_t length = std::min(2 * section, factors.size() - i);
          std::merge(factors.cbegin() + i, factors.cbegin() + i + section,
                     factors.cbegin() + i + section,
                     factors.cbegin() + i + length, buffer.begin());
          std::copy(buffer.cbegin(), buffer.cbegin() + length,
                    factors.begin() + i);
        }
      }
    }
  }
  return factors;
}
template <typename T>
T euler_function(T n) {
  T res = n;
  for (T i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      while (n % i == 0) {
        n /= i;
      }
      res -= res / i;
    }
  }
  if (n > 1) {
    res -= res / n;
  }
  return res;
}
template <typename T, typename U>
T inverse_element(const T n, const U mod) {
  return binpow(static_cast<long long>(n), mod - 2, mod);
}
inline void inverseElementForSegment(int r[], const int n, const int mod) {
  r[1] = 1;
  for (int i = 2; i < n; ++i) {
    r[i] = (mod - static_cast<long long>(mod) / i * r[mod % i] % mod) % mod;
  }
}
template <typename T>
T inverse_element_comp_mod(const T n, const T mod) {
  return binpow(n, euler_function(mod) - 1, mod);
}
template <typename T>
void binomial_coefficients(const size_t n, std::vector<std::vector<T>>* c) {
  std::vector<std::vector<T>> result(n, std::vector<T>(n));
  for (size_t i = 0; i < n; ++i) {
    result[i][0] = 1;
    result[i][i] = 1;
    for (size_t j = 1; j < i; ++j) {
      result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
    }
  }
  c->swap(result);
}
template <class T>
std::string toRoman(T n) {
  const int ValsCount = 13;
  const int Vals[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
  const char* Digits[] = {"I",  "IV", "V",  "IX", "X",  "XL", "L",
                          "XC", "C",  "CD", "D",  "CM", "M"};
  std::string res = "";
  int x = ValsCount - 1;
  while (n) {
    while (Vals[x] > n) {
      --x;
    }
    n -= Vals[x];
    res += Digits[x];
  }
  return res;
}
template <typename T>
std::vector<T> calc_powers(const T base, const size_t n) {
  std::vector<T> powers(n + 1);
  powers[0] = 1;
  for (size_t i = 1; i < powers.size(); ++i) {
    powers[i] = powers[i - 1] * base;
  }
  return powers;
}
template <typename T>
std::vector<T> calc_factorial(const size_t n) {
  std::vector<T> factorial(n + 1);
  factorial[0] = 1;
  for (size_t i = 1; i < factorial.size(); ++i) {
    factorial[i] = factorial[i - 1] * i;
  }
  return factorial;
}
inline uint32_t abs(const uint32_t x) { return x; }
inline uint64_t abs(const uint64_t x) { return x; }
namespace safe {
template <typename T>
constexpr T abs(const T arg) {
  return arg < 0 ? -arg : arg;
}
template <typename T>
constexpr bool is_zero(const T arg) {
  return abs(arg) < EPS;
}
template <typename T>
constexpr bool equal(const T lhs, const T rhs) {
  return is_zero(lhs - rhs);
}
template <typename T>
constexpr bool not_equal(const T lhs, const T rhs) {
  return !equal(lhs, rhs);
}
template <typename T>
constexpr bool less_or_equal(const T lhs, const T rhs) {
  return lhs < rhs || equal(lhs, rhs);
}
template <typename T>
constexpr bool less(const T lhs, const T rhs) {
  return lhs < rhs && !equal(lhs, rhs);
}
template <typename T>
constexpr bool greater_or_equal(const T lhs, const T rhs) {
  return less_or_equal(rhs, lhs);
}
template <typename T>
constexpr bool greater(const T lhs, const T rhs) {
  return less(rhs, lhs);
}
template <typename T>
T sqrt(const T arg) {
  static_assert(std::is_floating_point<T>(),
                "Implemented only for floating point types.");
  if (is_zero(arg)) {
    return 0;
  }
  return std::sqrt(arg);
}
template <typename T>
T asin(const T arg) {
  static_assert(std::is_floating_point<T>(),
                "Implemented only for floating point types.");
  const T tmp_arg =
      std::min(static_cast<T>(1.0), std::max(static_cast<T>(-1.0), arg));
  return std::asin(tmp_arg);
}
template <typename T>
T acos(const T arg) {
  static_assert(std::is_floating_point<T>(),
                "Implemented only for floating point types.");
  const T tmp_arg =
      std::min(static_cast<T>(1.0), std::max(static_cast<T>(-1.0), arg));
  return std::acos(tmp_arg);
}
}  // namespace safe
template <typename T = long double,
          typename std::enable_if<std::is_floating_point<T>::value>::type* =
              nullptr>
class Decimal {
 public:
  using value_type = T;
  constexpr Decimal() : Decimal(0) {}
  constexpr Decimal(const T value) : value_(value) {}
  Decimal& operator+=(const Decimal& rhs) {
    value_ += rhs.value_;
    return *this;
  }
  Decimal& operator-=(const Decimal& rhs) {
    value_ -= rhs.value_;
    return *this;
  }
  Decimal& operator*=(const Decimal& rhs) {
    value_ *= rhs.value_;
    return *this;
  }
  Decimal& operator/=(const Decimal& rhs) {
    value_ /= rhs.value_;
    return *this;
  }
  constexpr Decimal operator+(const Decimal& rhs) const {
    return {value_ + rhs.value_};
  }
  constexpr Decimal operator-(const Decimal& rhs) const {
    return {value_ - rhs.value_};
  }
  constexpr Decimal operator*(const Decimal& rhs) const {
    return {value_ * rhs.value_};
  }
  constexpr Decimal operator/(const Decimal& rhs) const {
    return {value_ / rhs.value_};
  }
  constexpr Decimal operator+() const { return {value_}; }
  constexpr Decimal operator-() const { return negate(); }
  constexpr Decimal negate() const { return {-value_}; }
  constexpr Decimal abs() const { return {safe::abs(value_)}; }
  Decimal sqrt() const { return {safe::sqrt(value_)}; }
  Decimal asin() const { return {safe::asin(value_)}; }
  Decimal acos() const { return {safe::acos(value_)}; }
  Decimal pow(const Decimal arg) const {
    return {std::pow(value_, arg.value())};
  }
  Decimal log() const { return {std::log(value_)}; }
  constexpr bool operator==(const Decimal& rhs) const {
    return safe::equal(value_, rhs.value_);
  }
  constexpr bool operator!=(const Decimal& rhs) const {
    return safe::not_equal(value_, rhs.value_);
  }
  constexpr bool operator<(const Decimal& rhs) const {
    return safe::less(value_, rhs.value_);
  }
  constexpr bool operator<=(const Decimal& rhs) const {
    return safe::less_or_equal(value_, rhs.value_);
  }
  constexpr bool operator>(const Decimal& rhs) const {
    return safe::greater(value_, rhs.value_);
  }
  constexpr bool operator>=(const Decimal& rhs) const {
    return safe::greater_or_equal(value_, rhs.value_);
  }
  constexpr explicit operator value_type() const { return value_; }
  constexpr value_type value() const { return value_; }
  constexpr value_type double_value() const { return value_; }
  constexpr int int_value() const { return static_cast<int>(value_); }
  constexpr long long long_value() const {
    return static_cast<long long>(value_);
  }
  constexpr Decimal frac() const { return {value_ - long_value()}; }
  Decimal ceil() const {
    if (safe::is_zero(frac())) {
      return {value_};
    }
    return {long_value() + 1.0};
  }
  constexpr Decimal floor() const {
    return {static_cast<value_type>(long_value())};
  }
  constexpr Decimal trunc() const { return floor(); }
  constexpr Decimal round() const { return Decimal{value_ + 0.5}.floor(); }
  std::string str() const { return std::to_string(value_); }
  static Decimal pi() { return {PI}; }
  static Decimal zero() { return {0}; }
  friend std::istream& operator>>(std::istream& in, Decimal& x) {
    in >> x.value_;
    return in;
  }
  friend std::ostream& operator<<(std::ostream& out, const Decimal& x) {
    out << x.value_;
    return out;
  }

 private:
  value_type value_;
};
template <typename T>
std::string to_string(const Decimal<T> arg) {
  return arg.str();
}
namespace std {
template <typename T>
struct is_floating_point<Decimal<T>> : std::true_type {};
template <typename T>
Decimal<T> abs(const Decimal<T> arg) {
  return arg.abs();
}
template <typename T>
Decimal<T> sqrt(const Decimal<T> arg) {
  return arg.sqrt();
}
template <typename T>
Decimal<T> asin(const Decimal<T> arg) {
  return arg.asin();
}
template <typename T>
Decimal<T> acos(const Decimal<T> arg) {
  return arg.acos();
}
template <typename T>
Decimal<T> pow(const Decimal<T> lhs, const Decimal<T> rhs) {
  return lhs.pow(rhs);
}
template <typename T>
Decimal<T> log(const Decimal<T> arg) {
  return arg.log();
}
template <typename T>
struct hash<Decimal<T>> {
  size_t operator()(const Decimal<T> arg) const {
    return hash<typename Decimal<T>::value_type>()(arg.value());
  }
};
}  // namespace std
template <typename T, typename SquareT = T, typename DecimalT = Decimal<>>
class Coord2D {
 public:
  using value_type = T;
  using square_type = SquareT;
  using decimal_type = DecimalT;
  using decimal_coord_type = Coord2D<decimal_type, decimal_type, decimal_type>;
  constexpr Coord2D() : Coord2D(0, 0) {}
  constexpr Coord2D(const value_type x, const value_type y) : x(x), y(y) {}
  decimal_type angle() const { return atan2(y, x); }
  constexpr Coord2D add(const Coord2D& rhs) const {
    return {x + rhs.x, y + rhs.y};
  }
  constexpr Coord2D subtract(const Coord2D& rhs) const {
    return {x - rhs.x, y - rhs.y};
  }
  constexpr Coord2D operator+(const Coord2D& rhs) const { return add(rhs); }
  constexpr Coord2D operator-(const Coord2D& rhs) const {
    return subtract(rhs);
  }
  Coord2D& operator+=(const Coord2D& rhs) {
    x += rhs.x;
    y += rhs.y;
    return *this;
  }
  Coord2D& operator-=(const Coord2D& rhs) {
    x -= rhs.x;
    y -= rhs.y;
    return *this;
  }
  value_type& operator[](size_t index) {
    if (index == 0) {
      return x;
    }
    if (index == 1) {
      return y;
    }
  }
  const value_type& operator[](const size_t index) const {
    if (index == 0) {
      return x;
    }
    if (index == 1) {
      return y;
    }
  }
  bool operator==(const Coord2D& rhs) const { return x == rhs.x && y == rhs.y; }
  bool operator<(const Coord2D& rhs) const {
    return x < rhs.x || (x == rhs.x && y < rhs.y);
  }
  template <typename C>
  C as() const {
    return {static_cast<typename C::value_type>(x),
            static_cast<typename C::value_type>(y)};
  }
  std::string str() const {
    return "(" + std::to_string(x) + ", " + std::to_string(y) + ")";
  }
  friend std::istream& operator>>(std::istream& in, Coord2D& rhs) {
    in >> rhs.x >> rhs.y;
    return in;
  }
  value_type x;
  value_type y;

 protected:
  constexpr square_type squared_dist(const Coord2D& rhs) const {
    return sqr<square_type>(x - rhs.x) + sqr<square_type>(y - rhs.y);
  }
  decimal_type dist(const Coord2D& rhs) const {
    return std::sqrt(squared_dist(rhs));
  }
  template <typename std::enable_if<
                std::is_integral<value_type>::value>::type* = nullptr>
  constexpr value_type manhattan_dist(const Coord2D& rhs) const {
    return std::abs(x - rhs.x) + std::abs(y - rhs.y);
  }
};
template <typename T, typename SquareT = T, typename DecimalT = Decimal<>>
class Coord3D {
 public:
  using value_type = T;
  using square_type = SquareT;
  using decimal_type = DecimalT;
  using decimal_coord_type = Coord3D<decimal_type, decimal_type, decimal_type>;
  constexpr Coord3D() : Coord3D(0, 0, 0) {}
  constexpr Coord3D(const value_type x, const value_type y, const value_type z)
      : x(x), y(y), z(z) {}
  constexpr Coord3D add(const Coord3D& rhs) const {
    return {x + rhs.x, y + rhs.y, z + rhs.z};
  }
  constexpr Coord3D subtract(const Coord3D& rhs) const {
    return {x - rhs.x, y - rhs.y, z - rhs.z};
  }
  constexpr Coord3D operator+(const Coord3D& rhs) const { return add(rhs); }
  constexpr Coord3D operator-(const Coord3D& rhs) const {
    return subtract(rhs);
  }
  Coord3D& operator+=(const Coord3D& rhs) const {
    x += rhs.x;
    y += rhs.y;
    y += rhs.z;
    return *this;
  }
  Coord3D& operator-=(const Coord3D& rhs) const {
    x -= rhs.x;
    y -= rhs.y;
    z -= rhs.z;
    return *this;
  }
  value_type& operator[](size_t index) {
    if (index == 0) {
      return x;
    }
    if (index == 1) {
      return y;
    }
    if (index == 2) {
      return z;
    }
  }
  const value_type& operator[](const size_t index) const {
    if (index == 0) {
      return x;
    }
    if (index == 1) {
      return y;
    }
    if (index == 2) {
      return z;
    }
  }
  template <typename C>
  C as() const {
    return {static_cast<typename C::value_type>(x),
            static_cast<typename C::value_type>(y),
            static_cast<typename C::value_type>(z)};
  }
  std::string str() const {
    return "(" + std::to_string(x) + ", " + std::to_string(y) + ", " +
           std::to_string(z) + ")";
  }
  friend std::istream& operator>>(std::istream& in, Coord3D& rhs) {
    in >> rhs.x >> rhs.y >> rhs.z;
    return in;
  }
  value_type x;
  value_type y;
  value_type z;

 protected:
  constexpr square_type squared_dist(const Coord3D& rhs) const {
    return sqr<square_type>(x - rhs.x) + sqr<square_type>(y - rhs.y) +
           sqr<square_type>(z - rhs.z);
  }
  decimal_type dist(const Coord3D& rhs) const {
    return std::sqrt(squared_dist(rhs));
  }
  template <typename std::enable_if<
                std::is_integral<value_type>::value>::type* = nullptr>
  constexpr value_type manhattan_dist(const Coord3D& rhs) const {
    return std::abs(x - rhs.x) + std::abs(y - rhs.y) + std::abs(z - rhs.z);
  }
};
template <typename Coord>
struct is_2d {
  static constexpr bool value = std::is_same<
      Coord, Coord2D<typename Coord::value_type, typename Coord::square_type,
                     typename Coord::decimal_type>>::value;
};
template <typename Coord>
struct is_3d {
  static constexpr bool value = std::is_same<
      Coord, Coord3D<typename Coord::value_type, typename Coord::square_type,
                     typename Coord::decimal_type>>::value;
};
template <typename Coord,
          typename std::enable_if<is_2d<Coord>::value>::type* = nullptr>
struct CompareByY {
  bool operator()(const Coord& lhs, const Coord& rhs) const {
    return lhs.y < rhs.y || lhs.y == rhs.y && lhs.x < rhs.x;
  }
};
template <typename T, typename S, typename D>
std::string to_string(const Coord2D<T, S, D>& coord) {
  return coord.str();
}
template <typename T, typename S, typename D>
std::string to_string(const Coord3D<T, S, D>& coord) {
  return coord.str();
}
namespace std {
template <typename T, typename S, typename D>
struct hash<Coord2D<T, S, D>> {
  size_t operator()(const Coord2D<T, S, D>& arg) const {
    return hash<pair<T, T>>({arg.x, arg.y});
  }
};
template <typename T, typename S, typename D>
struct hash<Coord3D<T, S, D>> {
  size_t operator()(const Coord3D<T, S, D>& arg) const {
    return arg.x * 877117 + arg.y * 1000000009 + arg.z;
  }
};
}  // namespace std
template <typename Coord>
class Vector;
template <typename Coord>
class Point : public Coord {
 public:
  using vector_type = Vector<Coord>;
  using value_type = typename Coord::value_type;
  using square_type = typename Coord::square_type;
  using decimal_type = typename Coord::decimal_type;
  using coordinates_type = Coord;
  using decimal_point_type = Point<typename Coord::decimal_coord_type>;
  using decimal_vector_type = typename vector_type::decimal_vector_type;
  constexpr Point() : Coord() {}
  template <typename C = Coord,
            typename std::enable_if<is_2d<C>::value>::type* = nullptr>
  constexpr Point(const value_type x, const value_type y) : Coord(x, y) {}
  template <typename C = Coord,
            typename std::enable_if<is_3d<C>::value>::type* = nullptr>
  constexpr Point(const value_type x, const value_type y, const value_type z)
      : Coord(x, y, z) {}
  explicit constexpr Point(const Coord& coord) : Coord(coord) {}
  constexpr Point add(const Point& rhs) const { return Point(Coord::add(rhs)); }
  constexpr Point subtract(const Point& rhs) const {
    return Point(Coord::subtract(rhs));
  }
  constexpr Point operator+(const Point& rhs) const { return add(rhs); }
  constexpr Point operator-(const Point& rhs) const { return subtract(rhs); }
  Point& operator+=(const Point& rhs) {
    Coord::operator+=(rhs);
    return *this;
  }
  Point& operator-=(const Point& rhs) {
    Coord::operator-=(rhs);
    return *this;
  }
  constexpr square_type squared_dist(const Point& rhs) const {
    return Coord::squared_dist(rhs);
  }
  decimal_type dist(const Point& rhs) const { return Coord::dist(rhs); }
  template <typename std::enable_if<
                std::is_integral<value_type>::value>::type* = nullptr>
  constexpr value_type manhattan_dist(const Point& rhs) const {
    return Coord::manhattan_dist(rhs);
  }
  constexpr Point move_by(const vector_type& vector) const {
    return Point(this->x + vector.x, this->y + vector.y);
  }
  decimal_point_type get_height(const Point& A, const Point& B) const {
    const vector_type v(A, B);
    const vector_type u(A, *this);
    const decimal_type projection = decimal_type(v % u) / v.length();
    const auto projected =
        v.template as<decimal_vector_type>().normalize(projection);
    return A.template as<decimal_point_type>().move_by(projected);
  }
  decimal_type dist(const Point& A, const Point& B) const {
    const decimal_type dist_ab = A.dist(B);
    const vector_type a(A, *this);
    const vector_type b(B, *this);
    const decimal_type vector_mult = a * b;
    return vector_mult.abs() / dist_ab;
  }
  template <typename P>
  constexpr P as() const {
    return P(Coord::template as<typename P::coordinates_type>());
  }
};
template <typename Coord>
class Vector : public Coord {
 public:
  using point_type = Point<Coord>;
  using value_type = typename Coord::value_type;
  using square_type = typename Coord::square_type;
  using decimal_type = typename Coord::decimal_type;
  using coordinates_type = Coord;
  using decimal_vector_type = Vector<typename Coord::decimal_coord_type>;
  constexpr Vector() : Coord() {}
  template <typename C = Coord,
            typename std::enable_if<is_2d<C>::value>::type* = nullptr>
  constexpr Vector(const value_type x, const value_type y) : Coord(x, y) {}
  template <typename C = Coord,
            typename std::enable_if<is_3d<C>::value>::type* = nullptr>
  constexpr Vector(const value_type x, const value_type y, const value_type z)
      : Coord(x, y, z) {}
  constexpr explicit Vector(const Coord& coord) : Coord(coord) {}
  constexpr Vector(const point_type& a, const point_type& b)
      : Coord(b.x - a.x, b.y - a.y) {}
  constexpr Vector add(const Vector& rhs) const {
    return Vector(Coord::add(rhs));
  }
  constexpr Vector subtract(const Vector& rhs) const {
    return Vector(Coord::subtract(rhs));
  }
  constexpr Vector operator+(const Vector& rhs) const { return add(rhs); }
  constexpr Vector operator-(const Vector& rhs) const { return subtract(rhs); }
  Vector& operator+=(const Vector& rhs) const {
    Coord::operator+=(rhs);
    return *this;
  }
  Vector& operator-=(const Vector& rhs) const {
    Coord::operator-=(rhs);
    return *this;
  }
  constexpr Vector multiply(const value_type rhs) const {
    return Vector(this->x * rhs, this->y * rhs);
  }
  constexpr Vector operator*(const value_type rhs) const {
    return multiply(rhs);
  }
  decimal_type length() const { return Coord::dist(Coord()); }
  constexpr bool is_zero() const { return length() == 0; }
  constexpr Vector negate() const { return Vector(-this->x, -this->y); }
  constexpr Vector operator-() const { return negate(); }
  decimal_vector_type normalize(const decimal_type new_len = 1) const {
    const decimal_type len = length();
    if (len == 0) {
      if (new_len == 0) {
        return decimal_vector_type();
      }
      assert(false);
    }
    return as<decimal_vector_type>().multiply(new_len / len);
  }
  constexpr value_type scalar_mult(const Vector& rhs) const {
    return this->x * rhs.x + this->y * rhs.y;
  }
  constexpr value_type vector_mult(const Vector& rhs) const {
    return this->x * rhs.y - this->y * rhs.x;
  }
  constexpr value_type operator%(const Vector& rhs) const {
    return scalar_mult(rhs);
  }
  constexpr value_type operator*(const Vector& rhs) const {
    return vector_mult(rhs);
  }
  template <typename V>
  constexpr V as() const {
    return V(Coord::template as<typename V::coordinates_type>());
  }
};
template <typename T, typename SquareT = T, typename DecimalT = Decimal<>>
using Point2D = Point<Coord2D<T, SquareT, DecimalT>>;
template <typename T, typename SquareT = T, typename DecimalT = Decimal<>>
using Point3D = Point<Coord3D<T, SquareT, DecimalT>>;
template <typename T, typename SquareT = T, typename DecimalT = Decimal<>>
using Vector2D = Vector<Coord2D<T, SquareT, DecimalT>>;
template <typename T, typename SquareT = T, typename DecimalT = Decimal<>>
using Vector3D = Vector<Coord3D<T, SquareT, DecimalT>>;
template <typename Coord>
struct is_2d<Point<Coord>> {
  static constexpr bool value = is_2d<Coord>::value;
};
template <typename Coord>
struct is_3d<Point<Coord>> {
  static constexpr bool value = is_3d<Coord>::value;
};
template <typename Coord>
struct is_2d<Vector<Coord>> {
  static constexpr bool value = is_2d<Coord>::value;
};
template <typename Coord>
struct is_3d<Vector<Coord>> {
  static constexpr bool value = is_3d<Coord>::value;
};
namespace std {
template <typename Coord>
struct hash<Point<Coord>> {
  size_t operator()(const Point<Coord>& arg) const { return hash<Coord>(arg); }
};
template <typename Coord>
struct hash<Vector<Coord>> {
  size_t operator()(const Vector<Coord>& arg) const { return hash<Coord>(arg); }
};
}  // namespace std
template <typename T>
class Queue {
 public:
  using value_type = T;
  using size_type = std::size_t;
  using reference = value_type&;
  using const_reference = const value_type&;
  using rvalue = value_type&&;
  using container = std::vector<value_type>;
  explicit Queue(const size_type max_size) : data_(container(max_size)) {
    clear();
  }
  reference front() { return data_[head_index_]; }
  const_reference front() const { return data_[head_index_]; }
  reference back() { return data_[tail_index_ - 1]; }
  const_reference back() const { return data_[tail_index_ - 1]; }
  constexpr bool empty() const { return head_index_ == tail_index_; }
  void clear() {
    head_index_ = 0;
    tail_index_ = 0;
  }
  constexpr size_type size() const { return tail_index_ - head_index_; }
  void push(const_reference value) { data_[tail_index_++] = value; }
  void push(rvalue value) { data_[tail_index_++] = std::move(value); }
  value_type pop_front() { return data_[head_index_++]; }
  value_type pop_back() { return data_[--tail_index_]; }
  void swap(Queue& rhs) {
    data_.swap(rhs.data_);
    std::swap(head_index_, rhs.head_index_);
    std::swap(tail_index_, rhs.tail_index_);
  }
  const container& data() const { return data_; }
  bool operator==(const Queue& rhs) const {
    return head_index_ == rhs.head_index_ && tail_index_ == rhs.tail_index_ &&
           data_ == rhs.data_;
  }
  bool operator!=(const Queue& rhs) const { return !operator==(rhs); }
  bool operator<(const Queue& rhs) const { return data_ < rhs.data_; }
  bool operator<=(const Queue& rhs) const { return data_ <= rhs.data_; }
  bool operator>(const Queue& rhs) const { return data_ > rhs.data_; }
  bool operator>=(const Queue& rhs) const { return data_ >= rhs.data_; }

 private:
  container data_;
  size_type head_index_;
  size_type tail_index_;
};
class DJourney {
 public:
  static constexpr bool kWriteCaseNumber = false;
  static constexpr bool kMultiTest = false;
  using Pt = Point2D<int>;
  const int kMaxn = 1111;
  void solve(std::istream& in, std::ostream& out) {
    ll n, m;
    in >> n >> m;
    std::vector<std::string> field(n);
    in >> field;
    std::vector<ll> pref_sum(kMaxn);
    for (int i : range(1, kMaxn)) {
      pref_sum[i] = pref_sum[i - 1] + i;
    }
    Decimal<> sum = 0;
    std::vector<Pt> static_points;
    for (int i : range(n)) {
      for (int j : range(m)) {
        const ll cur_sum = (pref_sum[i] + pref_sum[n - i - 1]) * m +
                           (pref_sum[j] + pref_sum[m - j - 1]) * n;
        if (field[i][j] == '.') {
          sum += cur_sum;
        } else {
          sum -= cur_sum;
          static_points.emplace_back(i, j);
        }
      }
    }
    const int count_static = static_points.size();
    42;
    for (const auto& pt : static_points) {
      const ll sum_dist_to_static =
          std::accumulate(static_points.begin(), static_points.end(), 0LL,
                          [&pt](const ll acc, const Pt& value) {
                            return acc + pt.manhattan_dist(value);
                          });
      sum += sum_dist_to_static;
    }
    sort(static_points);
    for (int i : range(count_static)) {
      const auto& pt = static_points[i];
      const int count_left = pt.y;
      int cur_right = pt.y;
      int prev_x = pt.x;
      for (int j : inclusiveDownrange(i)) {
        const auto& cur = static_points[j];
        if (cur.y < cur_right || prev_x > cur.x + 1) {
          break;
        }
        cur_right = cur.y;
        prev_x = cur.x;
        sum += (m - cur_right - 1) * count_left * 4;
      }
      cur_right = pt.y;
      prev_x = pt.x;
      for (int j : range(i + 1, count_static)) {
        const auto& cur = static_points[j];
        if (cur.y < cur_right || prev_x < cur.x - 1) {
          break;
        }
        cur_right = cur.y;
        prev_x = cur.x;
        sum += (m - cur_right - 1) * count_left * 4;
      }
    }
    42;
    sort(static_points, CompareByY<Pt>());
    42;
    for (int i : range(count_static)) {
      const auto& pt = static_points[i];
      const int count_up = pt.x;
      int cur_down = pt.x;
      int prev_y = pt.y;
      for (int j : inclusiveDownrange(i)) {
        const auto& cur = static_points[j];
        if (cur.x < cur_down || prev_y > cur.y + 1) {
          break;
        }
        cur_down = cur.x;
        prev_y = cur.y;
        sum += (n - cur_down - 1) * count_up * 4;
      }
      cur_down = pt.x;
      prev_y = pt.y;
      for (int j : range(i + 1, count_static)) {
        const auto& cur = static_points[j];
        42;
        if (cur.x < cur_down || prev_y < cur.y - 1) {
          break;
        }
        cur_down = cur.x;
        prev_y = cur.y;
        sum += (n - cur_down - 1) * count_up * 4;
      }
    }
    42;
    const ll count = sqr<ll>(n * m - count_static);
    out << sum / count << std::endl;
  }
  DJourney() {}
  std::vector<std::vector<int>> bfs(const int x, const int y,
                                    const std::vector<std::string>& field,
                                    const bool ban_static = true) {
    const int n = field.size();
    const int m = field.front().size();
    static Queue<Pt> q(kMaxn * kMaxn);
    q.clear();
    auto dist = make_vector<int>(n, m, INF);
    auto add = [&dist, &field, &n, &m, &ban_static](const int x, const int y,
                                                    const int len) {
      if (x < 0 || y < 0 || x >= n || y >= m ||
          ban_static && field[x][y] == 'X') {
        return;
      }
      if (umin(dist[x][y], len)) {
        q.push({x, y});
      }
    };
    add(x, y, 0);
    while (!q.empty()) {
      const Pt cur = q.pop_front();
      const int len = dist[cur.x][cur.y];
      for (int dir : range(4)) {
        add(cur.x + DX[dir], cur.y + DY[dir], len + 1);
      }
    }
    return dist;
  }
  static constexpr bool kUseCustomChecker = true;
  bool check(std::istringstream in, std::istringstream jury,
             std::istringstream out) {
    int n, m;
    in >> n >> m;
    std::vector<std::string> field(n);
    in >> field;
    Decimal<> jans = 0;
    int count_static = 0;
    for (int x : range(n)) {
      for (int y : range(m)) {
        if (field[x][y] == 'X') {
          ++count_static;
          continue;
        }
        auto dist = bfs(x, y, field);
        ll cur_sum = 0;
        for (int i : range(n)) {
          for (int j : range(m)) {
            if (dist[i][j] < INF) {
              cur_sum += dist[i][j];
            }
          }
        }
        jans += cur_sum;
      }
    }
    jans /= sqr<ll>(n * m - count_static);
    Decimal<> pans;
    out >> pans;
    if (pans != jans) {
      42;
      return false;
    }
    return true;
  }
  static constexpr size_t kGeneratedTestsCount = 100;
  static constexpr bool kStopAfterFirstFail = true;
  static void generate_test(std::ostream& test) {
    const int kMaxn = 5;
    const int n = Random::get(2, kMaxn);
    const int m = Random::get(2, kMaxn);
    std::vector<std::string> field(n, std::string(m, '.'));
    std::set<Pt> points;
    for (int i : range(n)) {
      for (int j : range(m)) {
        points.emplace(i, j);
      }
    }
    int static_count = Random::get(1, std::min(n, m));
    while (static_count > 0 && !points.empty()) {
      const int id = Random::get<int>(0, points.size() - 1);
      int index = 0;
      for (const auto& pt : points) {
        if (index == id) {
          field[pt.x][pt.y] = 'X';
          --static_count;
          for (int dir : range(4, 8)) {
            const Pt neighbor{pt.x + DX[dir], pt.y + DY[dir]};
            points.erase(neighbor);
          }
          for (int i : range(n)) {
            points.erase({i, pt.y});
          }
          for (int j : range(m)) {
            points.erase({pt.x, j});
          }
          break;
        }
        ++index;
      }
    }
    test << n << " " << m << std::endl;
    for (const auto& row : field) {
      test << row << std::endl;
    }
  }
};
int main() {
  DJourney solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  srand(time(nullptr));
  out << std::fixed << std::setprecision(16);
  if (DJourney::kMultiTest) {
    size_t tests_count;
    in >> tests_count;
    for (size_t test_id : inclusiveRange<size_t>(1, tests_count)) {
      if (DJourney::kWriteCaseNumber) {
        out << "Case #" << test_id << ": ";
      }
      solver.solve(in, out);
    }
  } else {
    solver.solve(in, out);
  }
  return 0;
}