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

#define int long long
// #define endl "\n"

#ifndef _LOCAL
#pragma GCC optimize("-O3")
// #pragma GCC target("avx2")
// #pragma GCC optimize("unroll-loops")
#endif

void solve();
typedef long long ll;
typedef __int128_t LL;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, pair<int, int>> pip;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<pair<int, int>> vp;
typedef vector<vector<int>> vvi;
typedef vector<vector<double>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<string>> vvs;
typedef vector<vector<char>> vvc;
typedef vector<vector<pair<int, int>>> vvp;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<vector<vector<vector<int>>>> vvvvi;
template <typename T>
using vec = vector<T>;
template <typename T>
using vv = vector<vector<T>>;
template <typename T>
using vvv = vector<vector<vector<T>>>;
template <typename T>
using vvvv = vector<vector<vector<vector<T>>>>;
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using mset = multiset<T>;
template <typename T>
using uset = unordered_set<T>;
template <typename T, typename U>
using umap = unordered_map<T, U>;

#define _PI 3.14159265358979323846
#define _E 2.7182818284590452354
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define bg begin()
#define ed end()
#define mt make_tuple
#define td typedef
#define elif else if
#define ifnot(x) if(!(x))
#define si(x) (int)((x).size())
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define lb(v, a) (lower_bound(begin(v), end(v), a) - begin(v))
#define ub(v, a) (upper_bound(begin(v), end(v), a) - begin(v))
#define inr(l, x, r) (l <= x && x < r)
#define cbit(x) __builtin_popcountll(x)
#define tbit(t) (t == 0 ? -1 : 63 - __builtin_clzll(t))
#define bbit(t) (t == 0 ? 64 : __builtin_ctzll(t))
#define gb(msk, i) ((msk) >> (i) & 1)
#define mask(x) ((1LL << (x)) - 1)
#define setbits(i, n) \
    for(int j_ = (n), i = bbit(j_); j_; j_ ^= 1LL << i, i = bbit(j_))

#define rep1(a)                                                  \
    for(int NEVER_USE_VARIABLE = 0; NEVER_USE_VARIABLE < (int)a; \
        NEVER_USE_VARIABLE++)
#define rep2(i, a) for(int i = 0; i < (int)a; i++)
#define rep3(i, a, b) for(int i = a; i < (int)b; i++)
#define rep4(i, a, b, c) for(int i = a; i < (int)b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll NEVER_USE_VARIABLE = n; NEVER_USE_VARIABLE--;)
#define rrep2(i, n) for(ll i = n; i--;)
#define rrep3(i, a, b) for(ll i = b; i-- > (a);)
#define rrep4(i, a, b, c) \
    for(ll i = (a) + ((b) - (a) - 1) / (c) * (c); i >= (a); i -= c)
#define rrep(...) \
    overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define reps(i, a) for(int i = 0; i < (int)a.size(); i++)
#define rreps(i, a) for(int i = (int)a.size() - 1; i >= 0; i--)
#define fore1(i, a) for(auto &&i : a)
#define fore2(x, y, a) for(auto &&[x, y] : a)
#define fore3(x, y, z, a) for(auto &&[x, y, z] : a)
#define fore(...) overload4(__VA_ARGS__, fore3, fore2, fore1)(__VA_ARGS__)
#define ryes return yes();
#define rno return no();
#define rerr return err();
istream &operator>>(istream &is, modint998244353 &a) {
    long long v;
    is >> v;
    a = v;
    return is;
}
ostream &operator<<(ostream &os, const modint998244353 &a) {
    return os << a.val();
}
istream &operator>>(istream &is, modint1000000007 &a) {
    long long v;
    is >> v;
    a = v;
    return is;
}
ostream &operator<<(ostream &os, const modint1000000007 &a) {
    return os << a.val();
}
// 十進数からb進数へ
template <class T>
string to_baseB(T x, int b = 10) {
    string ans;
    do {
        int num = x % b;
        ans = (char)((num <= 9) ? ('0' + num) : ('A' + num - 10)) + ans;
        x /= b;
    } while(x != 0);
    return ans;
}
// b進数から十進数へ
long long to_base10(const string &x, int b = 10) {
    long long ans = 0, base = 1;
    for(int i = x.length() - 1; i >= 0; --i) {
        int num =
            ('0' <= x[i] && x[i] <= '9') ? (x[i] - '0') : (x[i] - 'A' + 10);
        ans += base * num;
        base *= b;
    }
    return ans;
}

ostream &operator<<(ostream &s, const __int128_t &p) {
    s << to_baseB(p);
    return s;
}
istream &operator>>(istream &is, __int128_t &v) {
    string s;
    is >> s;
    v = 0;
    for(int i = 0; i < (int)s.size(); i++) {
        if(isdigit(s[i])) {
            v = v * 10 + s[i] - '0';
        }
    }
    if(s[0] == '-') {
        v *= -1;
    }
    return is;
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << p.first << "," << p.second;
    return os;
}
template <class T>
ostream &operator<<(ostream &s, set<T> P) {
    fore(it, P) {
        s << it << " ";
    }
    return s;
}
template <class T1, class T2>
ostream &operator<<(ostream &s, map<T1, T2> P) {
    fore(x, y, P) {
        s << "<" << x << "->" << y << "> ";
    }
    return s;
}
template <class T>
ostream &operator<<(ostream &s, multiset<T> P) {
    fore(it, P) {
        s << it << " ";
    }
    return s;
}
template <class T>
ostream &operator<<(ostream &s, unordered_set<T> P) {
    fore(it, P) {
        s << it << " ";
    }
    return s;
}
template <class T1, class T2>
ostream &operator<<(ostream &s, unordered_map<T1, T2> P) {
    fore(x, y, P) {
        s << "<" << x << "->" << y << "> ";
    }
    return s;
}
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
    for(auto &e : v) is >> e;
    return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for(auto &e : v) os << e << ' ';
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
    for(auto &e : v) {
        for(auto &c : e) os << c << ' ';
        os << endl;
    }
    return os;
}
template <class t, size_t n>
ostream &operator<<(ostream &os, const array<t, n> &a) {
    return os << vector<t>(all(a));
}

template <int i, class T>
void print_tuple(ostream &, const T &) {}
template <int i, class T, class H, class... Args>
void print_tuple(ostream &os, const T &t) {
    if(i) os << ",";
    os << get<i>(t);
    print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t) {
    print_tuple<0, tuple<Args...>, Args...>(os, t);
    return os;
}
template <class T>
ostream &operator<<(ostream &os, queue<T> q) {
    while(!q.empty()) {
        os << q.front() << ' ';
        q.pop();
    }
    return os;
}
template <class T>
ostream &operator<<(ostream &os, stack<T> q) {
    while(!q.empty()) {
        os << q.top() << ' ';
        q.pop();
    }
    return os;
}
template <class T>
ostream &operator<<(ostream &os, deque<T> q) {
    while(!q.empty()) {
        os << q.front() << ' ';
        q.pop_front();
    }
    return os;
}
template <class T>
ostream &operator<<(ostream &os, priority_queue<T> q) {
    while(!q.empty()) {
        os << q.top() << ' ';
        q.pop();
    }
    return os;
}
template <class T>
ostream &operator<<(ostream &os, priority_queue<T, vector<T>, greater<T>> q) {
    while(!q.empty()) {
        os << q.top() << ' ';
        q.pop();
    }
    return os;
}
template <class T>
vector<T> &operator++(vector<T> &v) {
    for(auto &e : v) e++;
    return v;
}
template <class T>
vector<T> operator++(vector<T> &v, signed) {
    auto res = v;
    for(auto &e : v) e++;
    return res;
}
template <class T>
vector<T> &operator--(vector<T> &v) {
    for(auto &e : v) e--;
    return v;
}
template <class T>
vector<T> operator--(vector<T> &v, signed) {
    auto res = v;
    for(auto &e : v) e--;
    return res;
}
template <class T, class U>
pair<T, U> &operator+=(pair<T, U> &a, pair<T, U> b) {
    a.first += b.first;
    a.second += b.second;
    return a;
}
template <class T, class U>
pair<T, U> &operator-=(pair<T, U> &a, pair<T, U> b) {
    a.first -= b.first;
    a.second -= b.second;
    return a;
}
template <class T, class U>
pair<T, U> operator+(pair<T, U> a, pair<T, U> b) {
    return make_pair(a.first + b.first, a.second + b.second);
}
template <class T, class U>
pair<T, U> operator-(pair<T, U> a, pair<T, U> b) {
    return make_pair(a.first - b.first, a.second - b.second);
}

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3)                                                 \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
         << x3 << endl
#define debug_4(x1, x2, x3, x4)                                             \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
         << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5)                                         \
    cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
         << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

void out() {
    cout << endl;
}
template <class T>
void out(const T &a) {
    cout << a;
    cout << endl;
}
template <class T, class... Ts>
void out(const T &a, const Ts &...b) {
    cout << a;
    (cout << ... << (cout << ' ', b));
    cout << endl;
}
void ofs_in(ostream &ofs) {
    ofs << endl;
}
template <class T>
void ofs_in(ostream &ofs, const T &a) {
    ofs << a;
    ofs << endl;
}
template <class T, class... Ts>
void ofs_in(ostream &ofs, const T &a, const Ts &...b) {
    ofs << a;
    (ofs << ... << (ofs << ' ', b));
    ofs << endl;
}
#define rout_1(x1) return out(x1)
#define rout_2(x1, x2) return out(x1, x2)
#define rout_3(x1, x2, x3) return out(x1, x2, x3)
#define rout_4(x1, x2, x3, x4) return out(x1, x2, x3, x4)
#define rout_5(x1, x2, x3, x4, x5) return out(x1, x2, x3, x4, x5)
#define rout(...)                                                    \
    CHOOSE((__VA_ARGS__, rout_5, rout_4, rout_3, rout_2, rout_1, ~)) \
    (__VA_ARGS__)
struct fast_ios {
    fast_ios() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(12);
    };
} fast_ios_;

template <class T = long long>
struct Binomial {
    int p;
    int MAX;
    vector<long long> fac, finv, inv;

    // テーブルを作る前処理
    Binomial(int p_, int n = 1) : p(p_), MAX(1), fac(2), finv(2), inv(2) {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        if(n != 1) build(n);
    }

    void build(int new_max) {
        MAX++;
        fac.resize(new_max + 1);
        inv.resize(new_max + 1);
        finv.resize(new_max + 1);
        for(; MAX <= new_max; MAX++) {
            fac[MAX] = fac[MAX - 1] * MAX % p;
            inv[MAX] = p - inv[p % MAX] * (p / MAX) % p;
            finv[MAX] = finv[MAX - 1] * inv[MAX] % p;
        }
        MAX--;
    }

    // nCk
    T mod_comb(int n, int k) {
        if(n < k) return 0;
        if(n < 0 || k < 0) return 0;
        if(n > MAX) build(n);
        return fac[n] * (finv[k] * finv[n - k] % p) % p;
    }
    T operator()(int n, int k) {
        return mod_comb(n, k);
    }

    // nPk
    T mod_perm(int n, int k) {
        if(n < k) return 0;
        if(n < 0 || k < 0) return 0;
        if(n > MAX) build(n);
        return fac[n] * finv[n - k] % p;
    }
    // n!
    T operator[](int n) {
        if(n > MAX) build(n);
        return fac[n];
    }
    // 1/n!
    T operator()(int n) {
        if(n > MAX) build(n);
        return finv[n];
    }
};

template <typename T = long long>
struct modpow {
    long long x, m;
    int n;
    vector<T> d;
    modpow(long long x) : x(x), n(1), d(1, 1) {}
    T operator[](int i) {
        while(n <= i) d.push_back(d.back() * x), ++n;
        return d[i];
    }
};
modpow two(2), ten(10);

/*
座標圧縮
https://youtu.be/fR3W5IcBGLQ?t=8550
を参考に
(T x):xが何番目か
[T i]:i番目の値
*/
template <typename T = int>
struct CC {
    bool initialized;
    vector<T> xs;
    CC() : initialized(false) {}
    CC(vector<T> v) : initialized(false) {
        for(auto x : v) xs.push_back(x);
    }
    void add(T x) {
        xs.push_back(x);
    }
    void add(vector<T> v) {
        for(auto x : v) xs.push_back(x);
    }
    void init() {
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        initialized = true;
    }
    int operator()(T x) {
        if(!initialized) init();
        return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
    }
    T operator[](int i) {
        if(!initialized) init();
        return xs[i];
    }
    int size() {
        if(!initialized) init();
        return xs.size();
    }
    friend ostream &operator<<(ostream &os, const CC &cc) {
        for(int i = 0; i < (int)cc.xs.size(); i++) {
            os << cc.xs[i] << " ";
        }
        os << endl;
        return (os);
    }
};

struct RandomNumberGenerator {
    mt19937 engine;

    RandomNumberGenerator(int seed = -1) {
        if(seed == -1)
            engine =
                mt19937(chrono::steady_clock::now().time_since_epoch().count());
        else
            engine = mt19937(seed);
    }

    long long operator()(long long a, long long b) {  // [a, b)
        uniform_int_distribution<long long> dist(a, b - 1);
        return dist(engine);
    }

    long long operator()(long long b) {  // [0, b)
        return (*this)(0, b);
    }

    long long operator()() {
        return (*this)(0, 1LL << 60);
    }

    double operator[](double a) {
        return (double)(*this)(0, 1LL << 60) / (1LL << 60) * a;
    }

    double normal_dist(double sigma, double mean = 0) {
        std::normal_distribution<> dist(mean, sigma);
        return dist(engine);
    }
} rnd;

clock_t start_time = clock();
double now_time() {
    clock_t end_time = clock();
    return (double)(end_time - start_time) / CLOCKS_PER_SEC;
}
template <class T = int, size_t n, size_t idx = 0>
auto mv(const size_t (&d)[n], const T &init) noexcept {
    if constexpr(idx < n)
        return std::vector(d[idx], mv<T, n, idx + 1>(d, init));
    else
        return init;
}
template <class T = int, size_t n>
auto mv(const size_t (&d)[n]) noexcept {
    return mv(d, T{});
}
template <class T>
void rnd_shuffle(vector<T> &v) {
    shuffle(v.begin(), v.end(), rnd.engine);
}
template <class T>
T sample(T v, int n) {
    T res;
    sample(v.begin(), v.end(), back_inserter(res), n, rnd.engine);
    return res;
}
template <class F>
long long bin_search(long long ok, long long ng, const F &f) {
    while(abs(ok - ng) > 1) {
        long long mid = (ok + ng) >> 1;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}
template <class T, class F>
T bin_search_double(T ok, T ng, const F &f, int iter = 90) {
    while(iter--) {
        T mid = (ok + ng) / 2;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}
void read_edges(vector<vector<int>> &g, int m = -1, int bidirected = true) {
    if(m == -1) m = g.size() - 1;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        if(bidirected) g[v].push_back(u);
    }
}
vector<int> counter(vector<int> &v, int mx = -1) {
    if(mx == -1) mx = *max_element(v.begin(), v.end());
    vector<int> res(mx + 1);
    for(auto x : v) res[x]++;
    return res;
}
template <class T = int, class U = vector<T>>
map<T, int> map_counter(U &v) {
    map<T, int> res;
    for(auto x : v) res[x]++;
    return res;
}
vector<int> iota(int n, int s = 0) {
    vi a(n);
    iota(a.begin(), a.end(), s);
    return a;
}
template <class T>
void sort(T &v) {
    sort(all(v));
}
template <class T>
void rsort(T &v) {
    sort(rall(v));
}
template <class T>
void reverse(T &v) {
    reverse(all(v));
}
template <class T>
auto max(const T &a) {
    return *max_element(a.begin(), a.end());
}
template <class T>
auto min(const T &a) {
    return *min_element(a.begin(), a.end());
}
template <class T>
int argmax(const T &a) {
    return max_element(a.begin(), a.end()) - a.begin();
}
template <class T>
int argmin(const T &a) {
    return min_element(a.begin(), a.end()) - a.begin();
}
long long max(signed x, long long y) {
    return max((long long)x, y);
}
long long max(long long x, signed y) {
    return max(x, (long long)y);
}
long long min(signed x, long long y) {
    return min((long long)x, y);
}
long long min(long long x, signed y) {
    return min(x, (long long)y);
}
template <class T, class S>
bool chmax(T &a, const S &b) {
    if(a < (T)b) {
        a = (T)b;
        return 1;
    }
    return 0;
}
template <class T, class S>
bool chmin(T &a, const S &b) {
    if((T)b < a) {
        a = (T)b;
        return 1;
    }
    return 0;
}
template <class T>
vector<int> argsort(vector<T> v, bool ascending_order = true) {
    vector<int> res(v.size());
    iota(res.begin(), res.end(), 0);
    if(ascending_order)
        sort(res.begin(), res.end(), [&](int i, int j) { return v[i] < v[j]; });
    else
        sort(res.begin(), res.end(), [&](int i, int j) { return v[i] > v[j]; });
    return res;
}
template <class T>
T sumv(vector<T> &v) {
    T res = 0;
    int n = v.size();
    for(int i = 0; i < n; i++) res += v[i];
    return res;
}
template <class T>
vector<T> uniq(vector<T> v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v;
}
template <class T>
vector<T> compress(vector<T> v) {
    vector<T> v2(v.size());
    v2 = v;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(int i = 0; i < (int)v2.size(); i++) {
        v2[i] = lower_bound(v.begin(), v.end(), v2[i]) - v.begin();
    }
    return v2;
}
vector<int> inverse(vector<int> &p) {
    int n = p.size();
    vector<int> inv(n);
    for(int i = 0; i < n; i++) inv[p[i]] = i;
    return inv;
}
template <typename T>
vector<pair<T, int>> idx_pair(vector<T> &a) {
    int n = a.size();
    vector<pair<T, int>> res(n);
    for(int i = 0; i < n; i++) res[i] = {a[i], i};
    return res;
}
template <typename T>
vector<T> acc0(vector<T> &v) {
    vector<T> res(v.size());
    if((int)v.size() == 0) return res;
    res[0] = v[0];
    for(int i = 1; i < (int)v.size(); i++) {
        res[i] = res[i - 1] + v[i];
    }
    return res;
}
template <typename T>
vector<T> acc1(vector<T> &v) {
    vector<T> res(v.size() + 1);
    for(int i = 0; i < (int)v.size(); i++) {
        res[i + 1] = res[i] + v[i];
    }
    return res;
}
template <typename T>
vector<vector<T>> acc0(vector<vector<T>> v) {
    int h = v.size(), w = v[0].size();
    for(int i = 0; i < h; i++) {
        for(int j = 1; j < w; j++) {
            v[i][j] += v[i][j - 1];
        }
    }
    for(int i = 1; i < h; i++) {
        for(int j = 0; j < w; j++) {
            v[i][j] += v[i - 1][j];
        }
    }
    return v;
}
template <typename T>
vector<vector<T>> acc1(vector<vector<T>> &v) {
    int h = v.size(), w = v[0].size();
    vector<vector<T>> res(h + 1, vector<T>(w + 1));
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            res[i + 1][j + 1] = v[i][j] + res[i + 1][j];
        }
    }
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            res[i + 1][j + 1] += res[i][j + 1];
        }
    }
    return res;
}
template <class T>
void erase1(multiset<T> &st, int x) {
    auto it = st.find(x);
    assert(it != st.end());
    st.erase(it);
}

long long exp(long long x, int n) {
    long long res = 1;
    while(n > 0) {
        if(n & 1) res = res * x;
        x = x * x;
        n >>= 1;
    }
    return res;
}
__int128_t absl(const __int128_t &x) {
    return x > 0 ? x : -x;
}
bool ispow2(int i) {
    return i && (i & -i) == i;
}
int countDigits(long long n) {
    string tmp = to_string(n);
    return (int)tmp.size();
}
template <class T>
T sq(T n) {
    return n * n;
}
long long ceil(long long x, long long y) {
    return (x + y - 1) / y;
}
long long floor(long long x, long long y) {
    return (y < 0 ? floor(-x, -y)
                  : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));
}
constexpr long long tri(long long n) {
    return n * (n + 1) / 2;
}
// l + ... + r
constexpr long long tri(long long l, long long r) {
    return (l + r) * (r - l + 1) / 2;
}
template <typename T>
T modulo(T n, T d) {
    return (n % d + d) % d;
}
int ctoi(const char &c, const char start = '0') {
    return c - start;
}
int atoi(const char &c, const char start = 'a') {
    return c - start;
}
vector<int> ctoi(string &s, const char start = '0') {
    vector<int> res;
    for(auto &c : s) {
        int x = c - start;
        if(x < 0 || x >= 10) x = -1;
        res.push_back(x);
    }
    return res;
}
vector<int> atoi(string &s, const char start = 'a') {
    vector<int> res;
    for(auto &c : s) {
        int x = c - start;
        if(x < 0 || x >= 26) x = -1;
        res.push_back(x);
    }
    return res;
}
vector<vector<int>> ctoi(vector<string> &s, const char start = '0') {
    int n = s.size();
    vector<vector<int>> res(n);
    for(int i = 0; i < n; i++) res[i] = ctoi(s[i], start);
    return res;
}
vector<vector<int>> atoi(vector<string> &s, const char start = 'a') {
    int n = s.size();
    vector<vector<int>> res(n);
    for(int i = 0; i < n; i++) res[i] = atoi(s[i], start);
    return res;
}
string itoc(vector<int> &v, const char start = '0') {
    int n = v.size();
    string res;
    for(int i = 0; i < n; i++) {
        res.push_back(start + v[i]);
    }
    return res;
}
string itoa(vector<int> &v, const char start = 'a') {
    return itoc(v, start);
}
vector<string> itoc(vector<vector<int>> &v, const char start = '0') {
    int n = v.size();
    vector<string> res(n);
    for(int i = 0; i < n; i++) {
        int m = v[i].size();
        for(int j = 0; j < m; j++) {
            res[i] = itoc(v[i], start);
        }
    }
    return res;
}
vector<string> itoa(vector<vector<int>> &v, const char start = 'a') {
    return itoc(v, start);
}
template <class T>
int mex(T &a) {
    int n = a.size();
    vector<int> cnt(n + 1);
    for(auto x : a) {
        if(x > n) continue;
        cnt[x]++;
    }
    int res = 0;
    while(cnt[res]) res++;
    return res;
}
void yes() {
    cout << "Yes" << endl;
    // cout << "Alice" << endl;
    // cout << "Takahashi" << endl;
}
void no() {
    cout << "No" << endl;
    // cout << "Bob" << endl;
    // cout << "Aoki" << endl;
}
void yesno(bool x) {
    if(x)
        yes();
    else
        no();
}
void err() {
    cout << -1 << endl;
}

int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};

long long inf = (1 << 30) + (1LL << 60) - 2;
double eps = 1e-9;

// long long mod = 67280421310721;
// using mint = static_modint<1000000009>;
// using mint = dynamic_modint<1000000009>;
// long long mod = 1000000007;
// using mint = modint1000000007;
long long mod = 998244353;
using mint = modint998244353;
typedef vector<mint> vm;
typedef vector<vector<mint>> vvm;
typedef vector<vector<vector<mint>>> vvvm;
// Binomial<mint> C(mod);
// modpow<mint> mtwo(2), mten(10);
////////////////////////////////////////////////////////////////////////////////////////////
/*
https:opt-cp.com/fps-implementation/
https:judge.yosupo.jp/submission/42413
を参考に

以下、d:サイズdにresizeする
+,-,*,/,>>,<<
inv(d):逆数
multiply(g,d):gをconvolution
divide(g,d):gで割る
eval(a):f(a)
log(d):log(f)
exp(d):exp(f)
pow(k,d):f^k

MOD = 998244353（NTT-friendry）の時はfastが使える。
MOD =1000000007などの他の時は使えないので、
define fastをコメントアウトして、その下のnaiveを使う。
（*fpsや/fpsに関わる部分。）
*/

#define fast

#define rep_(i, a_, b_, a, b, ...) \
    for(int i = (a), lim##i = (b); i < lim##i; ++i)
#define rep2_(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define drep_(i, a_, b_, a, b, ...) \
    for(int i = (a) - 1, lim##i = (b); i >= lim##i; --i)
#define drep(i, ...) drep_(i, __VA_ARGS__, __VA_ARGS__, __VA_ARGS__, 0)

template <typename T>
struct Factorial {
    int MAX;
    vector<T> fac, finv;
    Factorial(int m = 0) : MAX(m), fac(m + 1, 1), finv(m + 1, 1) {
        rep2_(i, 2, MAX + 1) fac[i] = fac[i - 1] * i;
        finv[MAX] /= fac[MAX];
        drep(i, MAX + 1, 3) finv[i - 1] = finv[i] * i;
    }
    T binom(int n, int k) {
        if(k < 0 || n < k) return 0;
        return fac[n] * finv[k] * finv[n - k];
    }
    T perm(int n, int k) {
        if(k < 0 || n < k) return 0;
        return fac[n] * finv[n - k];
    }
};
Factorial<mint> fc;

template <class T>
struct FormalPowerSeries : vector<T> {
    using vector<T>::vector;
    using vector<T>::operator=;
    using F = FormalPowerSeries;

    F operator-() const {
        F res(*this);
        for(auto &e : res) e = -e;
        return res;
    }
    F &operator*=(const T &g) {
        for(auto &e : *this) e *= g;
        return *this;
    }
    F &operator/=(const T &g) {
        assert(g != T(0));
        *this *= g.inv();
        return *this;
    }
    F &operator+=(const F &g) {
        int n = this->size(), m = g.size();
        rep2_(i, min(n, m))(*this)[i] += g[i];
        return *this;
    }
    F &operator-=(const F &g) {
        int n = this->size(), m = g.size();
        rep2_(i, min(n, m))(*this)[i] -= g[i];
        return *this;
    }
    F &operator<<=(const int d) {
        int n = this->size();
        if(d >= n) *this = F(n);
        this->insert(this->begin(), d, 0);
        this->resize(n);
        return *this;
    }
    F &operator>>=(const int d) {
        int n = this->size();
        this->erase(this->begin(), this->begin() + min(n, d));
        this->resize(n);
        return *this;
    }

    // O(n log n)
    F inv(int d = -1) const {
        int n = this->size();
        assert(n != 0 && (*this)[0] != 0);
        if(d == -1) d = n;
        assert(d >= 0);
        F res{(*this)[0].inv()};
        for(int m = 1; m < d; m *= 2) {
            F f(this->begin(), this->begin() + min(n, 2 * m));
            F g(res);
            f.resize(2 * m), internal::butterfly(f);
            g.resize(2 * m), internal::butterfly(g);
            rep2_(i, 2 * m) f[i] *= g[i];
            internal::butterfly_inv(f);
            f.erase(f.begin(), f.begin() + m);
            f.resize(2 * m), internal::butterfly(f);
            rep2_(i, 2 * m) f[i] *= g[i];
            internal::butterfly_inv(f);
            T iz = T(2 * m).inv();
            iz *= -iz;
            rep2_(i, m) f[i] *= iz;
            res.insert(res.end(), f.begin(), f.begin() + m);
        }
        res.resize(d);
        return res;
    }

#ifdef fast
    // fast: FMT-friendly modulus only
    // O(n log n)
    F &multiply_inplace(const F &g, int d = -1) {
        int n = this->size();
        if(d == -1) d = n;
        assert(d >= 0);
        *this = convolution(move(*this), g);
        this->resize(d);
        return *this;
    }
    F multiply(const F &g, const int d = -1) const {
        return F(*this).multiply_inplace(g, d);
    }
    F &operator*=(const F &g) {
        int n = this->size();
        *this = convolution(move(*this), g);
        this->resize(n);
        return *this;
    }
    // O(n log n)
    F &divide_inplace(const F &g, int d = -1) {
        int n = this->size();
        if(d == -1) d = n;
        assert(d >= 0);
        *this = convolution(move(*this), g.inv(d));
        this->resize(d);
        return *this;
    }
    F divide(const F &g, const int d = -1) const {
        return F(*this).divide_inplace(g, d);
    }
    F &operator/=(const F &g) {
        int n = (*this).size();
        *this = convolution(*this, g.inv(n));
        (*this).resize(n);
        return *this;
    }
#else
    // naive
    // // O(n^2)
    F &multiply_inplace(const F &g) {
        int n = this->size(), m = g.size();
        drep(i, n) {
            (*this)[i] *= g[0];
            rep2_(j, 1, min(i + 1, m))(*this)[i] += (*this)[i - j] * g[j];
        }
        return *this;
    }
    F multiply(const F &g) const {
        return F(*this).multiply_inplace(g);
    }
    // O(n^2)
    F &divide_inplace(const F &g) {
        assert(g[0] != T(0));
        T ig0 = g[0].inv();
        int n = this->size(), m = g.size();
        rep(i, n) {
            rep2_(j, 1, min(i + 1, m))(*this)[i] -= (*this)[i - j] * g[j];
            (*this)[i] *= ig0;
        }
        return *this;
    }
    F divide(const F &g) const {
        return F(*this).divide_inplace(g);
    }
    F &operator*=(const F &g) {
        int n = (*this).size(), m = g.size();
        drep(i, n) {
            (*this)[i] *= g[0];
            rep2_(j, 1, min(i + 1, m))(*this)[i] += (*this)[i - j] * g[j];
        }
        return *this;
    }
    F &operator/=(const F &g) {
        assert(g[0] != T(0));
        T ig0 = g[0].inv();
        int n = (*this).size(), m = g.size();
        rep(i, n) {
            rep2_(j, 1, min(i + 1, m))(*this)[i] -= (*this)[i - j] * g[j];
            (*this)[i] *= ig0;
        }
        return *this;
    }
#endif

    // sparse
    // O(nk)
    F &multiply_inplace(vector<pair<int, T>> g) {
        int n = this->size();
        auto [d, c] = g.front();
        if(d == 0)
            g.erase(g.begin());
        else
            c = 0;
        drep(i, n) {
            (*this)[i] *= c;
            for(auto &[j, b] : g) {
                if(j > i) break;
                (*this)[i] += (*this)[i - j] * b;
            }
        }
        return *this;
    }
    F multiply(const vector<pair<int, T>> &g) const {
        return F(*this).multiply_inplace(g);
    }
    F &operator*=(vector<pair<int, T>> g) {
        int n = (*this).size();
        auto [d, c] = g.front();
        if(d == 0)
            g.erase(g.begin());
        else
            c = 0;
        drep(i, n) {
            (*this)[i] *= c;
            for(auto &[j, b] : g) {
                if(j > i) break;
                (*this)[i] += (*this)[i - j] * b;
            }
        }
        return *this;
    }

    // O(nk)
    F &divide_inplace(vector<pair<int, T>> g) {
        int n = this->size();
        auto [d, c] = g.front();
        assert(d == 0 && c != T(0));
        T ic = c.inv();
        g.erase(g.begin());
        rep2_(i, n) {
            for(auto &[j, b] : g) {
                if(j > i) break;
                (*this)[i] -= (*this)[i - j] * b;
            }
            (*this)[i] *= ic;
        }
        return *this;
    }
    F divide(const vector<pair<int, T>> &g) const {
        return F(*this).divide_inplace(g);
    }
    F &operator/=(vector<pair<int, T>> g) {
        int n = (*this).size();
        auto [d, c] = g.front();
        assert(d == 0 && c != T(0));
        T ic = c.inv();
        g.erase(g.begin());
        rep2_(i, n) {
            for(auto &[j, b] : g) {
                if(j > i) break;
                (*this)[i] -= (*this)[i - j] * b;
            }
            (*this)[i] *= ic;
        }
        return *this;
    }

    // multiply and divide (1 + cz^d)
    // O(n)
    void multiply_inplace(const int d, const T c) {
        int n = this->size();
        if(c == T(1))
            drep(i, n - d)(*this)[i + d] += (*this)[i];
        else if(c == T(-1))
            drep(i, n - d)(*this)[i + d] -= (*this)[i];
        else
            drep(i, n - d)(*this)[i + d] += (*this)[i] * c;
    }
    // O(n)
    void divide_inplace(const int d, const T c) {
        int n = this->size();
        if(c == T(1))
            rep2_(i, n - d)(*this)[i + d] -= (*this)[i];
        else if(c == T(-1))
            rep2_(i, n - d)(*this)[i + d] += (*this)[i];
        else
            rep2_(i, n - d)(*this)[i + d] -= (*this)[i] * c;
    }

    // O(n)
    T eval(const T &a) const {
        T x(1), res(0);
        for(auto e : *this) res += e * x, x *= a;
        return res;
    }

    // O(n)
    F &integral_inplace() {
        int n = this->size();
        assert(n > 0);
        if(n == 1) return *this = F{0};
        this->insert(this->begin(), 0);
        this->pop_back();
        vector<T> inv(n);
        inv[1] = 1;
        int p = T::mod();
        rep2_(i, 2, n) inv[i] = -inv[p % i] * (p / i);
        rep2_(i, 2, n)(*this)[i] *= inv[i];
        return *this;
    }
    F integral() const {
        return F(*this).integral_inplace();
    }

    // O(n)
    F &derivative_inplace() {
        int n = this->size();
        assert(n > 0);
        rep2_(i, 2, n)(*this)[i] *= i;
        this->erase(this->begin());
        this->push_back(0);
        return *this;
    }
    F derivative() const {
        return F(*this).derivative_inplace();
    }

    // O(n log n)
    F &log_inplace(int d = -1) {
        int n = this->size();
        assert(n > 0 && (*this)[0] == 1);
        if(d == -1) d = n;
        assert(d >= 0);
        if(d < n) this->resize(d);
        F f_inv = this->inv();
        this->derivative_inplace();
        this->multiply_inplace(f_inv);
        this->integral_inplace();
        return *this;
    }
    F log(const int d = -1) const {
        return F(*this).log_inplace(d);
    }

    // O(n log n)
    // https://arxiv.org/abs/1301.5804 (Figure 1, right)
    F &exp_inplace(int d = -1) {
        int n = this->size();
        assert(n > 0 && (*this)[0] == 0);
        if(d == -1) d = n;
        assert(d >= 0);
        F g{1}, g_fft{1, 1};
        (*this)[0] = 1;
        this->resize(d);
        F h_drv(this->derivative());
        for(int m = 2; m < d; m *= 2) {
            // prepare
            F f_fft(this->begin(), this->begin() + m);
            f_fft.resize(2 * m), internal::butterfly(f_fft);

            // Step 2.a'
            {
                F _g(m);
                rep2_(i, m) _g[i] = f_fft[i] * g_fft[i];
                internal::butterfly_inv(_g);
                _g.erase(_g.begin(), _g.begin() + m / 2);
                _g.resize(m), internal::butterfly(_g);
                rep2_(i, m) _g[i] *= g_fft[i];
                internal::butterfly_inv(_g);
                _g.resize(m / 2);
                _g /= T(-m) * m;
                g.insert(g.end(), _g.begin(), _g.begin() + m / 2);
            }

            // Step 2.b'--d'
            F t(this->begin(), this->begin() + m);
            t.derivative_inplace();
            {
                // Step 2.b'
                F r{h_drv.begin(), h_drv.begin() + m - 1};
                // Step 2.c'
                r.resize(m);
                internal::butterfly(r);
                rep2_(i, m) r[i] *= f_fft[i];
                internal::butterfly_inv(r);
                r /= -m;
                // Step 2.d'
                t += r;
                t.insert(t.begin(), t.back());
                t.pop_back();
            }

            // Step 2.e'
            if(2 * m < d) {
                t.resize(2 * m);
                internal::butterfly(t);
                g_fft = g;
                g_fft.resize(2 * m);
                internal::butterfly(g_fft);
                rep2_(i, 2 * m) t[i] *= g_fft[i];
                internal::butterfly_inv(t);
                t.resize(m);
                t /= 2 * m;
            } else {  // この場合分けをしても数パーセントしか速くならない
                F g1(g.begin() + m / 2, g.end());
                F s1(t.begin() + m / 2, t.end());
                t.resize(m / 2);
                g1.resize(m), internal::butterfly(g1);
                t.resize(m), internal::butterfly(t);
                s1.resize(m), internal::butterfly(s1);
                rep2_(i, m) s1[i] = g_fft[i] * s1[i] + g1[i] * t[i];
                rep2_(i, m) t[i] *= g_fft[i];
                internal::butterfly_inv(t);
                internal::butterfly_inv(s1);
                rep2_(i, m / 2) t[i + m / 2] += s1[i];
                t /= m;
            }

            // Step 2.f'
            F v(this->begin() + m, this->begin() + min<int>(d, 2 * m));
            v.resize(m);
            t.insert(t.begin(), m - 1, 0);
            t.push_back(0);
            t.integral_inplace();
            rep2_(i, m) v[i] -= t[m + i];

            // Step 2.g'
            v.resize(2 * m);
            internal::butterfly(v);
            rep2_(i, 2 * m) v[i] *= f_fft[i];
            internal::butterfly_inv(v);
            v.resize(m);
            v /= 2 * m;

            // Step 2.h'
            rep2_(i, min(d - m, m))(*this)[m + i] = v[i];
        }
        return *this;
    }
    F exp(const int d = -1) const {
        return F(*this).exp_inplace(d);
    }

    // O(n log n)
    F &pow_inplace(const ll k, int d = -1) {
        int n = this->size();
        if(d == -1) d = n;
        assert(d >= 0 && k >= 0);
        if(d == 0) return *this = F(0);
        if(k == 0) {
            *this = F(d);
            (*this)[0] = 1;
            return *this;
        }
        int l = 0;
        while(l < n && (*this)[l] == 0) ++l;
        if(l == n || l > (d - 1) / k) return *this = F(d);
        T c{(*this)[l]};
        this->erase(this->begin(), this->begin() + l);
        *this /= c;
        this->log_inplace(d - l * k);
        *this *= k;
        this->exp_inplace();
        *this *= c.pow(k);
        this->insert(this->begin(), l * k, 0);
        return *this;
    }
    F pow(const ll k, const int d = -1) const {
        return F(*this).pow_inplace(k, d);
    }

    // O(n log n)
    F &shift_inplace(const T c) {
        int n = this->size();
        fc = Factorial<T>(n);
        rep2_(i, n)(*this)[i] *= fc.fac[i];
        reverse(this->begin(), this->end());
        F g(n);
        T cp = 1;
        rep2_(i, n) g[i] = cp * fc.finv[i], cp *= c;
        this->multiply_inplace(g, n);
        reverse(this->begin(), this->end());
        rep2_(i, n)(*this)[i] *= fc.finv[i];
        return *this;
    }
    F shift(const T c) const {
        return F(*this).shift_inplace(c);
    }

    F operator*(const T &g) const {
        return F(*this) *= g;
    }
    F operator/(const T &g) const {
        return F(*this) /= g;
    }
    F operator+(const F &g) const {
        return F(*this) += g;
    }
    F operator-(const F &g) const {
        return F(*this) -= g;
    }
    F operator<<(const int d) const {
        return F(*this) <<= d;
    }
    F operator>>(const int d) const {
        return F(*this) >>= d;
    }
    F operator*(const F &g) const {
        return F(*this) *= g;
    }
    F operator/(const F &g) const {
        return F(*this) /= g;
    }
    F operator*(vector<pair<int, T>> g) const {
        return F(*this) *= g;
    }
    F operator/(vector<pair<int, T>> g) const {
        return F(*this) /= g;
    }
};

using fps = FormalPowerSeries<mint>;
using sfps = vector<pair<int, mint>>;
////////////////////////////////////////////////////////////////////////////////////////////

signed main() {
    int testcase = 1;
    // cin >> testcase;
    for(int i = 0; i < testcase; i++) {
        solve();
    }

    debug(now_time());
}

void solve() {
    int n, k;
    cin >> n >> k;

    fps f(n + 1);

    rep(i, 1, n + 1) {
        rep(k, 1, n + 1) {
            if(k * i > n) break;
            f[k * i] -= mint{1} / k;
        }
    }

    f = f.exp(n + 1);
    debug(f);
    fps g(n + 1);

    rep(i, n) {
        if(i * (k + 1) > n) break;
        g[i * (k + 1)] = f[i];
    }

    f = g / f;

    vm ans(n);
    rep(i, 1, n + 1) ans[i - 1] = f[i];

    out(ans);
}