#include <bits/stdc++.h>
using namespace std;
template<int M>
struct static_mint {
static_assert(0 < M, "Module must be positive");
int val;
static_mint() : val() {}
static_mint(long long x) : val(x % M) { if (val < 0) val += M; }
static_mint pow(long long n) const {
static_mint ans = 1, x(*this);
for (; n > 0; n /= 2) {
if (n & 1) ans *= x;
x *= x;
}
return ans;
}
static_mint inv() const {
return pow(M - 2);
}
static_mint operator+() const {
static_mint m;
m.val = val;
return m;
}
static_mint operator-() const {
static_mint m;
m.val = (val == 0 ? 0 : M - val);
return m;
}
static_mint &operator+=(const static_mint &m) {
if ((val += m.val) >= M) val -= M;
return *this;
}
static_mint &operator-=(const static_mint &m) {
if ((val -= m.val) < 0) val += M;
return *this;
}
static_mint &operator*=(const static_mint &m) {
val = (long long) val * m.val % M;
return *this;
}
static_mint &operator/=(const static_mint &m) {
val = (long long) val * m.inv().val % M;
return *this;
}
friend static_mint operator+(const static_mint &lhs, const static_mint &rhs) {
return static_mint(lhs) += rhs;
}
friend static_mint operator-(const static_mint &lhs, const static_mint &rhs) {
return static_mint(lhs) -= rhs;
}
friend static_mint operator*(const static_mint &lhs, const static_mint &rhs) {
return static_mint(lhs) *= rhs;
}
friend static_mint operator/(const static_mint &lhs, const static_mint &rhs) {
return static_mint(lhs) /= rhs;
}
friend bool operator==(const static_mint &lhs, const static_mint &rhs) {
return lhs.val == rhs.val;
}
friend bool operator!=(const static_mint &lhs, const static_mint &rhs) {
return lhs.val != rhs.val;
}
static_mint &operator++() {
return *this += 1;
}
static_mint &operator--() {
return *this -= 1;
}
static_mint operator++(int) {
static_mint result(*this);
*this += 1;
return result;
}
static_mint operator--(int) {
static_mint result(*this);
*this -= 1;
return result;
}
template<typename T>
explicit operator T() const {
return T(val);
}
friend std::ostream &operator<<(std::ostream &os, const static_mint &m) {
return os << m.val;
}
friend std::istream &operator>>(std::istream &is, static_mint &m) {
long long x;
return is >> x, m = x, is;
}
};
template <typename>
struct is_mint_helper : std::false_type { };
template <int M>
struct is_mint_helper<static_mint<M>> : std::true_type { };
template <typename T>
struct is_mint : is_mint_helper<typename std::decay<T>::type> { };
namespace ntt {
template<int P>
struct prime_info {
constexpr static int root = 0, root_pw = 0;
};
template<>
struct prime_info<7340033> {
constexpr static int root = 5, root_pw = 1 << 20;
};
template<>
struct prime_info<998244353> {
constexpr static int root = 15311432, root_pw = 1 << 23;
};
template<>
struct prime_info<754974721> {
constexpr static int root = 739831874, root_pw = 1 << 24;
};
template<>
struct prime_info<167772161> {
constexpr static int root = 243, root_pw = 1 << 25;
};
template<>
struct prime_info<469762049> {
constexpr static int root = 2187, root_pw = 1 << 26;
};
std::vector<int> rev = {0};
void compute_bit_reverse(int lg) {
static int computed = 0;
if (lg <= computed) return;
rev.resize(1 << lg);
for (int i = (1 << computed); i < (1 << lg); i++) {
rev[i] = (rev[i >> 1] >> 1) ^ ((i & 1) << 30);
}
computed = lg;
}
template<int M>
std::vector<static_mint<M>> root = {0, 1};
template<int M>
void compute_roots(int lg) {
static int computed = 1;
if (lg <= computed) return;
root<M>.resize(1 << lg);
for (int k = computed; k < lg; k++) {
static_mint<M> z(prime_info<M>::root);
for (int i = (1 << (k + 1)); i < prime_info<M>::root_pw; i <<= 1) {
z *= z;
}
for (int i = (1 << (k - 1)); i < (1 << k); i++) {
root<M>[i << 1] = root<M>[i];
root<M>[i << 1 | 1] = root<M>[i] * z;
}
}
}
template<int M>
void ntt(std::vector<static_mint<M>> &a) {
int n = int(a.size()), lg = 32 - __builtin_clz(n) - 1;
compute_bit_reverse(lg);
compute_roots<M>(lg);
int shift = 31 - lg;
for (int i = 0; i < n; i++) {
if (i < (rev[i] >> shift)) {
std::swap(a[i], a[rev[i] >> shift]);
}
}
for (int k = 1; k < n; k <<= 1) {
static_mint<M> wl = prime_info<M>::root;
for (int i = 2 * k; i < prime_info<M>::root_pw; i <<= 1) {
wl *= wl;
}
for (int i = 0; i < n; i += 2 * k) {
for (int j = 0; j < k; j++) {
static_mint<M> z = root<M>[j + k] * a[i + j + k];
a[i + j + k] = a[i + j] - z;
a[i + j] = a[i + j] + z;
}
}
}
}
template<int M>
std::enable_if_t<prime_info<M>::root != 0, std::vector<static_mint<M>>>
convolution(std::vector<static_mint<M>> a, std::vector<static_mint<M>> b) {
int n = 1;
while (n < a.size() + b.size()) {
n <<= 1;
}
a.resize(n);
b.resize(n);
ntt(a), ntt(b);
static_mint<M> n_inv = static_mint<M>(n).inv();
for (int i = 0; i < n; i++) {
a[i] *= b[i] * n_inv;
}
reverse(a.begin() + 1, a.end());
ntt(a);
return a;
}
template<int M>
static_mint<M> garner(int a1, int a2, int a3) {
constexpr static int M1 = 754974721, M2 = 167772161, M3 = 469762049;
const static int R12 = static_mint<M2>(M1).inv().val;
const static int R13 = static_mint<M3>(M1).inv().val;
const static int R23 = static_mint<M3>(M2).inv().val;
int x1 = a1;
int x2 = (long long) (a2 - x1) * R12 % M2;
if (x2 < 0) x2 += M2;
int x3 = ((long long) (a3 - x1) * R13 % M3 - x2) * R23 % M3;
if (x3 < 0) x3 += M3;
return static_mint<M>(x1) + static_mint<M>(x2) * M1 + static_mint<M>(x3) * M1 * M2;
}
template<int M>
std::enable_if_t<prime_info<M>::root == 0, std::vector<static_mint<M>>>
convolution(std::vector<static_mint<M>> a, const std::vector<static_mint<M>> &b) {
constexpr static int M1 = 754974721, M2 = 167772161, M3 = 469762049;
auto c1 = convolution(vector<static_mint<M1>>(a.begin(), a.end()), vector<static_mint<M1>>(b.begin(), b.end()));
auto c2 = convolution(vector<static_mint<M2>>(a.begin(), a.end()), vector<static_mint<M2>>(b.begin(), b.end()));
auto c3 = convolution(vector<static_mint<M3>>(a.begin(), a.end()), vector<static_mint<M3>>(b.begin(), b.end()));
int n = int(c1.size());
a.resize(n);
for (int i = 0; i < n; i++) {
a[i] = garner<M>(c1[i].val, c2[i].val, c3[i].val);
}
return a;
}
template<int M = 998244353, typename T>
std::enable_if_t<!is_mint<T>::value, std::vector<T>>
convolution(const std::vector<T> &a, const std::vector<T> &b) {
auto f = convolution(std::vector<static_mint<M>>(a.begin(), a.end()),
std::vector<static_mint<M>>(b.begin(), b.end()));
return vector<T>(f.begin(), f.end());
}
template<typename T>
void normalize(const std::vector<T> &a) {
for (int i = int(a.size()) - 1; i >= 0; i--) {
if (a[i]) {
a.resize(i + 1);
return;
}
}
a.clear();
}
}
template <typename T>
struct polynomial : public std::vector<T> {
template <typename...args>
polynomial(args...A) : std::vector<T>(A...) { }
polynomial(const std::initializer_list<T> &l) : std::vector<T>(l) { }
int deg() const noexcept {
return (int) this->size() - 1;
}
void normalize() {
for (int i = deg(); i >= 0; i--) {
if ((*this)[i]) {
this->resize(i + 1);
return;
}
}
this->clear();
}
polynomial &operator+=(const polynomial &q) {
if (q.size() > this->size()) {
this->resize(q.size());
}
for (int i = 0; i < q.size(); i++) {
(*this)[i] += q[i];
}
normalize();
return *this;
}
polynomial &operator-=(const polynomial &q) {
if (q.size() > this->size()) {
this->resize(q.size());
}
for (int i = 0; i < q.size(); i++) {
(*this)[i] -= q[i];
}
normalize();
return *this;
}
void naive_mul(polynomial &a, const polynomial &b) const {
polynomial result(a.deg() + b.deg() + 1);
for (int i = 0; i <= a.deg(); i++) {
for (int j = 0; j <= b.deg(); j++) {
result[i + j] += a[i] * b[j];
}
}
a.swap(result);
}
void ntt_mul(polynomial &fa, polynomial fb) const {
fa = ntt::convolution(fa, fb);
}
polynomial &operator*=(const polynomial &q) {
if (this->empty() || q.empty()) {
this->clear();
} else if (this->size() <= 60) {
naive_mul(*this, q);
} else {
ntt_mul(*this, q);
}
normalize();
return *this;
}
polynomial &operator*=(const T &val) {
for (auto &x : *this) {
x *= val;
}
return *this;
}
void divide(polynomial &a, polynomial b) const {
assert(!b.empty());
if (a.deg() < b.deg()) {
a.clear();
return;
}
reverse(a.begin(), a.end());
int sz = a.deg() - b.deg() + 1;
a %= sz;
reverse(b.begin(), b.end());
a *= b.inv(sz);
a %= sz;
reverse(a.begin(), a.end());
}
polynomial &operator/=(const polynomial &q) {
divide(*this, q);
normalize();
return *this;
}
polynomial &operator/=(T val) {
val = 1 / val;
for (auto &x : *this) {
x *= val;
}
return *this;
}
polynomial &operator%=(const polynomial &q) {
*this -= q * (*this / q);
normalize();
return *this;
}
polynomial &operator%=(size_t k) {
if (k <= deg())
this->resize(k);
return *this;
}
polynomial &operator<<=(size_t k) {
if (this->size() <= k) {
this->clear();
} else {
polynomial result(this->begin() + k, this->end());
this->swap(result);
}
return *this;
}
polynomial &operator>>=(size_t k) {
polynomial result(this->size() + k);
std::copy(this->begin(), this->end(), result.begin() + k);
this->swap(result);
return *this;
}
T operator()(const T &val) {
T ans = 0;
for (int i = deg(); i >= 0; i--) {
ans = (ans * val + (*this)[i]);
}
return ans;
}
friend polynomial operator+(polynomial p, const polynomial &q) {
p += q;
return p;
}
friend polynomial operator-(polynomial p, const polynomial &q) {
p -= q;
return p;
}
friend polynomial operator*(polynomial p, const polynomial &q) {
p *= q;
return p;
}
friend polynomial operator*(polynomial p, const T &val) {
p *= val;
return p;
}
friend polynomial operator*(const T &val, polynomial p) {
p *= val;
return p;
}
friend polynomial operator/(polynomial p, const polynomial &q) {
p /= q;
return p;
}
friend polynomial operator/(polynomial p, const T &val) {
p /= val;
return p;
}
friend polynomial operator%(polynomial p, const polynomial &q) {
p %= q;
return p;
}
friend polynomial operator%(polynomial p, size_t k) {
p %= k;
return p;
}
friend polynomial operator<<(polynomial p, size_t k) {
p <<= k;
return p;
}
friend polynomial operator>>(polynomial p, size_t k) {
p >>= k;
return p;
}
polynomial inv(int k = -1) const {
if (k == -1)
k = this->size();
assert(!this->empty() && (*this)[0] != 0);
polynomial b(1, 1 / (*this)[0]);
for (int i = 2; i <= (k << 1); i <<= 1) {
polynomial temp = (*this) % i;
temp *= b, temp %= i;
temp *= T(-1), temp[0] += 2;
b *= temp, b %= i;
}
b.resize(k);
return b;
}
polynomial derivative() const {
if (deg() < 1) {
return {};
}
polynomial result(this->size() - 1);
for (int i = 1; i < this->size(); i++) {
result[i - 1] = i * (*this)[i];
}
return result;
}
polynomial integral() const {
if (this->empty()) {
return {};
}
polynomial result(this->size() + 1);
for (int i = 0; i < this->size(); i++) {
result[i + 1] = (*this)[i] / (i + 1);
}
return result;
}
polynomial log(int k = -1) const {
assert(!this->empty() && (*this)[0] == 1);
if (k == -1)
k = this->size();
polynomial result = ((derivative() % k) * inv(k)).integral();
result.resize(k);
return result;
}
polynomial exp(int k = -1) const {
assert(this->empty() || (*this)[0] == 0);
if (k == -1)
k = this->size();
polynomial q(1, 1);
for (int i = 2; i <= (k << 1); i <<= 1) {
polynomial temp = polynomial(1, 1) + (*this % i) - q.log(i);
q *= temp, q %= i;
}
q.resize(k);
return q;
}
polynomial pow(int n, int k = -1) const {
if (k == -1)
k = this->size();
if (this->empty())
return polynomial(k);
T alpha = 0;
int pw = 0;
for (int i = 0; i < this->size(); i++) {
if ((*this)[i]) {
alpha = (*this)[i];
pw = i;
break;
}
}
if ((long long)pw * n >= k) {
return polynomial(k);
}
polynomial<T> b = (*this) << pw;
b /= alpha;
b = (T(n) * b.log(k)).exp(k);
b >>= pw * n;
b *= alpha.pow(n);
b.resize(k);
return b;
}
template <typename U>
std::vector<T> multipoint_evaluation(const std::vector<U> &pt) {
int n = (int) pt.size();
std::vector<polynomial> tree(4 * n);
auto build = [&](int i, int l, int r, const auto &self) -> void {
if (l == r) {
tree[i] = {T(-pt[l]), 1};
} else {
int mid = (l + r) >> 1;
self(i << 1, l, mid, self);
self(i << 1 | 1, mid + 1, r, self);
tree[i] = tree[i << 1] * tree[i << 1 | 1];
}
};
build(1, 0, n - 1, build);
std::vector<T> result(n);
auto dfs = [&](int i, int l, int r, polynomial p, const auto &self) -> void {
p %= tree[i];
if (l == r) {
result[l] = (p.empty() ? 0 : p[0]);
} else {
int mid = (l + r) >> 1;
self(i << 1, l, mid, p, self);
self(i << 1 | 1, mid + 1, r, p, self);
}
};
dfs(1, 0, n - 1, *this, dfs);
return result;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
using mint = static_mint<998244353>;
int n, m;
cin >> n >> m;
polynomial<mint> c(n), p(m);
for (int i = 0; i < n; i++) cin >> c[i];
for (int i = 0; i < m; i++) cin >> p[i];
auto result = c.multipoint_evaluation(p);
for (int i = 0; i < m; i++) {
cout << result[i] << ' ';
}
cout << '\n';
return 0;
}