#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

using mint = modint998244353;

struct RedCerr : public streambuf {
    streambuf* orig;
    bool line_start = true;
    RedCerr() : orig(cerr.rdbuf()) { cerr.rdbuf(this); }
    ~RedCerr() { cerr.rdbuf(orig); }
    int overflow(int c) override {
        if (c == EOF) return c;
        if (line_start) {
            string red = "\033[31m";
            orig->sputn(red.c_str(), red.size());
            line_start = false;
        }
        orig->sputc(c);
        if (c == '\n') {
            string reset = "\033[0m";
            orig->sputn(reset.c_str(), reset.size());
            line_start = true;
        }
        return c;
    }
} red_cerr;


//int64_t
using lint = int64_t;

//long double
using ld = long double;

//ベクター
template<typename T> using vc = vector<T>; //1次元リスト
template<typename T> using vv = vector<vector<T>>; //2次元リスト
template<typename T> using vvv = vector<vector<vector<T>>>; //3次元リスト
template<typename T> using vvvv = vector<vector<vector<vector<T>>>>; //4次元リスト

//ペア
using pll = pair<int64_t, int64_t>;

//プライオリティーキュー
template<typename T> using pq = priority_queue<T, vector<T>>; // 大きい順
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>; // 小さい順

#define pb push_back
#define mp make_pair
#define fi first
#define se second

//all マクロ
#define all(v) (v).begin(), (v).end()

//ループマクロ
#define     re(n)       for (int64_t r_= 0;            r_<  int64_t(n);r_++)
#define    rep(i, n)    for (int64_t i = 0;            i <  int64_t(n); i++)
#define   repp(i, n)    for (int64_t i = 0;            i <= int64_t(n); i++)
#define   rrep(i, a, b) for (int64_t i = int64_t(a);   i <  int64_t(b); i++)
#define  rrepp(i, a, b) for (int64_t i = int64_t(a);   i <= int64_t(b); i++)
#define   reep(i, n)    for (int64_t i = int64_t(n)-1; i >= 0;          i--)
#define  reepp(i, n)    for (int64_t i = int64_t(n);   i >= 0;          i--)
#define  rreep(i, a, b) for (int64_t i = int64_t(b)-1; i >= int64_t(a); i--)
#define rreepp(i, a, b) for (int64_t i = int64_t(b);   i >= int64_t(a); i--)

//sizeをint64_t型に
#define sz(x) ((int64_t)x.size())

//next_permutation
#define next_p(v) next_permutation((v).begin(), (v).end())


//無限
const int64_t inf = 1001001001;
const int64_t INF = 4004004004004004004LL;

//モッド
const int64_t MOD = 998244353;
//const int64_t MOD = 1000000007;

//パイ
const long double pi = 3.141592653589793238L;

//ネイピア数
const long double napier = 2.7182818284590452353L;

//移動
static constexpr int64_t dh[] = {0, -1, 0, 1, -1, -1, 1, 1, 0};
static constexpr int64_t dw[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};



//cin cout オーバーロード
//vector
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T & in : v) is >> in;
    return is;
}
template <typename T>
ostream &operator<<(ostream & os, const vector<T> &v) {
    for (int64_t i = 0; i < (int64_t)v.size(); i++) {
        os << v[i] << (i + 1 != (int64_t)v.size() ? " " : "");
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
    for (int64_t i = 0; i < (int64_t)v.size(); i++) {
        os << v[i] << endl;
    }
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v) {
    for (int64_t i = 0; i < (int64_t)v.size(); i++) {
        os << "i = " << i << endl;
        os << v[i];
    }
    return os;
}

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


//vector複数行受け取り
template <typename T1, typename T2>
void vcin(vector<T1> &u, vector<T2> &v) {
    if (u.size() != v.size()) {
        cerr << "vcinエラー サイズが異なります" << endl;
        assert(false);
        return;
    }
    for (int64_t i = 0; i < (int64_t)u.size(); i++) {
        cin >> u[i] >> v[i];
    }
    return;
}
template <typename T1, typename T2, typename T3>
void vcin(vector<T1> &u, vector<T2> &v, vector<T3> &w) {
    if (u.size() != v.size() || v.size() != w.size()) {
        cerr << "vcinエラー サイズが異なります" << endl;
        assert(false);
        return;
    }
    for (int64_t i = 0; i < (int64_t)u.size(); i++) {
        cin >> u[i] >> v[i] >> w[i];
    }
    return;
}


//Yes No出力
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;

void YN (bool b) {
    if (b) cout << "YES" << endl;
    else cout << "NO" << endl;
    return;
}
void yn (bool b) {
    if (b) cout << "Yes" << endl;
    else cout << "No" << endl;
    return;
}



// 値の更新
template<typename T1, typename T2>
bool chmax(T1 &x, const T2 &y) {
    bool compare = x < y;
    if (compare) x = y;
    return compare;
}
template<typename T1, typename T2>
bool chmin(T1 &x, const T2 &y) {
    bool compare = x > y;
    if (compare) x = y;
    return compare;
}

//経過時間
long double Time () {
    return 1.0 * (clock()) / CLOCKS_PER_SEC;
}


//小さい順
template<typename T>
void Vsort (vector<T> &v) {
    sort(v.begin(), v.end());
    return;
}
//大きい順
template<typename T>
void Vsortg (vector<T> &v) {
    sort(v.rbegin(), v.rend());
    return;
}

//リバース
template<typename T>
void Vreverse (vector<T> &v) {
    reverse(v.begin(), v.end());
    return;
}

//重複の削除
template<typename T>
void Vunique (vector<T> &v) {
    #ifndef ONLINE_JUDGE
    static bool w = false;
    if (!w) { cerr << "Vuniqueでは必ずソートされてますか？" << endl; w = true; }
    #endif
    v.erase(unique(v.begin(), v.end()), v.end());
    return;
}

//上下反転
template<typename T>
void UDflip (vector<vector<T>> &v) {
    reverse(v.begin(), v.end());
    return;
}

//左右反転
template<typename T>
void LRflip (vector<vector<T>> &v) {
    for (auto &x : v) {
        reverse(x.begin(), x.end());
    }
    return;
}

//リストの移動
template<typename T>
void Vrotate (vector<T> &v, int64_t n) {
    if (v.empty()) return;
    n %= (int64_t)v.size();
    rotate(v.begin(), v.begin() + n, v.end());
    return;
}

//右回転
template<typename T>
void VVrotate (vector<vector<T>> &v) {
    int64_t H = v[0].size();
    int64_t W = v.size();
    vector<vector<T>> L(H, vector<T>(W));
    for (int64_t i = 0; i < W; i++) {
        for (int64_t j = 0; j < H; j++) {
            L[j][W - i - 1] = v[i][j];
        }
    }
    v = L;
    return;
}

//左回転
template<typename T>
void VVrotateg (vector<vector<T>> &v) {
    int64_t H = v[0].size();
    int64_t W = v.size();
    vector<vector<T>> L(H, vector<T>(W));
    for (int64_t i = 0; i < W; i++) {
        for (int64_t j = 0; j < H; j++) {
            L[H - j - 1][i] = v[i][j];
        }
    }
    v = L;
    return;
}


//2次元距離
template<typename T>
long double distan (T x1, T y1, T x2, T y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
//2次元距離の2乗
template<typename T>
T distan2 (T x1, T y1, T x2, T y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

//範囲内チェック
#define in_grid(h, w, H, W) if (!(0 <= h && 0 <= w && h < H && w < W)) continue;


//nPr
int64_t nPr (int64_t n, int64_t r) {
    int64_t Ans = 1;
    for (int64_t i = 0; i < r; i++) {
        Ans *= n - i;
    }
    return Ans;
}

//nCr
vector<vector<int64_t>> nCr_memo;
int64_t nCr (int64_t n, int64_t r) {
    if (n < r) {
        cerr << "Error nCrのrがnより大きいです" << endl;
        assert(false);
        return 0;
    }
    for (int64_t i = (int64_t)nCr_memo.size(); i <= n; i++) {
        nCr_memo.push_back(vector<int64_t>(i + 1, 1));
        for (int64_t j = 1; j < i; j++) {
            nCr_memo[i][j] = nCr_memo[i - 1][j - 1] + nCr_memo[i - 1][j];
        }
    }
    return nCr_memo[n][r];
}

//累乗
int64_t power (int64_t a, int64_t b) {
    int64_t Ans = 1;
    while (b > 0) {
        if (b & 1) Ans *= a;
        a *= a;
        b >>= 1;
    }
    return Ans;
}

//階乗
int64_t factorial(int64_t n) {
    int64_t Ans = 1;
    for (int64_t i = 1; i <= n; i++) Ans *= i;
    return Ans;
}

//数値のN桁目
int64_t digit(int64_t x, int64_t k) {
    while (k--) x /= 10;
    return x % 10;
}


//!MOD関連の関数 ここをベースに使用することもあるので 消さないこと

//MOD累乗
int64_t Mpower(int64_t a, int64_t b, int64_t mod) {
    int64_t Ans = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) Ans = (Ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return Ans;
}

//int128のMOD累乗
__int128_t MPOWER(__int128_t a, __int128_t b, __int128_t mod) {
    __int128_t Ans = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) Ans = (Ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return Ans;
}


//ミラーラビンの素数判定 int128MOD累乗
bool is_prime(int64_t N) {
    if (N <= 1) return false;
    if (N == 2) return true;
    if (N % 2 == 0) return false;
    vector<int64_t> L = {2, 7, 61};
    if (N >= 4759123141LL) L = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    int64_t s = 0, d = N - 1;
    while (d % 2 == 0) {
        s++;
        d >>= 1;
    }
    for (auto x : L) {
        if (N <= x) return true;
        int64_t t, p = MPOWER(x, d, N);
        if (p != 1) {
            for (t = 0; t < s; t++) {
                if (p == N - 1) break;
                p = __int128_t(p) * p % N;
            }
            if (t == s) return false;
        }
    }
    return true;
}


static constexpr int64_t seg_MOD = 998244353;
static constexpr int64_t seg_ID = -8'000'000'000'000'000'000LL;

constexpr int64_t sum_op (int64_t a, int64_t b) { return (a + b); }
constexpr int64_t mul_op (int64_t a, int64_t b) { return (a * b); }
constexpr int64_t SUM_op (int64_t a, int64_t b) { return (a + b) % seg_MOD; }
constexpr int64_t MUL_op (int64_t a, int64_t b) { return (a * b) % seg_MOD; }
          string  txt_op (string  a, string  b) { return (a + b); }
constexpr int64_t min_op (int64_t a, int64_t b) { return min(a , b); }
constexpr int64_t max_op (int64_t a, int64_t b) { return max(a , b); }
constexpr int64_t lcm_op (int64_t a, int64_t b) { return lcm(a , b); }
constexpr int64_t gcd_op (int64_t a, int64_t b) { return gcd(a , b); }
constexpr int64_t and_op (int64_t a, int64_t b) { return (a & b); }
constexpr int64_t or_op  (int64_t a, int64_t b) { return (a | b); }
constexpr int64_t xor_op (int64_t a, int64_t b) { return (a ^ b); }
constexpr pair<int64_t, int64_t> sum_OP (pair<int64_t, int64_t> a, pair<int64_t, int64_t> b)
    { return {sum_op(a.first, b.first), a.second + b.second}; }

constexpr int64_t no0_e () { return 0; }
constexpr int64_t no1_e () { return 1; }
constexpr int64_t all_e () { return -1; }
          string  emp_e () { return ""; }
constexpr int64_t max_e () { return  4'000'000'000'000'000'000LL; }
constexpr int64_t min_e () { return -4'000'000'000'000'000'000LL; }
constexpr pair<int64_t, int64_t> no0_E () { return {0, 0}; }

constexpr int64_t add_map (int64_t f, int64_t x) { return x + f; }
constexpr int64_t upd_map (int64_t f, int64_t x) { return f == seg_ID ? x : f; }
constexpr pair<int64_t, int64_t> add_MAP (int64_t f, pair<int64_t, int64_t> x) { x.first += f * x.second; return x; }
constexpr pair<int64_t, int64_t> upd_MAP (int64_t f, pair<int64_t, int64_t> x) { if (f != seg_ID) x.first = f * x.second; return x; }

constexpr int64_t add_com (int64_t f, int64_t g) { return g + f; }
constexpr int64_t upd_com (int64_t f, int64_t g) { return f == seg_ID ? g : f; }

constexpr int64_t no0_id () { return 0; }
constexpr int64_t upd_id () { return seg_ID; }

//セグ木
using sumtree = segtree<int64_t, sum_op, no0_e>;
using multree = segtree<int64_t, mul_op, no1_e>;
using txttree = segtree<string , txt_op, emp_e>;
using mintree = segtree<int64_t, min_op, max_e>;
using maxtree = segtree<int64_t, max_op, min_e>;
using lcmtree = segtree<int64_t, lcm_op, no1_e>;
using gcdtree = segtree<int64_t, gcd_op, no0_e>;
using andtree = segtree<int64_t, and_op, all_e>;
using ortree  = segtree<int64_t, or_op,  no0_e>;
using xortree = segtree<int64_t, xor_op, no0_e>;
using summodtree = segtree<int64_t, SUM_op, no0_e>;
using mulmodtree = segtree<int64_t, MUL_op, no1_e>;

//遅延セグ木
using lazyaddsum = lazy_segtree<pair<int64_t, int64_t>, sum_OP, no0_E, int64_t, add_MAP, add_com, no0_id>;
using lazyupdsum = lazy_segtree<pair<int64_t, int64_t>, sum_OP, no0_E, int64_t, upd_MAP, upd_com, upd_id>;
using addmintree = lazy_segtree<int64_t, min_op, max_e, int64_t, add_map, add_com, no0_id>;
using updmintree = lazy_segtree<int64_t, min_op, max_e, int64_t, upd_map, upd_com, upd_id>;
using addmaxtree = lazy_segtree<int64_t, max_op, min_e, int64_t, add_map, add_com, no0_id>;
using updmaxtree = lazy_segtree<int64_t, max_op, min_e, int64_t, upd_map, upd_com, upd_id>;

struct addsumtree : lazyaddsum {
    addsumtree (int64_t n) : lazyaddsum(vector<pair<int64_t, int64_t>>(n, {0, 1})) {}
    addsumtree (vector<int64_t> v) : lazyaddsum([&]{
        vector<pair<int64_t, int64_t>> p(v.size());
        for (int64_t i = 0; i < (int64_t)v.size(); i++) p[i] = {v[i], 1};
        return p;
    }()) {}
    int64_t prod(int l, int r) { return lazyaddsum::prod(l, r).first; }
    int64_t all_prod() { return lazyaddsum::all_prod().first; }
};
struct updsumtree : lazyupdsum {
    updsumtree (int64_t n) : lazyupdsum(vector<pair<int64_t, int64_t>>(n, {0, 1})) {}
    updsumtree (vector<int64_t> v) : lazyupdsum([&]{
        vector<pair<int64_t, int64_t>> p(v.size());
        for (int64_t i = 0; i < (int64_t)v.size(); i++) p[i] = {v[i], 1};
        return p;
    }()) {}
    int64_t prod(int l, int r) { return lazyupdsum::prod(l, r).first; }
    int64_t all_prod() { return lazyupdsum::all_prod().first; }
};



template <typename T, typename op>
struct SparseTable {
    int N, K;
    vector<int> log_table;
    vector<vector<T>> table;
    op f;
    SparseTable(const vector<T> &A, op f) : f(f) {
        N = A.size();
        K = 0;
        while ((1 << (K + 1)) <= N) ++K;
        table.resize(K + 1);
        table[0] = A;
        for (int k = 0; k < K; ++k) {
            int m = N - (1 << (k + 1)) + 1;
            table[k + 1].resize(m);
            for (int i = 0; i < m; ++i) {
                table[k + 1][i] =f(table[k][i], table[k][i + (1 << k)]);
            }
        }
        log_table.resize(N + 1);
        for (int k = 0; k <= K; ++k) {
            int s = (1 << k), t =min((1 << (k + 1)) - 1, N);
            for (int i = s; i <= t; ++i) {
                log_table[i] = k;
            }
        }
    }
    T query(int L, int R) const {
        int k = log_table[R - L];
        return f(table[k][L], table[k][R - (1 << k)]);
    }
};



vector<int64_t> primel (int64_t a) {
    int64_t b = a;
    vector<int64_t> L;
    for (int i = 2; i < sqrt(b); i++)
        while (a % i == 0)
            {a /= i; L.push_back(i);}
    if (a != 1) L.push_back(a);
    return L;
} //素因数分解primel

vector<pair<int64_t, int64_t>> primell (int64_t a) {
    int64_t b = a;
    vector<pair<int64_t, int64_t>> L;
    for (int i = 2; i <= sqrt(b); i++) {
        int c = 0;
        while (a % i == 0) {
        a /= i; c++;
        }
        if (c != 0) L.push_back(make_pair(i, c));
    }
    if (a != 1) L.push_back(make_pair(a, 1));
    return L;
} //素因数分解_指数まとめprimell

int64_t primec (int64_t a) {
    int64_t b = a, c = 0;
    for (int i = 2; i < sqrt(b); i++)
        while (a % i == 0) {a /= i; c++;}
    if (a != 1) c++;
    return c;
} //素因数数primec

void factor_RF (vector<int64_t> &l, vector<pair<int64_t, int64_t>> L, int64_t s, int64_t n, int64_t N) {
    if (n == N) l.push_back(s);
    else {
        for (int i = 0; i <= L[n].second; i++) {
            factor_RF(l, L, s * pow(L[n].first, i), n + 1, N);
        }
    }
    return;
}
vector<int64_t> factorl (int64_t a) {
    vector<int64_t> L;
    factor_RF(L, primell(a), 1, 0, primell(a).size());
    sort(all(L));
    return L;
} //因数factorl

int64_t factorc (int64_t a) {
    vector<pair<int64_t, int64_t>> L = primell(a);
    int64_t b = 1;
    for (auto x : L) {
        b *= x.second + 1;
    }
    return b;
} //因数数factorc


//!####################################################################################################


//フリーセグ木
//区間和の例
using seg_s = int64_t;
constexpr seg_s seg_op (seg_s a, seg_s b) {
    return a + b;
}
constexpr seg_s seg_e () {
    return 0;
}
using segtre = segtree<seg_s, seg_op, seg_e>;

//フリー遅延セグ木（サイズ持ち
//区間加算操作・区間和取得の例
using leg_s = pair<int64_t, int64_t>;
constexpr leg_s leg_op (leg_s a, leg_s b) { //演算
    auto x = a.first, y = b.first;//
    auto z = x + y;
    return {z, a.second + b.second};//
}
constexpr leg_s leg_e () { //初期値（単位元
    return {0, 0};
}
#define leg_f int64_t
constexpr leg_s leg_map (leg_f f, leg_s x) { //遅延後の操作
    auto a = x.first, size = x.second;//
    return {a + size * f, size};
}
constexpr leg_f leg_com (leg_f f, leg_f g) { //遅延の重ね方
    return g + f;
}
constexpr leg_f leg_id () { //遅延の単位元
    return 0;
}
using lazyleg = lazy_segtree<leg_s, leg_op, leg_e, leg_f, leg_map, leg_com, leg_id>;
struct legtre : lazyleg {
    legtre (int64_t n) : lazyleg(vector<leg_s>(n, {0, 1})) {}
    legtre (vector<int64_t> v) : lazyleg([&]{
        vector<leg_s> p(v.size());
        for (int64_t i = 0; i < (int64_t)v.size(); i++) p[i] = {v[i], 1};
        return p;
    }()) {}
};



template <typename T> inline constexpr bool is_pair = false;
template <typename T1, typename T2> inline constexpr bool is_pair<pair<T1, T2>> = true;
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p);
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p);
template <typename T1, typename T2, typename T3> requires (!is_pair<T3>) pair<T1, T2> operator+(const pair<T1, T2> &p, const T3 &a);
template <typename T1, typename T2, typename T3> requires (!is_pair<T3>) pair<T1, T2> operator-(const pair<T1, T2> &p, const T3 &a);
template <typename T1, typename T2, typename T3> requires (!is_pair<T3>) pair<T1, T2> operator*(const pair<T1, T2> &p, const T3 &a);
template <typename T1, typename T2, typename T3> requires (!is_pair<T3>) pair<T1, T2> operator/(const pair<T1, T2> &p, const T3 &a);
template <typename T1, typename T2, typename T3> requires (!is_pair<T3>) pair<T1, T2> operator%(const pair<T1, T2> &p, const T3 &a);
template <typename T1, typename T2, typename T3> requires (!is_pair<T3>) pair<T1, T2> &operator+=(pair<T1, T2> &p, const T3 &a);
template <typename T1, typename T2, typename T3> requires (!is_pair<T3>) pair<T1, T2> &operator-=(pair<T1, T2> &p, const T3 &a);
template <typename T1, typename T2, typename T3> requires (!is_pair<T3>) pair<T1, T2> &operator*=(pair<T1, T2> &p, const T3 &a);
template <typename T1, typename T2, typename T3> requires (!is_pair<T3>) pair<T1, T2> &operator/=(pair<T1, T2> &p, const T3 &a);
template <typename T1, typename T2, typename T3> requires (!is_pair<T3>) pair<T1, T2> &operator%=(pair<T1, T2> &p, const T3 &a);
template <typename T1, typename T2> pair<T1, T2> &operator++(pair<T1, T2> &p);
template <typename T1, typename T2> pair<T1, T2> &operator--(pair<T1, T2> &p);
template <typename T1, typename T2> pair<T1, T2> operator++(pair<T1, T2> &p, int);
template <typename T1, typename T2> pair<T1, T2> operator--(pair<T1, T2> &p, int);
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &p1, const pair<T1, T2> &p2);
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &p1, const pair<T1, T2> &p2);
template <typename T1, typename T2> pair<T1, T2> operator*(const pair<T1, T2> &p1, const pair<T1, T2> &p2);
template <typename T1, typename T2> pair<T1, T2> operator/(const pair<T1, T2> &p1, const pair<T1, T2> &p2);
template <typename T1, typename T2> pair<T1, T2> operator%(const pair<T1, T2> &p1, const pair<T1, T2> &p2);
template <typename T1, typename T2> pair<T1, T2> &operator+=(pair<T1, T2> &p1, const pair<T1, T2> &p2);
template <typename T1, typename T2> pair<T1, T2> &operator-=(pair<T1, T2> &p1, const pair<T1, T2> &p2);
template <typename T1, typename T2> pair<T1, T2> &operator*=(pair<T1, T2> &p1, const pair<T1, T2> &p2);
template <typename T1, typename T2> pair<T1, T2> &operator/=(pair<T1, T2> &p1, const pair<T1, T2> &p2);
template <typename T1, typename T2> pair<T1, T2> &operator%=(pair<T1, T2> &p1, const pair<T1, T2> &p2);

//*pairと定数の演算
template <typename T1, typename T2, typename T3>
requires (!is_pair<T3>)
pair<T1, T2> operator+(const pair<T1, T2> &p, const T3 &a) {
    pair<T1, T2> res = p;
    res += a;
    return res;
}
template <typename T1, typename T2, typename T3>
requires (!is_pair<T3>)
pair<T1, T2> operator-(const pair<T1, T2> &p, const T3 &a) {
    pair<T1, T2> res = p;
    res -= a;
    return res;
}
template <typename T1, typename T2, typename T3>
requires (!is_pair<T3>)
pair<T1, T2> operator*(const pair<T1, T2> &p, const T3 &a) {
    pair<T1, T2> res = p;
    res *= a;
    return res;
}
template <typename T1, typename T2, typename T3>
requires (!is_pair<T3>)
pair<T1, T2> operator/(const pair<T1, T2> &p, const T3 &a) {
    pair<T1, T2> res = p;
    res /= a;
    return res;
}
template <typename T1, typename T2, typename T3>
requires (!is_pair<T3>)
pair<T1, T2> operator%(const pair<T1, T2> &p, const T3 &a) {
    pair<T1, T2> res = p;
    res %= a;
    return res;
}

template <typename T1, typename T2, typename T3>
requires (!is_pair<T3>)
pair<T1, T2> &operator+=(pair<T1, T2> &p, const T3 &a) {
    p.first += a;
    p.second += a;
    return p;
}
template <typename T1, typename T2, typename T3>
requires (!is_pair<T3>)
pair<T1, T2> &operator-=(pair<T1, T2> &p, const T3 &a) {
    p.first -= a;
    p.second -= a;
    return p;
}
template <typename T1, typename T2, typename T3>
requires (!is_pair<T3>)
pair<T1, T2> &operator*=(pair<T1, T2> &p, const T3 &a) {
    p.first *= a;
    p.second *= a;
    return p;
}
template <typename T1, typename T2, typename T3>
requires (!is_pair<T3>)
pair<T1, T2> &operator/=(pair<T1, T2> &p, const T3 &a) {
    p.first /= a;
    p.second /= a;
    return p;
}
template <typename T1, typename T2, typename T3>
requires (!is_pair<T3>)
pair<T1, T2> &operator%=(pair<T1, T2> &p, const T3 &a) {
    p.first %= a;
    p.second %= a;
    return p;
}
template <typename T1, typename T2>
pair<T1, T2> &operator++(pair<T1, T2> &p) {
    ++p.first;
    ++p.second;
    return p;
}
template <typename T1, typename T2>
pair<T1, T2> &operator--(pair<T1, T2> &p) {
    --p.first;
    --p.second;
    return p;
}
template <typename T1, typename T2>
pair<T1, T2> operator++(pair<T1, T2> &p, int) {
    pair<T1, T2> old = p;
    ++p;
    return old;
}
template <typename T1, typename T2>
pair<T1, T2> operator--(pair<T1, T2> &p, int) {
    pair<T1, T2> old = p;
    --p;
    return old;
}


//*pair同士の演算
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2> &p1, const pair<T1, T2> &p2) {
    pair<T1, T2> p = p1;
    p += p2;
    return p;
}
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2> &p1, const pair<T1, T2> &p2) {
    pair<T1, T2> p = p1;
    p -= p2;
    return p;
}
template <typename T1, typename T2>
pair<T1, T2> operator*(const pair<T1, T2> &p1, const pair<T1, T2> &p2) {
    pair<T1, T2> p = p1;
    p *= p2;
    return p;
}
template <typename T1, typename T2>
pair<T1, T2> operator/(const pair<T1, T2> &p1, const pair<T1, T2> &p2) {
    pair<T1, T2> p = p1;
    p /= p2;
    return p;
}
template <typename T1, typename T2>
pair<T1, T2> operator%(const pair<T1, T2> &p1, const pair<T1, T2> &p2) {
    pair<T1, T2> p = p1;
    p %= p2;
    return p;
}

template <typename T1, typename T2>
pair<T1, T2> &operator+=(pair<T1, T2> &p1, const pair<T1, T2> &p2) {
    p1.first += p2.first;
    p1.second += p2.second;
    return p1;
}
template <typename T1, typename T2>
pair<T1, T2> &operator-=(pair<T1, T2> &p1, const pair<T1, T2> &p2) {
    p1.first -= p2.first;
    p1.second -= p2.second;
    return p1;
}
template <typename T1, typename T2>
pair<T1, T2> &operator*=(pair<T1, T2> &p1, const pair<T1, T2> &p2) {
    p1.first *= p2.first;
    p1.second *= p2.second;
    return p1;
}
template <typename T1, typename T2>
pair<T1, T2> &operator/=(pair<T1, T2> &p1, const pair<T1, T2> &p2) {
    p1.first /= p2.first;
    p1.second /= p2.second;
    return p1;
}
template <typename T1, typename T2>
pair<T1, T2> &operator%=(pair<T1, T2> &p1, const pair<T1, T2> &p2) {
    p1.first %= p2.first;
    p1.second %= p2.second;
    return p1;
}


//*pairの操作
template<typename T>
void Pswap(pair<T, T> &p) {
    swap(p.first, p.second);
}
template<typename T>
void Pswap(vector<pair<T, T>> &v) {
    for (auto &p : v) swap(p.first, p.second);
}

//!####################################################################################################

using mint = modint998244353;


void solve () {
    lint H, W; cin >> H >> W;
    vc<string> S(H); cin >> S;
    lint U = 0, L = 0, D = H-1, R = W-1;
    rep (i, H) {
        lint c = 0;
        rep (j, W) if (S[i][j] == '.') c++;
        if (c == 0) U++;
        else break;
    }
    rep (j, W) {
        lint c = 0;
        rep (i, H) if (S[i][j] == '.') c++;
        if (c == 0) L++;
        else break;
    }
    reep (i, H) {
        lint c = 0;
        rep (j, W) if (S[i][j] == '.') c++;
        if (c == 0) D--;
        else break;
    }
    reep (j, W) {
        lint c = 0;
        rep (i, H) if (S[i][j] == '.') c++;
        if (c == 0) R--;
        else break;
    }
    lint cc = 0;
    char now = S[U][L];
    rrepp (i, L, R) if (now != S[U][i]) {cc++; now = S[U][i];}
    rrepp (i, U, D) if (now != S[i][R]) {cc++; now = S[i][R];}
    rreepp (i, L, R) if (now != S[D][i]) {cc++; now = S[D][i];}
    rreepp (i, U, D) if (now != S[i][L]) {cc++; now = S[i][L];}
    if (cc >= 4) {
        cout << -1 << endl;
        return;
    }
    lint sh = U, sw;
    rrepp (i, L, R) if (S[U][i] == '.') {sw = i; break;}
    rrepp (i, L, R) if (S[U][i] == '.') S[U][i] = '*';
    rrepp (i, U, D) if (S[i][R] == '.') S[i][R] = '*';
    rreepp (i, L, R) if (S[D][i] == '.') S[D][i] = '*';
    rreepp (i, U, D) if (S[i][L] == '.') S[i][L] = '*';
    {
        auto SS = S;
        lint h = sh, w = sw, d = 0;
        deque<pll> Q;
        while (h >= 0 && w >= 0 && h < H && w < W && SS[h][w] != '#') {
            Q.push_back({h, w});
            char now = SS[h][w];
            SS[h][w] = '#';
            lint th = h + dh[d];
            lint tw = w + dw[d];
            if (th < 0 || tw < 0 || th >= H || tw >= W || SS[th][tw] == '#' || (now == '.' && SS[th][tw] == '*')) d = (d+3) % 4;
            h += dh[d];
            w += dw[d];
            if (now == '.' && SS[h][w] == '*') break;
        }
        Q.pop_front();
        SS[sh][sw] = '.';
        h = sh, w = sw, d = 3;
        while (h >= 0 && w >= 0 && h < H && w < W && SS[h][w] != '#') {
            Q.push_front({h, w});
            SS[h][w] = '#';
            lint th = h + dh[d];
            lint tw = w + dw[d];
            if (th < 0 || tw < 0 || th >= H || tw >= W || SS[th][tw] == '#') d = (d+1) % 4;
            h += dh[d];
            w += dw[d];
        }
        lint c = 0;
        for (auto x : SS) {
            for (auto y : x) {
                if (y == '.' || y == '*') c++;
            }
        }
        if (c == 0) {
            lint h = Q[0].fi, w = Q[0].se, d;
            auto x = Q[1] - Q[0];
            if (x == mp(0L, 1L)) d = 0;
            if (x == mp(-1L, 0L)) d = 1;
            if (x == mp(0L, -1L)) d = 2;
            if (x == mp(1L, 0L)) d = 3;
            cout << h+1 << ' ' << w+1 << ' ' << "RULD"[d] << endl;
            string ans = "F";
            rep (i, sz(Q)-2) {
                auto x = Q[i+1] - Q[i];
                auto y = Q[i+2] - Q[i+1];
                if (x == y) ans += 'F';
                else ans += 'R';
            }
            cout << sz(ans) << endl;
            cout << ans << endl;
            return;
        }
    }
    {
        auto SS = S;
        lint h = sh, w = sw, d = 3;
        deque<pll> Q;
        while (h >= 0 && w >= 0 && h < H && w < W && SS[h][w] != '#') {
            Q.push_front({h, w});
            char now = SS[h][w];
            SS[h][w] = '#';
            lint th = h + dh[d];
            lint tw = w + dw[d];
            if (th < 0 || tw < 0 || th >= H || tw >= W || SS[th][tw] == '#' || (now == '.' && SS[th][tw] == '*')) d = (d+1) % 4;
            h += dh[d];
            w += dw[d];
            if (now == '.' && SS[h][w] == '*') break;
        }
        Q.pop_back();
        SS[sh][sw] = '.';
        h = sh, w = sw, d = 0;
        while (h >= 0 && w >= 0 && h < H && w < W && SS[h][w] != '#') {
            Q.push_back({h, w});
            SS[h][w] = '#';
            lint th = h + dh[d];
            lint tw = w + dw[d];
            if (th < 0 || tw < 0 || th >= H || tw >= W || SS[th][tw] == '#') d = (d+3) % 4;
            h += dh[d];
            w += dw[d];
        }
        lint c = 0;
        for (auto x : SS) {
            for (auto y : x) {
                if (y == '.' || y == '*') c++;
            }
        }
        if (c == 0) {
            lint h = Q[0].fi, w = Q[0].se, d;
            auto x = Q[1] - Q[0];
            if (x == mp(0L, 1L)) d = 0;
            if (x == mp(-1L, 0L)) d = 1;
            if (x == mp(0L, -1L)) d = 2;
            if (x == mp(1L, 0L)) d = 3;
            cout << h+1 << ' ' << w+1 << ' ' << "RULD"[d] << endl;
            string ans = "F";
            rep (i, sz(Q)-2) {
                auto x = Q[i+1] - Q[i];
                auto y = Q[i+2] - Q[i+1];
                if (x == y) ans += 'F';
                else ans += 'R';
            }
            cout << sz(ans) << endl;
            cout << ans << endl;
            return;
        }
    }
    if (cc == 2) {
        cout << -1 << endl;
        return;
    }
    vv<lint> RR(H, vc<lint>(W, W-1));
    vv<lint> LL(H, vc<lint>(W, 0));
    vv<lint> UU(H, vc<lint>(W, 0));
    vv<lint> DD(H, vc<lint>(W, H-1));
    rep (h, H) {
        reep (w, W-1) {
            if (S[h][w+1] == '#') RR[h][w] = w;
            chmin(RR[h][w], RR[h][w+1]);
        }
    }
    rep (h, H) {
        rep (w, W-1) {
            if (S[h][w] == '#') LL[h][w+1] = w+1;
            chmax(LL[h][w+1], LL[h][w]);
        }
    }
    rep (w, W) {
        rep (h, H-1) {
            if (S[h][w] == '#') UU[h+1][w] = h+1;
            chmax(UU[h+1][w], UU[h][w]);
        }
    }
    rep (w, W) {
        reep (h, H-1) {
            if (S[h+1][w] == '#') DD[h][w] = h;
            chmin(DD[h][w], DD[h+1][w]);
        }
    }
    lint CC = 0;
    for (auto x : S) {
        for (auto y : x) {
            if (y != '#') CC++;
        }
    }
    queue<tuple<pll, lint, pll, lint>> Q;
    rrep (w, L, R) {
        Q.push({{U, w+1}, 2, {U, w}, 0});
        Q.push({{D, w}, 0, {D, w+1}, 2});
    }
    rrep (h, U, D) {
        Q.push({{h, L}, 3, {h+1, L}, 1});
        Q.push({{h+1, R}, 1, {h, R}, 3});
    }
    while (sz(Q)) {
        auto [a, ad, b, bd] = Q.front();
        Q.pop();
        lint c = 0;
        rep (i, 2) {
            lint h, w, dd, u = U, d = D, l = L, r = R, ddd;
            if (i == 0) {
                h = a.fi;
                w = a.se;
                dd = ad;
                ddd = 1;
            }
            else {
                h = b.fi;
                w = b.se;
                dd = bd;
                ddd = 3;
            }
            if (dd == 0) l = w+1;
            if (dd == 1) d = h-1;
            if (dd == 2) r = w-1;
            if (dd == 3) u = h+1;
            while (true) {
                lint th = h, tw = w;
                if (dd == 0) {
                    tw = min(RR[h][w], r);
                    if (i == 0) d = h - 1;
                    if (i == 1) u = h + 1;
                }
                if (dd == 1) {
                    th = max(UU[h][w], u);
                    if (i == 0) r = w - 1;
                    if (i == 1) l = w + 1;
                }
                if (dd == 2) {
                    tw = max(LL[h][w], l);
                    if (i == 0) u = h + 1;
                    if (i == 1) d = h - 1;
                }
                if (dd == 3) {
                    th = min(DD[h][w], d);
                    if (i == 0) l = w + 1;
                    if (i == 1) r = w - 1;
                }
                lint di = abs(th - h) + abs(tw - w);
                if (di == 0) break;
                c += di;
                dd = (dd + ddd) % 4;
                h = th;
                w = tw;
            }
        }
        if (c == CC) {
            deque<pll> Q;
            rep (i, 2) {
                lint h, w, dd, u = U, d = D, l = L, r = R, ddd;
                if (i == 0) {
                    h = a.fi;
                    w = a.se;
                    dd = ad;
                    ddd = 1;
                }
                else {
                    h = b.fi;
                    w = b.se;
                    dd = bd;
                    ddd = 3;
                }
                if (dd == 0) l = w+1;
                if (dd == 1) d = h-1;
                if (dd == 2) r = w-1;
                if (dd == 3) u = h+1;
                h += dh[dd];
                w += dw[dd];
                while (u <= h && h <= d && l <= w && w <= r && S[h][w] != '#') {
                    if (i == 0) Q.push_front({h, w});
                    else Q.push_back({h, w});
                    S[h][w] = '#';
                    lint th = h + dh[dd];
                    lint tw = w + dw[dd];
                    if (th < u || th > d || tw < l || tw > r || S[th][tw] == '#') {
                        dd = (dd + ddd) % 4;
                    }
                    h += dh[dd];
                    w += dw[dd];
                }
            }
            lint h = Q[0].fi, w = Q[0].se, d;
            auto x = Q[1] - Q[0];
            if (x == mp(0L, 1L)) d = 0;
            if (x == mp(-1L, 0L)) d = 1;
            if (x == mp(0L, -1L)) d = 2;
            if (x == mp(1L, 0L)) d = 3;
            cout << h+1 << ' ' << w+1 << ' ' << "RULD"[d] << endl;
            string ans = "F";
            rep (i, sz(Q)-2) {
                auto x = Q[i+1] - Q[i];
                auto y = Q[i+2] - Q[i+1];
                if (x == y) ans += 'F';
                else ans += 'R';
            }
            cout << sz(ans) << endl;
            cout << ans << endl;
            return;
        }
    }
    cout << -1 << endl;
    return;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    RedCerr red_cerr; //VSCodeで色つけるやつ
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);
    //modint::set_mod(1000000009);
    lint T = 1;
    //cin >> T;
    re (T) solve();
    cerr << endl << Time() << endl;
}