#pragma warning(disable:4996)
#include <bits/stdc++.h> 
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
using mint = static_modint<998244353>;
using vmint = vector<mint>;
using vvmint = vector<vmint>;
using vvvmint = vector<vvmint>;
using vvvvmint = vector<vvvmint>;
istream& operator>>(istream& is, mint& a) {
	long long v;
	is >> v;
	a = v;
	return is;
}
ostream& operator<<(ostream& os, mint a) {
	return os << a.val();
}
#endif
#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
#endif
template<typename T>
using vec = vector<T>;
using ll = long long;
using ull = unsigned long long;
using stirng = string;
using itn = int;
using vs = vec<string>;
using vc = vec<char>;
using vvc = vec<vc>;
using vvvc = vec<vvc>;
using vi = vec<int>;
using vvi = vec<vi>;
using vvvi = vec<vvi>;
using vvvvi = vec<vvvi>;
using vll = vec<ll>;
using vvll = vec<vll>;
using vvvll = vec<vvll>;
using vvvvll = vec<vvvll>;
using si = set<int>;
using vsi = vec<si>;
using vvsi = vec<vsi>;
using vvvsi = vec<vvsi>;
using sll = set<ll>;
using vsll = vec<sll>;
using vvsll = vec<vsll>;
using vvvsll = vec<vvsll>;
using vd = vec<double>;
using vvd = vec<vd>;
using vvvd = vec<vvd>;
using vvvvd = vec<vvvd>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pd = pair<double, double>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using msi = multiset<int>;
using msll = multiset<ll>;
using vpii = vec<pii>;
using vvpii = vec<vpii>;
using vvvpii = vec<vvpii>;
using vpll = vec<pll>;
using vvpll = vec<vpll>;
using vvvpll = vec<vvpll>;
using vpd = vec<pd>;
using spii = set<pii>;
using spll = set<pll>;
using spd = set<pd>;
using vspll = vec<spll>;
using vvspll = vec<vspll>;
using vb = vec<bool>;
using vvb = vec<vb>;
using vvvb = vec<vvb>;
#define rep(i,j,n) for(ll i=j;i<(n);i++)
#define rrep(i,j,n) for (ll i = (n)-1; i >=j; i--)
#define Call_4th(_1, _2, _3, _4, ...) _4
#define rp(...) Call_4th(__VA_ARGS__, _1, rp2)(__VA_ARGS__)
#define rp2(i, n) rep(i, 0, n)
#define rrp(i,n) rrep(i,0,(n))
#define all(v) v.begin(), v.end()
#define pb push_back
#define pp pop_back()
#define bk back()
#define ins insert
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl; 
#define NL {cout<<endl;}
#define n0 {cout<<"-1"<<endl;}
#define lwb lower_bound
#define upb upper_bound
#define reutrn return
#define Endl endl
template<typename T>
int len(T& x) { return int(x.size()); }
#define sz size()
#define fi first
#define se second
#define nxp next_permutation
ll mod0 = 998244353, lmax = 4e18, inf = 1050000000;
double pi = 3.141592653589793238462643;

//cin系統
template<typename... T>
void in(T&... X) { (cin >> ... >> X); }
template<typename T>
void ain(vec<T>& Y) { rp(K, Y.size()) cin >> Y[K]; }
template<typename T>
void ain(set<T>& Y, auto n) {
	rp(i, n) {
		T YY; cin >> YY;
		Y.insert(YY);
	}
}
template<typename T>
void ain(multiset<T>& Y, auto n) {
	rp(i, n) {
		T YY; cin >> YY;
		Y.insert(YY);
	}
}
template<typename T>
void ain(pair<T, T>& a) { cin >> a.fi >> a.se; }
template<typename T>
void bin(vec<T>& Z) { rp(L, Z.size()) ain(Z[L]); }

//cout系統
// vector
template <typename T> struct is_vector : false_type {};
template <typename T, typename Alloc>
struct is_vector<vector<T, Alloc>> : true_type {};
// queue
template <typename T> struct is_queue : false_type {};
template <typename T, typename Container>
struct is_queue<queue<T, Container>> : true_type {};
// stack
template <typename T> struct is_stack : false_type {};
template <typename T, typename Container>
struct is_stack<stack<T, Container>> : true_type {};
// pair
template <typename T> struct is_pair : false_type {};
template <typename T1, typename T2>
struct is_pair<pair<T1, T2>> : true_type {};
// set / multiset
template <typename T> struct is_set_like : false_type {};
template <typename Key, typename Compare, typename Alloc>
struct is_set_like<set<Key, Compare, Alloc>> : true_type {};
template <typename Key, typename Compare, typename Alloc>
struct is_set_like<multiset<Key, Compare, Alloc>> : true_type {};
// map / multimap
template <typename T> struct is_map_like : false_type {};
template <typename Key, typename Val, typename Compare, typename Alloc>
struct is_map_like<map<Key, Val, Compare, Alloc>> : true_type {};
template <typename Key, typename Val, typename Compare, typename Alloc>
struct is_map_like<multimap<Key, Val, Compare, Alloc>> : true_type {};

template <typename T>
void aout(const T& x) {
	if constexpr (is_vector<T>::value) {
		for (const auto& e : x) aout(e);
		cout << endl;
	}
	else if constexpr (is_queue<T>::value) {
		auto copy = x;
		while (!copy.empty()) {
			aout(copy.front());
			copy.pop();
		}
		cout << endl;
	}
	else if constexpr (is_stack<T>::value) {
		auto copy = x;
		while (!copy.empty()) {
			aout(copy.top());
			copy.pop();
		}
		cout << endl;
	}
	else if constexpr (is_pair<T>::value) {
		aout(x.first);
		aout(x.second);
		cout << endl;
	}
	else if constexpr (is_set_like<T>::value) {
		for (const auto& e : x) aout(e);
		cout << endl;
	}
	else if constexpr (is_map_like<T>::value) {
		for (const auto& e : x) aout(e); // pair<const Key, Val>
		cout << endl;
	}
	else {
		cout << x << " ";
	}
}

//数学系
ll modcnt(ll l, ll r, ll m, ll a) {//l以上r以下の整数iでi≡a(mod m)となるものの個数(l>r,a<0等も可)
	assert(m != 0);
	m = abs(m);
	ll x = l + ((a - l) % m + m) % m;//l以上で最小のi≡a(mod m)となるi
	if (x > r) return 0;
	return (r - x) / m + 1;
}
ll dsum(ll a) {//桁和
	ll r = 0;
	while (a != 0) {
		r += a % 10;
		a /= 10;
	}
	return r;
}
ll dnum(ll a) {//桁数(0は0桁)
	ll r = 0;
	while (a != 0) {
		r++;
		a /= 10;
	}
	return r;
}
sll yk(ll n) {//約数全列挙O(sqrt(N)),set<int>
	sll yaku;
	for (ll i = 1; i * i <= n; i++) if (n % i == 0) {
		yaku.insert(i);
		yaku.insert(n / i);
	}
	return yaku;
}
vi ssa(int n) {//n:必要な素数の最大値 素数全列挙 線形篩
	vector<int> prime;
	vector<int>lpf(n + 1, 0);//最小素因数
	rep(i, 2, n + 1) {
		if (lpf[i] == 0) {
			lpf[i] = i;
			prime.push_back(i);
		}
		for (int k : prime) {
			if (k * i > n || k > lpf[i]) break;//k最小素因数よりk<=i
			lpf[k * i] = k;//kを最小素因数に持つ数k*iを拾う
		}
	}
	return prime;
}
vector<pll> sib(ll x) {//素因数分解
	if (x == 1) return vector<pll>(1, { 1,1 });
	vector<pll> ans;
	for (ll i = 2; i * i <= x; i++) {//rootx回iを回しxで割る
		ll kaisu = 0;
		while (x % i == 0) {
			x /= i; kaisu++;
		}
		if (kaisu > 0) ans.pb({ i,kaisu });
	}
	if (x != 1) ans.pb({ x,1 });
	return ans;
}
bool isp(ll x) {//素数判定 O(sqrt(x))
	auto y = sib(x);
	return (x != 1 && y.sz == 1 && y[0] == pll{ x, 1 });
}
vec<vec<pll>> sib(ll x, ll y) {//閉区間[x,y]全素因数分解 x=1は何も返さない O(max(sqrt(y),y-x)loglogy) ABC227G ABC412E
	vi b = ssa(sqrt(y) + 100);
	vec<vec<pll>> r(y - x + 1);
	vll num(y - x + 1);
	rp(i, y - x + 1) num[i] = x + i;
	for (ll k : b) for (ll a = (1 + (x - 1) / k) * k; a <= y; a += k) {
		ll kaisu = 0;
		while (num[a - x] % k == 0) {
			num[a - x] /= k; kaisu++;
		}
		if (kaisu) r[a - x].pb({ k,kaisu });
	}
	rp(i, y - x + 1) if (num[i] != 1) r[i].pb({ num[i],1 });
	return r;
}
template<typename T>
ll sqrtll(T a) {//整数sqrt a<0orr非整数の場合-1を返す
	if (a < 0) return -1;
	ll r = sqrt(a);
	while (r * r > a) r--;
	while ((r + 1) * (r + 1) <= a) r++;
	if (r * r == a)return r;
	else return -1;
}
#define llsqrt sqrtll
ll powll(ll a, ll b) {//llでpow
	ll c = 1;
	assert(pow(a, b) <= 9e18);
	rp(i, b) {
		c *= a;
	}
	return c;
}
#define llpow powll
template<typename T>
T sq(T a) {//2乗
	return a * a;
}
template<typename T>
T cb(T a) {//3乗
	return a * a * a;
}
string basea(ll x, ll a) {//xをa進法に変換
	string r;
	while (x != 0) {
		r.pb(x % a + '0');
		x /= a;
	}
	reverse(all(r));
	return r;
}
ll base10(string x, ll a) {//a進数のxを10進法に戻す
	ll r = 0;
	rp(i, x.sz) {
		r *= a;
		r += x[i] - '0';
	}
	return r;
}
vll vbasea(ll x, ll a) {//xをa進法に変換(vector)
	vll r;
	while (x != 0) {
		r.pb(x % a);
		x /= a;
	}
	reverse(all(r));
	return r;
}
template<typename T>
ll bc(T x) {//bitcount
	assert(x >= 0);
	return __builtin_popcount(x);
}
double ds(double x1, double x2, double y1, double y2) {//dist
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
ll ds2(ll x1, ll x2, ll y1, ll y2) {//distの2乗(整数値)
	return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
template<typename T>
ll ds2(vec<T> a) {
	return (a[0] - a[2]) * (a[0] - a[2]) + (a[1] - a[3]) * (a[1] - a[3]);
}
ll gpsum(ll a, ll r, ll n, ll m) {//初項a,公比r,項数nの等比数列の総和mod m r=10でレピュニットも可能
	if (n == 0) return 0;
	if (n == 1) return a % m;
	modint::set_mod(m);
	if (n % 2 == 1) return (a + gpsum(a * r % m, r, n - 1, m)) % m;
	else return ((modint(r).pow(n / 2) + 1) * gpsum(a, r, n / 2, m)).val();
}

//二分探索
template<typename T>
auto lwa(typename std::vector<T>::iterator b, typename std::vector<T>::iterator e, T c) {//[b,e)でcより小さい最大の値のイテレータ(複数あれば右端)
	auto it = std::lower_bound(b, e, c);
	if (it == b) return e;
	--it;
	return it;
}
template<typename T>
auto lwa(vector<T>& a, T b) {//aでbより小さい最大の値のイテレータ(複数あれば右端)
	return lwa(all(a), b);
}
template<typename T>
auto lwa(set<T>& a, T b) {//aでbより小さい最大の値のイテレータ(複数あれば右端)
	auto i = a.lwb(b);
	if (i == a.begin()) return a.end();
	else i--;
	return i;
}
template<typename T>
auto lwa(multiset<T>& a, T b) {//aでbより小さい最大の値のイテレータ(複数あれば右端)
	auto i = a.lwb(b);
	if (i == a.begin()) return a.end();
	else i--;
	return i;
}

template<typename T>
auto lwc(typename std::vector<T>::iterator b, typename std::vector<T>::iterator e, T c) {//aでb以下の最大の値のイテレータ(複数あれば左端)
	auto i = lwb(b, e, c);
	if (i != e && *i == c) return i;
	if (i == b) return e;
	else i--;
	return i;
}
template<typename T>
auto lwc(vector<T>& a, T b) {//aでb以下の最大の値のイテレータ(複数あれば左端)
	return lwc(all(a), b);
}
template<typename T>
auto lwc(set<T>& a, T b) {//aでb以下の最大の値のイテレータ(複数あれば左端)
	auto i = a.lwb(b);
	if (i != a.end() && *i == b) return i;
	if (i == a.begin()) return a.end();
	else i--;
	return i;
}
template<typename T>
auto lwc(multiset<T>& a, T b) {//aでb以下の最大の値のイテレータ(複数あれば左端)
	auto i = a.lwb(b);
	if (i != a.end() && *i == b) return i;
	if (i == a.begin()) return a.end();
	else i--;
	return i;
}

template <typename T>
std::pair<typename vector<T>::iterator, typename vector<T>::iterator> its(vec<T>& v, T a) {//{--lwb,lwb}({x未満の右端,x以上の左端})のpair返す(なければend())
	auto it = lwb(all(v), a);
	if (it == v.begin()) return { v.end(), it };
	auto it2 = it; it2--;
	return { it2,it };
}
template <typename T>
std::pair<typename set<T>::iterator, typename set<T>::iterator> its(set<T>& v, T a) {//{--lwb,lwb}({x未満の右端,x以上の左端})のpair返す(なければend())
	auto it = v.lwb(a);
	if (it == v.begin()) return { v.end(), it };
	auto it2 = it; it2--;
	return { it2,it };
}
template <typename T>
std::pair<typename multiset<T>::iterator, typename multiset<T>::iterator> its(multiset<T>& v, T a) {//{--lwb,lwb}({x未満の右端,x以上の左端})のpair返す(なければend())
	auto it = v.lwb(a);
	if (it == v.begin()) return { v.end(), it };
	auto it2 = it; it2--;
	return { it2,it };
}

template <typename T>
typename vector<T>::iterator nits(vec<T>& v, T a, bool isr = 1) {//itsのうちaに近い方返す(距離同じの場合isr==0なら左優先,1なら右優先) v.sz==0のときv.end()返す
	auto cd = its(v, a);
	if (cd.fi == v.end()) return cd.se;
	if (cd.se == v.end()) return cd.fi;
	auto l = a - *cd.fi, r = *cd.se - a;
	if (l < r) return cd.fi;
	if (l > r || isr == 1) return cd.se;
	return cd.fi;
}
template <typename T>
typename set<T>::iterator nits(set<T>& v, T a, bool isr = 1) {//itsのうちaに近い方返す(距離同じの場合isr==0なら左優先,1なら右優先) v.sz==0のときv.end()返す
	auto cd = its(v, a);
	if (cd.fi == v.end()) return cd.se;
	if (cd.se == v.end()) return cd.fi;
	auto l = a - *cd.fi, r = *cd.se - a;
	if (l < r) return cd.fi;
	if (l > r || isr == 1) return cd.se;
	return cd.fi;
}
template <typename T>
typename multiset<T>::iterator nits(multiset<T>& v, T a, bool isr = 1) {//itsのうちaに近い方返す(距離同じの場合isr==0なら左優先,1なら右優先) v.sz==0のときv.end()返す
	auto cd = its(v, a);
	if (cd.fi == v.end()) return cd.se;
	if (cd.se == v.end()) return cd.fi;
	auto l = a - *cd.fi, r = *cd.se - a;
	if (l < r) return cd.fi;
	if (l > r || isr == 1) return cd.se;
	return cd.fi;
}

template <typename T>
int rcount(vec<T>& a, T l, T r) {//ソート済配列aから[l,r]の範囲(l以上r以下)の要素カウント
	//右端を超える最小のi-左端に引っかかる最小のi
	//l,rのどちらに対しても境界を含む/含まないを入れ替えるときupb/lwbを変えれば良い
	return upb(all(a), r) - lwb(all(a), l);
}
template <typename T>
int rcount(set<T>& a, T l, T r) {//ソート済配列aから[l,r]の範囲(l以上r以下)の要素カウント
	return a.upb(r) - a.lwb(l);
}

template <class Container, class Key>
bool has(const Container& c, const Key& x) {//sort済vector/set/map等に対しその値を持つかどうか返す
	if constexpr (is_set_like<Container>::value || is_map_like<Container>::value) {
		// set / multiset / map
		return c.find(x) != c.end();
	}
	else {
		// vector 等（ソート済前提）
		return std::binary_search(c.begin(), c.end(), x);
	}
}

//配列便利関数系
template<typename T>
bool chmin(T& M1, T M2) {
	if (M1 > M2) { M1 = M2; return 1; }
	else return 0;
}
template<typename T>
bool chmax(T& M1, T M2) {
	if (M1 < M2) { M1 = M2; return 1; }
	else return 0;
}
template<typename T>
auto vmax(T a) {
	return *max_element(all(a));
}
template<typename T>
auto vmin(T a) {
	return *min_element(all(a));
}
template<typename T>
auto vmaxi(T a) {
	return max_element(all(a)) - a.begin();
}
template<typename T>
auto vmini(T a) {
	return min_element(all(a)) - a.begin();
}
template<typename T>
auto vsum(vector<T> a) {
	T x = 0;
	for (auto i : a)x += i;
	return x;
}
template<typename T>
vec<T> inv(vec<T> a) {//0-indexed 逆関数
	vec<T> ans(a.sz);
	rp(i, a.sz) {
		ans[a[i]] = i;
	}
	return ans;
}
template<typename T>
vec<T> inv1(vec<T> a) {//1-indexed
	vec<T> ans(a.sz);
	rp(i, a.sz) {
		ans[a[i] - 1] = i + 1;
	}
	return ans;
}
template<typename T>
vec<T> zat(vec<T> a) {//座標圧縮 T=ll,int
	auto b = a;
	sort(all(b));
	b.erase(unique(all(b)), b.end());
	vec<T> c(a.size());
	rp(i, a.size()) {
		c[i] = lwb(all(b), a[i]) - b.begin();
	}
	return c;
}
template<typename T>
vec<T> rsw(vec<T> a, bool is_put0 = 1) {//累積和 T=ll,int
	if (is_put0 == 0) {
		vec<T> b = {};
		rp(i, a.sz) b.pb(a[i] + (b.sz == 0 ? 0 : b[b.sz - 1]));
		return b;
	}
	vec<T> b = { 0 };
	rp(i, a.sz) b.pb(a[i] + b[b.sz - 1]);
	return b;
}
template<typename T>
T rswsum(vec<T>& a, int l, int r, bool is_put0 = 1) {//rsw配列から元の配列の[l,r)番目(0indexed)の和を取得
	if (is_put0 == 0) {
		assert(0 <= l && l <= r);
		assert(r <= a.sz);
		return (r == 0 ? 0 : a[r - 1]) - (l == 0 ? 0 : a[l - 1]);
	}
	assert(0 <= l && l <= r);
	assert(r < a.sz);
	return a[r] - a[l];
}
template<typename T>
T rswsum2(vec<T>& a, int l, int r, bool is_put0 = 1) {//rsw配列から元の配列の[l,r]番目(0indexed)の和を取得
	return rswsum(a, l, r + 1, is_put0);
}

//文字列系
vector<pair<char, ll>>  rle(string rr) {
	vector<pair<char, ll>> ret;
	char lc;
	rep(i, 0, rr.size()) {
		if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++;
		else { ret.pb({ rr[i],1 }); }
		lc = rr[i];
	}
	return ret;
}
vector<pair<int, ll>>  rle(vi rr) {
	vector<pair<int, ll>> ret;
	int lc;
	rep(i, 0, rr.size()) {
		if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++;
		else { ret.pb({ rr[i],1 }); }
		lc = rr[i];
	}
	return ret;
}
vector<pair<ll, ll>>  rle(vll rr) {
	vector<pair<ll, ll>> ret;
	ll lc;
	rep(i, 0, rr.size()) {
		if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++;
		else { ret.pb({ rr[i],1 }); }
		lc = rr[i];
	}
	return ret;
}
bool kai(string S) {//回文か判定
	bool ans = 1;
	rp(i, S.size()) if (S[i] != S[S.size() - 1 - i]) ans = 0;
	return ans;
}
template <typename... Args>
string concat(const Args&... args) {//任意個のchat・string・int等を引数に取り文字列として繋げたstringを返す(整数はasciiでcharに変換)
	string res;
	(res += ... += args);
	return res;
}

//その他
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
bool yn(bool jg) {
	if (jg) {
		cout << "Yes" << endl; return true;
	}
	else {
		cout << "No" << endl; return false;
	}
}
bool ynab(bool jg) {
	if (jg) {
		cout << "Alice" << endl; return true;
	}
	else {
		cout << "Bob" << endl; return false;
	}
}
template<typename T>
void cp(map < T, ll >& a, T b, ll c) {//countplus
	if (a.find(b) == a.end()) a[b] = c;
	else a[b] += c;
	if (a[b] == 0) a.erase(b);
}
template<typename T>
bool cross(T a, T b, T c, T d) {//区間(a,b)と区間(c,d)が重なるか判定
	return !(b <= c || d <= a);
}
template<typename T>
bool crosse(T a, T b, T c, T d) {//区間[a,b]と区間[c,d]が重なるか判定
	return !(b < c || d < a);
}
template<typename T>
vec<vll> absort(vec<T> a, vec<T> b) {//l,rのl昇順r逆順sort
	vec<vec<T>> ab(a.sz);
	rp(i, a.sz) ab[i] = { a[i],-b[i],i };
	sort(all(ab));
	rp(i, a.sz) ab[i][1] = -ab[i][1];
	return ab;
}
template<typename T>
bool rabc(T a, T b, T c) {//円環状でa,b,cがこの順か判定 同じ値はfalse
	return ((a - b) / abs(a - b)) * ((b - c) / abs(b - c)) * ((c - a) / abs(c - a)) > 0;
}
bool labc(ll a, ll b, ll c) {//a<=b<cか判定
	return a <= b && b < c;
}
#define inr labc
bool labc2(ll a, ll b, ll c) {//a<=b<=cか判定
	return a <= b && b <= c;
}
#define inr2 labc2

vector<vector<char>> rot(vs a) {//時計回り90度回転
	vector<vector<char>> r(a[0].sz, vector<char>(a.sz));
	rp(i, a.sz)rp(j, a[0].sz) r[j][a[0].sz - 1 - i] = a[i][j];
	return r;
}
template<typename T>
vector<vector<T>> rot(vector<vector<T>> a) {
	vector<vector<T>> r(a[0].sz, vector<T>(a.sz));
	rp(i, a.sz)rp(j, a[0].sz) r[j][a.sz - 1 - i] = a[i][j];
	return r;
}

template<typename T>
vector<T> freq(vector<T> a) {// 配列から度数分布
	vector<T> r(vmax(a) + 1, 0);
	rp(i, a.sz) {
		r[a[i]]++;
	}
	return r;
}
//実行時間調整付きassert
std::chrono::steady_clock::time_point START_TIME;
void start() {
	START_TIME = std::chrono::steady_clock::now();
}

void assertt(bool b, int t) {
	if (b) return;
	if (START_TIME.time_since_epoch().count() == 0) {
		start();
	}
	auto target_time = START_TIME + std::chrono::milliseconds(t - 100);
	while (std::chrono::steady_clock::now() < target_time);
	assert(0);
}
bool testt(int t) {//tミリ秒経っていないならtrue (while(testt(1950))のように使う)
	assert(START_TIME.time_since_epoch().count() != 0);
	auto target_time = START_TIME + std::chrono::milliseconds(t - 100);
	return (std::chrono::steady_clock::now() < target_time);
}
//lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);
//S:中身型 op:左右合成 e:初期値
//F:遅延型 mapping:遅延適用後の要素 composition:遅延合成( 関数f(g()) ) id:遅延初期値(何もさせない)

using S = pll;
using F = ll;
S op(S a, S b) {
	return {a.fi+b.fi,a.se+b.se};
}

S e() {
	return { 0,0 };
}
using segt = segtree<S, op, e>;
/*

S mapping(F x, S a) {//xをaに作用(x初期値に注意) S[l]~S[r]のopであるSにF適用するとF(S[l])~F(S[r])のopになる必要がある 、つまりL~Rの代表にFかけてもL~Rの代表であり続けられるようS作る必要がある
	if(x==0) return a;
	else return {a.se,a.se};
}
F composition(F f, F g) {//fの方が後(f初期値に注意) Fを何個合成しても1つのFで表せる
	if(f==0 && g==0 )return 0;
	return 1;
}
F id() { return 0; }
using lsegt = lazy_segtree<S, op, e, F, mapping, composition, id>;
*/
//cout<<setprecision(15)<<fixed<<
//function<返り値の型(引数の型1, 引数の型2, ...)> 関数名 = [&](引数の型1 引数名1, 引数の型2, 引数名2, ...)
//function<ll(int,int)> f=[&](int a,int b)
//再帰しない場合 auto f=[&](int a,int b) ->ll{} 
int mxkj = 200100;//階乗に入れる値の最大値
vector<mint> kj(mxkj + 1), gkj(mxkj + 1);
bool iskjset = 0;
void kjset(void) {//kjを使う場合は必ず呼ぶ
	iskjset = 1;
	kj[0] = 1;//階乗
	rep(i, 1, mxkj + 1) {
		kj[i] = kj[i - 1] * i;
	}
}
void kjset(int maxkj) {
	iskjset = 1;
	mxkj = maxkj;
	kj.resize(mxkj + 1);
	gkj.resize(mxkj + 1);
	kj[0] = 1;//階乗
	rep(i, 1, mxkj + 1) {
		kj[i] = kj[i - 1] * i;
	}
}
auto cmb = [](int fst, int snd) {
	assert(iskjset);
	bool ck = 1;//範囲外値でエラーを返すなら1(ck=0でもpowの引数など他の値が範囲外にならないか要確認)
	if (0 <= fst && fst <= mxkj && 0 <= snd && snd <= fst);
	else {
		if (ck) assert(0);
		else return mint(0);
	}
	if (gkj[snd] == 0) gkj[snd] = mint(1) / kj[snd];
	if (gkj[fst - snd] == 0) gkj[fst - snd] = mint(1) / kj[fst - snd];
	return  kj[fst] * gkj[snd] * gkj[fst - snd];
	};
auto pmt = [](int fst, int snd) {
	assert(iskjset);
	bool ck = 1;//範囲外値でエラーを返すなら1(ck=0でもpowの引数など他の値が範囲外にならないか要確認)
	if (0 <= fst && fst <= mxkj && 0 <= snd && snd <= fst);
	else {
		if (ck) assert(0);
		else return mint(0);
	}
	if (gkj[fst - snd] == 0) gkj[fst - snd] = mint(1) / kj[fst - snd];
	return  kj[fst] * gkj[fst - snd];
	};
auto getgkj = [](int fst) {
	if (gkj[fst] == 0) gkj[fst] = 1 / kj[fst];
	return gkj[fst];
	};
vec<mint> conv_sp(vmint a, vmint sp, ll mxi = 200100) {//疎な場合のconv高速化 aの長さN,spの非0係数K個としてO(NK)
	vec<pair<int, mint>> sps;
	int spmxi = -1;
	rp(i, sp.size()) {
		if (sp[i] != 0) {
			sps.pb({ i,sp[i] });
			spmxi = i;
		}
	}
	if (spmxi == -1) return { 0 };
	vmint r(min(mxi, ll(a.sz) + spmxi), 0);
	rp(i, a.sz) {
		for (auto j : sps) {
			if (i + j.fi < mxi)r[i + j.fi] += j.se * a[i];
		}
	}
	return r;
}
vec<mint> div_sp(vmint f, vmint sp, ll mxi = 200100) {//f/spをmxiまで計算 ただしspのx^0項非0 spの非0係数K個としてO(mxiK)
	assert(sp.sz > 0 && sp[0] != 0);
	vec<pair<int, mint>> sps;
	int spmxi = -1;
	rp(i, sp.size()) {
		if (sp[i] != 0) {
			sps.pb({ i,sp[i] });
			spmxi = i;
		}
	}
	vec<mint> r(mxi, 0);
	f.resize(mxi);
	mint gsp0 = 1 / sp[0];
	rp(i, mxi) {
		r[i] = f[i] * gsp0;
		for (auto j : sps) {
			if (i + j.fi < mxi)f[i + j.fi] -= r[i] * j.se;
		}
	}
	return r;
}
vec<mint> conv(vmint a, vmint b, ll mxi = 200100) {//a.sz+b.sz=nとしてO(nlogn) a.sz+b.sz>2^23=8.3e6を超えると畳み込み不可能
	if (a.sz > mxi) a.resize(mxi);
	if (b.sz > mxi) b.resize(mxi);
	vmint r = convolution(a, b);
	if (r.size() > mxi) r.resize(mxi);
	return r;
}
mint convget(vmint a, vmint b, ll i) {//conv(a,b)[i]をO(a.sz+b.sz+i)で求める
	if (i < 0) return 0;
	mint r = 0;
	rp(ii, i + 1) {
		if (ii < a.sz && i - ii < b.sz)r += a[ii] * b[i - ii];
	}
	return r;
}
vec<mint> vinv(vmint f, ll mxi = 200100) {// O(mxi・logmxi)
	assert(f.sz > 0 && f[0] != 0);
	vec<mint> g = { mint(1) / f[0] };
	f.resize(mxi); // fを最初にリサイズ
	for (ll len = 1; len < mxi; len <<= 1) {//g←g(2-fg)をlog(mxi)回
		int need = min(mxi, len << 1);
		auto fg = conv(vec<mint>(f.begin(), f.begin() + need), g, need);    // f * g

		for (int i = 0; i < need; i++) fg[i] = -fg[i];
		fg[0] += 2;  // 2 - f*g

		g = conv(g, fg, need);
	}
	return g;
}
vmint log(vmint f, ll mxi = 200100) {//log(f)を求める(ただしf[0]=1が必要) O(mxi・logmxi) ∫(f')/f
	if (f.sz > mxi) f.resize(mxi);
	assert(f[0] == 1);
	if (f.sz == 1) return { 0 };
	vmint bf(f.sz - 1);//fの微分
	rp(i, f.sz - 1) bf[i] = f[i + 1] * (i + 1);
	vmint bg = conv(bf, vinv(f, mxi), mxi);
	vmint g(bg.sz);
	g[0] = 0;
	rp(i, bg.sz - 1) g[i + 1] = bg[i] / (i + 1);
	return g;
}
vmint exp(vmint f, ll mxi = 200100) {//exp(f)をニュートン法で求める(ただしf[0]=0が必要) O(mxi・logmxi) 
	assert(f[0] == 0);
	vec<mint> g = { 1 };
	f.resize(mxi); // fを最初にリサイズ
	for (ll len = 1; len < mxi; len <<= 1) {//g←g(1-log(g)+f)をlog(mxi)回
		int need = min(mxi, len << 1);
		vmint x = log(g, need);
		x.resize(need);
		rp(i, need) x[i] = f[i] - x[i];
		x[0]++;
		g = conv(g, x, need);
	}
	return g;
}
vec<mint> vpow(vmint a, ll p, ll mxi = 200100) {//a[0]+a[1]x+a[2]x^2...のp乗をa^p=exp(log(a))を利用して計算 O(mxi・logmxi)
	int d = 0;//前から何個0が続くか
	rp(i, a.sz) {
		if (a[i] == 0) d++;
		else break;
	}
	assert(p >= 0 || d == 0);//p<0かつd>0は計算不能(FPSで定義されない)
	if (p == 0 || double(d) * p >= mxi || d == a.sz) {//0乗 or all zero
		vmint r(mxi, 0);
		if (p == 0) r[0] = 1;
		return r;
	}
	//a[0]=1になるように前d個の0を消し、a全体をa[0]で割る補正
	mint c = 1, ad = 1;
	if (a[d] != 1) {
		ad = a[d];
		c = 1 / a[d];
		rp(i, a.sz) a[i] *= c;
	}
	if (d > 0) {
		rp(i, a.sz - d)a[i] = a[i + d];
		a.resize(a.sz - d);
	}
	vmint ploga = log(a, mxi - d * p);//p*log(a)
	rp(i, ploga.sz) ploga[i] *= p;
	vmint r = exp(ploga, mxi - d * p);
	mint adp;//ad^p
	if (p < 0) adp = mint(c).pow(-p);
	else  adp = ad.pow(p);
	rp(i, r.sz) r[i] *= adp;
	r.resize(mxi);
	rrp(i, mxi) {
		if (i < d * p)r[i] = 0;
		else r[i] = r[i - d * p];
	}
	return r;
}
vec<mint> vap(vvmint a, ll mxi = 200100) {//多項式総積 次数の総和NとしてO(N(logN)^2)
	if (a.sz == 0) return { 1 };
	queue<vmint> q;
	for (auto& i : a) q.push(i);
	while (q.sz > 1) {
		vmint p1 = q.front();
		q.pop();
		vmint p2 = q.front();
		q.pop();
		vmint np = conv(p1, p2, mxi);
		q.push(np);
	}
	return q.front();
}
vec<mint> vquot(vmint g, vmint f) {//多項式除算 N次g,M次fに対してg=qf+r(m-1次以下)を満たすqをO(NlogN)で求める
	while (f.sz > 0 && f[f.sz - 1] == 0) f.pop_back();
	assert(f.sz != 0);
	while (g.sz > 0 && g[g.sz - 1] == 0) g.pop_back();
	if (g.sz < f.sz) return {};
	int n = int(g.sz) - 1, m = int(f.sz) - 1;
	vmint revg = g; reverse(all(revg));
	vmint revf = f; reverse(all(revf));
	vmint revq = conv(revg, vinv(revf, n - m + 1), n - m + 1);
	revq.resize(n - m + 1);
	reverse(all(revq));//ここでrevqがqを表すようになる
	return revq;
}
vec<mint> vmod(vmint g, vmint f) {//多項式の余り N次g,M次fに対してg=qf+r(m-1次以下)を満たすrをO(NlogN)で求める
	while (f.sz > 0 && f[f.sz - 1] == 0) f.pop_back();
	assert(f.sz != 0);
	vmint q = vquot(g, f);
	vmint qf = conv(q, f, f.sz - 1);
	vmint r(f.sz - 1);
	g.resize(f.sz - 1);
	qf.resize(f.sz - 1);
	rp(i, f.sz - 1) {
		r[i] = g[i] - qf[i];
	}
	while (r.sz > 0 && r[r.sz - 1] == 0) r.pop_back();
	return r;
}
vec<mint> vpowmod(vmint g, vmint f, ll p) {//多項式の余り g^p mod f f,gの次数NとしてO(NlogNlogp)
	vmint r = { 1 };
	assert(p < (ll(1) << 60));
	rrp(i, 60) {
		r = conv(r, r, 2 * r.sz);
		r = vmod(r, f);
		if (p & (ll(1) << i)) {
			r = conv(r, g, r.sz + g.sz);
			r = vmod(r, f);
		}
	}
	return r;
}
vec<mint> vplus(vmint f, vmint g) {//f+g
	if (f.sz > g.sz) swap(f, g);
	vmint r(g.sz, 0);
	rp(i, f.sz) r[i] = f[i] + g[i];
	rep(i, f.sz, g.sz) r[i] = g[i];
	return r;
}
mint vdn(vmint f, mint a) {//f(x)にaを代入(f(a)を計算)
	mint r = 0;
	rp(i, f.sz) r += f[i] * a.pow(i);
	return r;
}
vec<mint> v1pow(ll p, ll mxi = 200100) {//(1/(1-x))={1,1,1,...}^pをmxiまでO(mxi)で求める　p+mxiまでkjの前計算が必要 gkjが求まっていない場合はO(mxi・log998)
	assert(p + mxi - 1 <= mxkj);
	if (p == 0) {
		vmint r(mxi, 0);
		r[0] = 1;
		return r;
	}
	vmint r(mxi);
	rp(i, mxi) r[i] = cmb(p + i - 1, i);
	return r;
}
vec<mint> v1apow(mint a, ll p, ll mxi = 200100) {//(1+ax)^pをmxiまでa==1でO(mxi),a!=1でO(mxi・logp)で求める　mxiまでkjの前計算が必要 gkjが求まっていない場合はO(mxi・log998)
	assert(mxi <= mxkj);
	vmint r(mxi, 0);
	ll siz = min(mxi, p + 1);
	if (a == 1) rp(i, siz) {
		r[i] = cmb(p, i);
	}
	else rp(i, siz) {
		r[i] = cmb(p, i) * a.pow(i);
	}
	return r;
}
template<typename T>
mint parsum(vec<T> a, T s) {//部分和問題 配列aから0個以上選んで和をsにする通り数 aの総和xとしてO(x(logx)^2)
	if (s < 0) return 0;
	int n = a.sz;
	vvmint p(n);
	rp(i, n) {
		p[i] = vmint(a[i] + 1, 0);
		p[i][0] = 1;
		p[i][a[i]] += 1;
	}
	vmint ans = vap(p, s + 1);
	if (ans.sz <= s)return 0;
	return ans[s];
}

vmint apowsum(vmint a, ll m) {//長さNの配列aに対しΣ(a[i]^k)をk=0,1,2...Mに対してO(N(logN)^2+MlogM)で列挙
	int n = a.sz;
	vvmint x(n);
	rp(i, n) x[i] = { 1,-a[i] };
	vmint y = vap(x, n + 1);
	y = log(y,m+1);
	rp(i, y.sz) y[i] = -y[i] * i;
	y[0] = n;
	return y;
}

int main() {
	int n, m;
	cin >> n >> m;
	vmint a(n);
	ain(a);
	vmint ans = apowsum(a, m);
	rp(i, m) cout << ans[i + 1] << " ";
}