/** * author: otera **/ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long typedef long long ll; typedef unsigned long long ul; typedef unsigned int ui; typedef long double ld; const int inf=1e9+7; const ll INF=1LL<<60 ; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef complex Point; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair P; typedef pair LDP; typedef pair LP; #define fr first #define sc second #define all(c) c.begin(),c.end() #define pb push_back #define debug(x) cerr << #x << " = " << (x) << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } long long modinv(long long a, long long mod) { long long b = mod, u = 1, v = 0; while (b) { long long t = a/b; a -= t*b; swap(a, b); u -= t*v; swap(u, v); } u %= mod; if (u < 0) u += mod; return u; } const int MOD = 998244353; namespace NTT { // const int MOD = 998244353; // to be set appropriately const long long PR = 3; // to be set appropriately void trans(vector &v, bool inv = false) { int n = (int)v.size(); for (int i = 0, j = 1; j < n-1; j++) { for (int k = n>>1; k > (i ^= k); k >>= 1); if (i > j) swap(v[i], v[j]); } for (int t = 2; t <= n; t <<= 1) { long long bw = modpow(PR, (MOD-1)/t, MOD); if (inv) bw = modinv(bw, MOD); for (int i = 0; i < n; i += t) { long long w = 1; for (int j = 0; j < t/2; ++j) { int j1 = i + j, j2 = i + j + t/2; long long c1 = v[j1], c2 = v[j2] * w % MOD; v[j1] = c1 + c2; v[j2] = c1 - c2 + MOD; while (v[j1] >= MOD) v[j1] -= MOD; while (v[j2] >= MOD) v[j2] -= MOD; w = w * bw % MOD; } } } if (inv) { long long inv_n = modinv(n, MOD); for (int i = 0; i < n; ++i) v[i] = v[i] * inv_n % MOD; } } // C is A*B vector mult(vector A, vector B) { int size_a = 1; while (size_a < A.size()) size_a <<= 1; int size_b = 1; while (size_b < B.size()) size_b <<= 1; int size_fft = max(size_a, size_b) << 1; vector cA(size_fft, 0), cB(size_fft, 0), cC(size_fft, 0); for (int i = 0; i < A.size(); ++i) cA[i] = A[i]; for (int i = 0; i < B.size(); ++i) cB[i] = B[i]; trans(cA); trans(cB); for (int i = 0; i < size_fft; ++i) cC[i] = cA[i] * cB[i] % MOD; trans(cC, true); vector res((int)A.size() + (int)B.size() - 1); for (int i = 0; i < res.size(); ++i) res[i] = cC[i]; return res; } }; ll get_root(ll p) { for(int r = 2; r < p; ++ r) { int x = 1; set se; while(true) { if(se.size() == p - 1) return r; if(se.count(x)) break; se.insert(x); x = x * r % p; } } assert(false); } struct ComplexNumber { double real, imag; inline ComplexNumber& operator = (const ComplexNumber &c) {real = c.real; imag = c.imag; return *this;} friend inline ostream& operator << (ostream &s, const ComplexNumber &c) {return s<<'<'<';} }; inline ComplexNumber operator + (const ComplexNumber &x, const ComplexNumber &y) { return {x.real + y.real, x.imag + y.imag}; } inline ComplexNumber operator - (const ComplexNumber &x, const ComplexNumber &y) { return {x.real - y.real, x.imag - y.imag}; } inline ComplexNumber operator * (const ComplexNumber &x, const ComplexNumber &y) { return {x.real * y.real - x.imag * y.imag, x.real * y.imag + x.imag * y.real}; } inline ComplexNumber operator * (const ComplexNumber &x, double a) { return {x.real * a, x.imag * a}; } inline ComplexNumber operator / (const ComplexNumber &x, double a) { return {x.real / a, x.imag / a}; } const int MAX = 1<<19; // must be 2^n struct FFT { vector AT, BT, CT; void DTM(vector &F, bool inv) { int N = MAX; for (int t = N; t >= 2; t >>= 1) { double ang = acos(-1.0)*2/t; for (int i = 0; i < t/2; i++) { ComplexNumber w = {cos(ang*i), sin(ang*i)}; if (inv) w.imag = -w.imag; for (int j = i; j < N; j += t) { ComplexNumber f1 = F[j] + F[j+t/2]; ComplexNumber f2 = (F[j] - F[j+t/2]) * w; F[j] = f1; F[j+t/2] = f2; } } } for (int i = 1, j = 0; i < N; i++) { for (int k = N >> 1; k > (j ^= k); k >>= 1); if (i < j) swap(F[i], F[j]); } } // C is A*B void mult(vector &A, vector &B, vector &C) { AT.assign(MAX, {0.0, 0.0}); BT.assign(MAX, {0.0, 0.0}); CT.assign(MAX, {0.0, 0.0}); for (int i = 0; i < MAX; ++i) AT[i] = {(double)A[i], 0.0}; for (int i = 0; i < MAX; ++i) BT[i] = {(double)B[i], 0.0}; DTM(AT, false); DTM(BT, false); for (int i = 0; i < MAX; ++i) CT[i] = AT[i] * BT[i]; DTM(CT, true); for (int i = 0; i < MAX; ++i) { CT[i] = CT[i] / MAX; C[i] = (long long)(CT[i].real + 0.5); } } }; void solve() { int p; cin >> p; // vector a(MAX, 0), b(MAX, 0); vector a(p, 0), b(p, 0); rep(i, p - 1) { cin >> a[i + 1]; } rep(i, p - 1) { cin >> b[i + 1]; } if(p == 2) { cout << a[1] * b[1] % MOD << endl; return; } int r = get_root(p); vector x(1<<17), y(1<<17); int v = 1; rep(i, p - 1) { x[i] = a[v], y[i] = b[v]; // v = r ^ i // cerr << v << " "; v = v * r % p; } // cerr << endl; auto z = NTT::mult(x, y); // vector c(MAX); // FFT fft; // fft.mult(a, b, c); vector ans(p, 0); v = 1; rep(i, (int)z.size()) { ans[v] += z[i]; // v = r ^ i // ans[v] += c[i]; ans[v] %= MOD; v = v * r % p; } for(int i = 1; i <= p - 1; ++ i) { cout << ans[i] << " "; } cout << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); //cout << fixed << setprecision(10); //int t; cin >> t; rep(i, t)solve(); solve(); return 0; }