#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;

// #include <atcoder/all>
// using namespace atcoder;

// ====================
// デバッグユーティリティ
// ====================
#ifdef DEBUG

#define COLOR_RESET    "\033[0m"
#define COLOR_YELLOW   "\033[33m"
#define COLOR_CYAN     "\033[36m"
#define COLOR_MAGENTA  "\033[35m"
#define COLOR_BLACK    "\033[30m"
#define COLOR_RED      "\033[31m"
#define COLOR_GREEN    "\033[32m"
#define COLOR_BLUE     "\033[34m"
#define COLOR_WHITE    "\033[37m"
#define STYLE_DIM      "\033[2m"

// ====================
// 型情報出力
// ====================

// 整数をカンマ区切りに
string format_with_commas(unsigned __int128 x) {
    if (x == 0) return "0";
    string s;
    while (x > 0) {
        s.push_back('0' + (x % 10));
        x /= 10;
    }
    reverse(s.begin(), s.end());
    string out;
    int n = s.size(), cnt = 0;
    for (int i = n - 1; i >= 0; --i) {
        out.push_back(s[i]);
        if (++cnt % 3 == 0 && i != 0) out.push_back(',');
    }
    reverse(out.begin(), out.end());
    return out;
}

// 整数をカンマなし文字列に
string format_plain_digits(unsigned __int128 x) {
    if (x == 0) return "0";
    string s;
    while (x > 0) {
        s.push_back('0' + (x % 10));
        x /= 10;
    }
    reverse(s.begin(), s.end());
    return s;
}

// 浮動小数型 → 科学的記法
string format_float_with_exp(long double x) {
    if (x == 0.0L) return "0";
    int exp = floor(log10(fabsl(x)));
    long double base = x / powl(10.0L, exp);
    ostringstream oss;
    oss << fixed << setprecision(5) << base;
    return oss.str() + " × 10^" + to_string(exp);
}

// 整数型 min/max をカンマ区切り＋10^n 表記
template<typename T>
string format_int_with_exp(T x) {
    using U = unsigned __int128;

    auto make_exp_part = [](const string& plain, bool neg = false) -> string {
        if (plain == "0") return "  (≈ 0 × 10^0)";

        int exp = (int)plain.size() - 1;

        string head;
        head += plain[0];
        if (plain.size() >= 2) {
            head += ".";
            head += plain.substr(1, min<size_t>(2, plain.size() - 1));
        }

        return "  (≈ " + string(neg ? "-" : "") + head + " × 10^" + to_string(exp) + ")";
    };

    if constexpr (std::is_same_v<T, bool>) {
        return string(x ? "1 (true)" : "0 (false)");
    }
    else if constexpr (std::is_signed_v<T>) {
        if (x == std::numeric_limits<T>::min()) {
            U val = (U)((unsigned __int128)std::numeric_limits<T>::max()) + 1;
            string grouped = format_with_commas(val);
            string plain = format_plain_digits(val);
            return "-" + grouped + make_exp_part(plain, true);
        }

        bool neg = (x < 0);
        U val = neg ? U(-(__int128)x) : U(x);

        string grouped = format_with_commas(val);
        string plain = format_plain_digits(val);

        return string(neg ? "-" : "") + grouped + make_exp_part(plain, neg);
    }
    else {
        U val = U(x);
        string grouped = format_with_commas(val);
        string plain = format_plain_digits(val);
        return grouped + make_exp_part(plain, false);
    }
}

// 型情報出力
template<typename T>
void debug_typeinfo(const string& name) {
    cerr << COLOR_CYAN << "Type info for " << name << " ----------" << COLOR_RESET << "\n";
    cerr << COLOR_YELLOW << "  sizeof : " << COLOR_WHITE << sizeof(T) << " bytes\n";

    if constexpr (std::numeric_limits<T>::is_specialized) {
        if constexpr (std::is_integral_v<T>) {
            cerr << COLOR_YELLOW << "  min    : "
                 << COLOR_GREEN << format_int_with_exp(numeric_limits<T>::min())
                 << COLOR_RESET << "\n";
            cerr << COLOR_YELLOW << "  max    : "
                 << COLOR_GREEN << format_int_with_exp(numeric_limits<T>::max())
                 << COLOR_RESET << "\n";
        } else if constexpr (std::is_floating_point_v<T>) {
            cerr << COLOR_YELLOW << "  min    : "
                 << COLOR_GREEN << format_float_with_exp(numeric_limits<T>::min())
                 << COLOR_RESET << "\n";
            cerr << COLOR_YELLOW << "  max    : "
                 << COLOR_GREEN << format_float_with_exp(numeric_limits<T>::max())
                 << COLOR_RESET << "\n";
        }
    } else {
        cerr << "  min    : (not available)\n";
        cerr << "  max    : (not available)\n";
    }
    cerr << "----------------------------------\n";
}

// よく使う型リスト
void debug_type_list() {
    debug_typeinfo<int>("int");
    debug_typeinfo<long long>("long long");
    debug_typeinfo<unsigned long long>("unsigned long long");
    debug_typeinfo<__int128>("__int128");
    debug_typeinfo<unsigned __int128>("unsigned __int128");
    debug_typeinfo<float>("float");
    debug_typeinfo<double>("double");
    debug_typeinfo<long double>("long double");
    debug_typeinfo<char>("char");
    debug_typeinfo<bool>("bool");
    debug_typeinfo<string>("string");
}


string trim(const string& s) {
    size_t first = s.find_first_not_of(" \t");
    size_t last = s.find_last_not_of(" \t");
    if (first == string::npos) return "";
    return s.substr(first, (last - first + 1));
}

// pair
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    return os << "(" << p.first << ", " << p.second << ")";
}

// tuple
template<typename Tuple, size_t... Is>
void tuple_out_impl(ostream& os, const Tuple& t, index_sequence<Is...>) {
    ((os << (Is == 0 ? "" : ", ") << get<Is>(t)), ...);
}
template<typename... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
    os << "(";
    tuple_out_impl(os, t, index_sequence_for<Args...>{});
    os << ")";
    return os;
}
// ====================
// 追加のコンテナ出力
// ====================

// multiset
template<typename T>
ostream& operator<<(ostream& os, const multiset<T>& s) {
    os << "{ ";
    size_t i = 0;
    for (auto& x : s) {
        os << x;
        if (++i < s.size()) os << ", ";
    }
    os << " }";
    return os;
}

// unordered_multiset
template<typename T>
ostream& operator<<(ostream& os, const unordered_multiset<T>& s) {
    os << "{ ";
    size_t i = 0;
    for (auto& x : s) {
        os << x;
        if (++i < s.size()) os << ", ";
    }
    os << " }";
    return os;
}

// multimap
template<typename K, typename V>
ostream& operator<<(ostream& os, const multimap<K, V>& m) {
    os << "{ ";
    size_t i = 0;
    for (auto& [k, v] : m) {
        os << k << ": " << v;
        if (++i < m.size()) os << ", ";
    }
    os << " }";
    return os;
}

// unordered_multimap
template<typename K, typename V>
ostream& operator<<(ostream& os, const unordered_multimap<K, V>& m) {
    os << "{ ";
    size_t i = 0;
    for (auto& [k, v] : m) {
        os << k << ": " << v;
        if (++i < m.size()) os << ", ";
    }
    os << " }";
    return os;
}

// deque
template<typename T>
ostream& operator<<(ostream& os, const deque<T>& v) {
    os << "[ ";
    for (size_t i = 0; i < v.size(); i++) {
        os << v[i];
        if (i + 1 < v.size()) os << ", ";
    }
    os << " ]";
    return os;
}

// list
template<typename T>
ostream& operator<<(ostream& os, const list<T>& lst) {
    os << "[ ";
    bool first = true;
    for (auto& x : lst) {
        if (!first) os << ", ";
        os << x;
        first = false;
    }
    os << " ]";
    return os;
}

// forward_list
template<typename T>
ostream& operator<<(ostream& os, const forward_list<T>& lst) {
    os << "[ ";
    bool first = true;
    for (auto& x : lst) {
        if (!first) os << ", ";
        os << x;
        first = false;
    }
    os << " ]";
    return os;
}

// array
template<typename T, size_t N>
ostream& operator<<(ostream& os, const array<T, N>& a) {
    os << "[ ";
    for (size_t i = 0; i < N; i++) {
        os << a[i];
        if (i + 1 < N) os << ", ";
    }
    os << " ]";
    return os;
}

// set
template<typename T, typename Comp, typename Alloc>
ostream& operator<<(ostream& os, const set<T, Comp, Alloc>& s) {
    os << "{ ";
    size_t i = 0;
    for (auto& x : s) {
        os << x;
        if (++i < s.size()) os << ", ";
    }
    os << " }";
    return os;
}

// vector
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[ ";
    for (size_t i = 0; i < v.size(); i++) {
        os << v[i];
        if (i + 1 < v.size()) os << ", ";
    }
    os << " ]";
    return os;
}

template<typename T>
ostream& operator<<(ostream& os, const unordered_set<T>& s) {
    os << "{ ";
    size_t i = 0;
    for (auto& x : s) {
        os << x;
        if (++i < s.size()) os << ", ";
    }
    os << " }";
    return os;
}

// map
template<typename K, typename V>
ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{ ";
    size_t i = 0;
    for (auto& [k,v] : m) {
        os << k << ": " << v;
        if (++i < m.size()) os << ", ";
    }
    os << " }";
    return os;
}
template<typename K, typename V>
ostream& operator<<(ostream& os, const unordered_map<K,V>& m) {
    os << "{ ";
    size_t i = 0;
    for (auto& [k,v] : m) {
        os << k << ": " << v;
        if (++i < m.size()) os << ", ";
    }
    os << " }";
    return os;
}
// ====================
// vector 判定
// 2次元 vector を debug 用に判定＆整形出力
// ====================
template<class T>
struct is_vector : std::false_type {};

template<class U, class Alloc>
struct is_vector<std::vector<U, Alloc>> : std::true_type {};

// T が vector< vector<...> > なら true
template<class T>
struct is_2d_vector : std::false_type {};

template<class U, class Alloc>
struct is_2d_vector<std::vector<U, Alloc>> : is_vector<U> {};

// T が 1次元 vector なら true
template<class T>
struct is_1d_vector : std::false_type {};

template<class U, class Alloc>
struct is_1d_vector<std::vector<U, Alloc>>
    : std::bool_constant<!is_vector<U>::value> {};

// debug 表示モード
enum class DebugPrintMode {
    Normal,   // いつもの1行表示
    Index0,   // 0始まり番号つき縦表示
    Index1    // 1始まり番号つき縦表示
};


template<class T>
struct is_set_like : std::false_type {};

template<class K, class Comp, class Alloc>
struct is_set_like<std::set<K, Comp, Alloc>> : std::true_type {};

template<class K, class Comp, class Alloc>
struct is_set_like<std::multiset<K, Comp, Alloc>> : std::true_type {};

template<class K, class Hash, class KeyEq, class Alloc>
struct is_set_like<std::unordered_set<K, Hash, KeyEq, Alloc>> : std::true_type {};

template<class K, class Hash, class KeyEq, class Alloc>
struct is_set_like<std::unordered_multiset<K, Hash, KeyEq, Alloc>> : std::true_type {};



// ====================
// map 系判定
// ====================

template<class T>
struct is_map_like : std::false_type {};

template<class K, class V, class Comp, class Alloc>
struct is_map_like<std::map<K, V, Comp, Alloc>> : std::true_type {};

template<class K, class V, class Comp, class Alloc>
struct is_map_like<std::multimap<K, V, Comp, Alloc>> : std::true_type {};

template<class K, class V, class Hash, class KeyEq, class Alloc>
struct is_map_like<std::unordered_map<K, V, Hash, KeyEq, Alloc>> : std::true_type {};

template<class K, class V, class Hash, class KeyEq, class Alloc>
struct is_map_like<std::unordered_multimap<K, V, Hash, KeyEq, Alloc>> : std::true_type {};

template<class MapLike>
void print_indexed_map(std::ostream& os, const MapLike& mp, size_t start_index) {
    os << "\n";
    size_t idx = start_index;
    bool first = true;
    for (auto&& [k, v] : mp) {
        if (!first) os << "\n";
        os << COLOR_CYAN << idx++
           << COLOR_WHITE << ": { "
           << COLOR_BLUE << k
           << COLOR_WHITE << ": " << v << " }";
        first = false;
    }
}

template<class SetLike>
void print_indexed_set(std::ostream& os, const SetLike& st, size_t start_index) {
    os << "\n";
    size_t idx = start_index;
    bool first = true;
    for (const auto& x : st) {
        if (!first) os << "\n";
        os << COLOR_CYAN << idx++
           << COLOR_WHITE << ": " << x;
        first = false;
    }
}

template<class U>
void print_braced_vector(std::ostream& os, const std::vector<U>& v) {
    os << "{ ";
    for (size_t j = 0; j < v.size(); ++j) {
        os << v[j];
        if (j + 1 < v.size()) os << ", ";
    }
    os << " }";
}

// 1次元 vector を番号つきで表示する関数
template<class U>
void print_indexed_vector(std::ostream& os, const std::vector<U>& v, size_t start_index) {
    os << "\n";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i == 0) {
            os << COLOR_BLUE << (start_index + i)
               << COLOR_WHITE << ":[ " << v[i];
        } else {
            os << ",\n"
               << COLOR_BLUE << (start_index + i)
               << COLOR_WHITE << ":  " << v[i];
        }
    }
    os << " ]";
}

// 通常変数
template<typename T>
void debug_dispatch(const char* name, const T& x,
                    DebugPrintMode mode = DebugPrintMode::Normal) {
    size_t start_index = 0;
    if (mode == DebugPrintMode::Index1) start_index = 1;

    // 2次元 vector
    if constexpr (is_2d_vector<T>::value) {
        cerr << COLOR_YELLOW << name << COLOR_RESET << " :\n";
        size_t idx = start_index;
        for (size_t i = 0; i < x.size(); ++i) {
            cerr << COLOR_CYAN << idx++ << COLOR_WHITE << " : ";
            print_braced_vector(cerr, x[i]);
            cerr << COLOR_RESET << "\n";
        }
    }
    // 1次元 vector
    else if constexpr (is_1d_vector<T>::value) {
        if (mode == DebugPrintMode::Index0 || mode == DebugPrintMode::Index1) {
            cerr << COLOR_YELLOW << name << COLOR_WHITE << " :";
            print_indexed_vector(cerr, x, start_index);
            cerr << COLOR_RESET << "\n";
        } else {
            cerr << COLOR_YELLOW << name << COLOR_WHITE << " : "
                 << x << COLOR_RESET << "\n";
        }
    }
    // map 系
    else if constexpr (is_map_like<T>::value) {
        if (mode == DebugPrintMode::Index0 || mode == DebugPrintMode::Index1) {
            cerr << COLOR_YELLOW << name << COLOR_WHITE << " :";
            print_indexed_map(cerr, x, start_index);
            cerr << COLOR_RESET << "\n";
        } else {
            cerr << COLOR_YELLOW << name << COLOR_WHITE << " : "
                 << x << COLOR_RESET << "\n";
        }
    }
    // set 系
    else if constexpr (is_set_like<T>::value) {
        if (mode == DebugPrintMode::Index0 || mode == DebugPrintMode::Index1) {
            cerr << COLOR_YELLOW << name << COLOR_WHITE << " :";
            print_indexed_set(cerr, x, start_index);
            cerr << COLOR_RESET << "\n";
        } else {
            cerr << COLOR_YELLOW << name << COLOR_WHITE << " : "
                 << x << COLOR_RESET << "\n";
        }
    }
    // それ以外
    else {
        cerr << COLOR_YELLOW << name << COLOR_WHITE << " : "
             << x << COLOR_RESET << "\n";
    }
}

template<class PQ>
void debug_pq_impl(const char* name, PQ pq, size_t start_index) {
    cerr << COLOR_MAGENTA << name << " ----------" << COLOR_RESET << "\n";
    size_t idx = start_index;
    while (!pq.empty()) {
        cerr << COLOR_CYAN << idx++ << COLOR_WHITE << " : "
             << pq.top() << COLOR_RESET << "\n";
        pq.pop();
    }
}

template<class Stack>
void debug_stack_impl(const char* name, Stack s, size_t start_index) {
    cerr << COLOR_MAGENTA << name << " ----------" << COLOR_RESET << "\n";
    size_t idx = start_index;
    while (!s.empty()) {
        cerr << COLOR_CYAN << idx++ << COLOR_WHITE << " : "
             << s.top() << COLOR_RESET << "\n";
        s.pop();
    }
}


template<class Queue>
void debug_queue_impl(const char* name, Queue q, size_t start_index) {
    cerr << COLOR_MAGENTA << name << " ----------" << COLOR_RESET << "\n";
    size_t idx = start_index;
    while (!q.empty()) {
        cerr << COLOR_CYAN << idx++ << COLOR_WHITE << " : "
             << q.front() << COLOR_RESET << "\n";
        q.pop();
    }
}

template<class Iterable>
void print_indexed_iterable(std::ostream& os, const Iterable& c, size_t start_index) {
    os << "\n";
    size_t idx = start_index;
    bool first = true;
    for (const auto& x : c) {
        if (!first) os << "\n";
        os << COLOR_CYAN << idx++
           << COLOR_WHITE << ": " << x;
        first = false;
    }
}

// 複数変数
template<typename T>
void debug_single(DebugPrintMode mode, const char* name, const T& x) {
    debug_dispatch(name, x, mode);
}

template<typename... Args>
void debug_multi(DebugPrintMode mode, const char* names, Args&&... args) {
    stringstream ss(names);
    string name;
    ((getline(ss, name, ','), debug_single(mode, trim(name).c_str(), args)), ...);
}



// メインマクロ
#define debug(...) \
    do { \
        cerr << COLOR_CYAN << "debug ----------<< start" << COLOR_RESET << "\n"; \
        debug_multi(DebugPrintMode::Normal, #__VA_ARGS__, __VA_ARGS__); \
    } while (0)

#define debug_opt(mode, ...) \
    do { \
        cerr << COLOR_CYAN << "debug ----------<< start" << COLOR_RESET << "\n"; \
        debug_multi(mode, #__VA_ARGS__, __VA_ARGS__); \
    } while (0)

#define debug_idx0(...) \
    do { \
        cerr << COLOR_CYAN << "debug ----------<< start" << COLOR_RESET << "\n"; \
        debug_multi(DebugPrintMode::Index0, #__VA_ARGS__, __VA_ARGS__); \
    } while (0)

#define debug_idx1(...) \
    do { \
        cerr << COLOR_CYAN << "debug ----------<< start" << COLOR_RESET << "\n"; \
        debug_multi(DebugPrintMode::Index1, #__VA_ARGS__, __VA_ARGS__); \
    } while (0)

// queue
#define debug_queue(q) \
    do { \
        auto temp = q; int idx = 0; \
        cerr << COLOR_MAGENTA << #q << " ----------" << COLOR_RESET << "\n"; \
        while (!temp.empty()) { \
            cerr << COLOR_CYAN << idx++ << COLOR_WHITE << " : " \
                 << temp.front() << COLOR_RESET << "\n"; \
            temp.pop(); \
        } \
    } while (0)

// stack
#define debug_stack(s) \
    do { \
        auto temp = s; int idx = 0; \
        cerr << COLOR_MAGENTA << #s << " ----------" << COLOR_RESET << "\n"; \
        while (!temp.empty()) { \
            cerr << COLOR_CYAN << idx++ << COLOR_WHITE << " : " \
                 << temp.top() << COLOR_RESET << "\n"; \
            temp.pop(); \
        } \
    } while (0)

// priority_queue
#define debug_pq(pq) \
    do { \
        auto temp = pq; int idx = 0; \
        cerr << COLOR_MAGENTA << #pq << " ----------" << COLOR_RESET << "\n"; \
        while (!temp.empty()) { \
            cerr << COLOR_CYAN << idx++ << COLOR_WHITE << " : " \
                 << temp.top() << COLOR_RESET << "\n"; \
            temp.pop(); \
        } \
    } while (0)

#else
#define debug(...)
#define debug_opt(...)
#define debug_idx0(...)
#define debug_idx1(...)
#define debug_queue(q)
#define debug_stack(s)
#define debug_pq(pq)
#endif



// // 型情報出力
// #include <boost/type_index.hpp>
// template<typename T>
// void debug_typeinfo(const string& name) {
//     using boost::typeindex::type_id_with_cvr;
//     cout << COLOR_CYAN << "Type info for " << name << " ----------" << COLOR_RESET << "\n";
//     // cout << "  type   : " << type_id_with_cvr<T>().pretty_name() << "\n";
//     // cout << "  sizeof : " << sizeof(T) << " bytes\n";
//     cout << COLOR_YELLOW << "  type   : " << COLOR_WHITE << type_id_with_cvr<T>().pretty_name() << "\n";
//     cout << COLOR_YELLOW << "  sizeof : " << COLOR_WHITE << sizeof(T) << " bytes\n";

//     if constexpr (std::numeric_limits<T>::is_specialized) {
//         if constexpr (std::is_integral_v<T>) {
//             cout << COLOR_YELLOW << "  min    : " << COLOR_GREEN << format_int_with_exp(numeric_limits<T>::min()) << COLOR_RESET << "\n";
//             cout << COLOR_YELLOW << "  max    : " << COLOR_GREEN << format_int_with_exp(numeric_limits<T>::max()) << COLOR_RESET << "\n";
//             // cout << "  min    : " << format_int_with_exp(numeric_limits<T>::min()) << "\n";
//             // cout << "  max    : " << format_int_with_exp(numeric_limits<T>::max()) << "\n";
//         } else if constexpr (std::is_floating_point_v<T>) {
//             cout << COLOR_YELLOW << "  min    : " << COLOR_GREEN << format_float_with_exp(numeric_limits<T>::min()) << COLOR_RESET << "\n";
//             cout << COLOR_YELLOW << "  max    : " << COLOR_GREEN << format_float_with_exp(numeric_limits<T>::max()) << COLOR_RESET << "\n";
//             // cout << "  min    : " << format_float_with_exp(numeric_limits<T>::min()) << "\n";
//             // cout << "  max    : " << format_float_with_exp(numeric_limits<T>::max()) << "\n";
//         }
//     } else {
//         cout << "  min    : (not available)\n";
//         cout << "  max    : (not available)\n";
//     }
//     cout << "----------------------------------\n";
// }



using ll = long long;
[[maybe_unused]] const int INF = 1e9;        // 非常に大きい値（= 到達不能な値）
[[maybe_unused]] const long long LINF = 1e18; // long long 用の無限
[[maybe_unused]] const int NINF = -INF;      // 非常に小さい値（最小化の比較など）
// #include <limits>
// const int  INF  = std::numeric_limits<int>::max()/2;   // +∞ 代用
// const int  NEG  = std::numeric_limits<int>::min()/2;   // −∞ 代用
// const ll   LINF = std::numeric_limits<long long>::max()/4; // 64bit 版
// /2 /4 しておくと 加算してもオーバーフローしない
// long long gcd(long long a, long long b){
//     while (b != 0){
//         long long r = a % b;
//         a = b;
//         b = r;
//     }
//     return a;  // 最終的に最大公約数が入っている
// }

// long long lcm(long long a, long long b){
//     // 先に a で割るとオーバーフロー防止
//     // return a / gcd(a, b) * b;
//     // N (10^18 以上) → long long では危険
//     return ( (__int128)a / gcd(a, b) ) * b;
// }
// ====================
// 進数
// ====================
// #include <iostream>
// #include <bitset> // bitsetを使うために必要
// #include <iomanip>// setw(10) を使うのに必要
// using namespace std;
// -------------------------------------------50|
void sinsu() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int n = 0;
    cout << "進数表" << endl;
    for(int n = 0; n <= 255; ++n){
        cout << setw(10)
            <<n << " : 2進数 / "
            << bitset<8>(n) // 桁数<8>
            // << endl;
            << '\n';
    }
    return;
}
// ====================
// main 部分
// ====================
// https://atcoder.jp/contests/adt_easy_20231130_2/tasks
// -------------------------------------------50|
// #include <bits/stdc++.h>
// using namespace std;
// using ll = long long;
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    cin >> N >> M;
    vector<string> S(N);
    for(auto& s:S)cin >> s;
    debug_idx0(S);
    queue<pair<int,int>> dot;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j){
            if(S[i][j] == '.'){
                dot.push({i,j});
            }
        }
    }
    debug_queue(dot);
    if(!dot.empty()){
        int checkCon = 0;
        while(true){
            // cerr << "# ループ開始 -------------------------------" << '\n';
            auto A = dot.front();
            dot.pop();
            // debug_queue(dot);
            int i = A.first;
            int j = A.second;
            // debug(i,j,N);
            if(N == i+1){
                dot.push({i,j});
                checkCon++;
                if(checkCon == dot.size())break;
                continue;
            }
            if(S[i+1][j] =='#'){
                S[i][j] = '#';
                S[i+1][j] = '.';
                dot.push({i+1,j});
                checkCon = 0; // カウントリセット
            }else{
                dot.push({i,j});
                // １周チェック用 ------|
                checkCon++;
                if(checkCon == dot.size())break;
            }
        }
        while(true){
            auto A = dot.front();
            dot.pop();
            int i = A.first;
            int j = A.second;
            if(M == j+1){
                dot.push({i,j});
                checkCon++;
                if(checkCon == dot.size())break;
                continue;
            }
            if(S[i][j+1] =='#'){
                S[i][j] = '#';
                S[i][j+1] = '.';
                dot.push({i,j+1});
                checkCon = 0; // カウントリセット
            }else{
                dot.push({i,j});
                // １周チェック用 ------|
                checkCon++;
                if(checkCon == dot.size())break;
            }
        }
    }

    for(int i = 0; i < N; ++i){
        cout << S[i] << '\n';
    }
    return 0;
}

/* デバッグで使えるもの ---
    // 型例 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
    int x = 3;r
    long long y = 100;
    double z = 2.5;
    string s = "abc";
    pair<int, int> p = {2, 5};
    tuple<int, string, double> t = {1, "cat", 3.14};
    vector<int> v = {10, 20, 30};
    vector<vector<int>> g = {{1, 2}, {3}, {4, 5}};
    set<int> st = {3, 1, 4};

    stack<int> stc;
    stc.push(10);
    stc.push(20);
    stc.push(30);
    unordered_set<int> us = {8, 2, 5};
    map<int, string> mp = {{1, "one"}, {2, "two"}};
    unordered_map<int, string> ump = {{3, "three"}, {4, "four"}};
    deque<int> dq = {10, 20, 30};
    list<int> lst = {10, 20, 30};
    forward_list<int> flst = {10, 20, 30};
    array<int, 3> a = {10, 20, 30};
    multiset<int> ms = {3, 1, 3, 2};
    multimap<int, string> mm;
    mm.emplace(1, "one");
    mm.emplace(1, "uno");
    mm.emplace(2, "two");
    \\ デバッグの書き方_____________________
    debug(x,y,z,s,p,t,v,g,st,us,mp,ump,dq,lst,flst,a,ms,mm);
    debug_idx0(v);
    debug_idx1(v);
    debug_idx0(mp);
    debug_idx1(mp);
    // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    // 型例 以下は下記でバッグで出力できる~~~~~
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);

    debug_queue(q);
    stack<int> st2;
    st2.push(10);
    st2.push(20);
    st2.push(30);

    debug_stack(st2);
    priority_queue<int> pq;
    pq.push(5);
    pq.push(1);
    pq.push(9);

    \\ デバッグの書き方_____________________
    debug_pq(pq);

    debug_idx0(v, mp, ump, us, st);
    debug_queue(q);
    debug_stack(st2);
    debug_pq(pq);
    // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    // 型情報 ____________________________
    debug_typeinfo<int>("int");
    debug_typeinfo<double>("double");
    debug_type_list();
    // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
*/
/*
x が増えれば y も増えるとき，その関数は単調増加と言う
広義単調増加 x1 < x2 ならば f(x1) <= f(x2)
狭義単調増加 x1 < x2 ならば f(x1) <  f(x2)
*/

//dbg-
//ord-
// ./c < in.txt