#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;
}
