fwht_codeforces.cpp

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;

constexpr ll mod = 1e9+9;

template<class T, class U> T fpow(T _base, U _pow, T _mod){_base %= _mod; T _x = 1; for(; _pow > 0; _pow >>= 1){ if(_pow&1) _x = _x*_base%_mod; _base = _base*_base%_mod;} return _x;}
template<class T> T divmod(T _a, T _b, T _mod){return _a*fpow(_b, _mod-2, _mod)%_mod;}

template<class T> struct M2{
	T w, x, y, z, det;
	M2(T a, T b, T c, T d){
		w = a, x = b, y = c, z = d;
		det = divmod(1LL, w*z-x*y, mod);
	}
};
const M2<ll> M[] = {{1, 1, 1, 0}, {0, 1, 1, 1}, {1, 1, 1, -1}};
//                  OR             AND          XOR

template<class T> void go(vector<T> &v, bool inv, int k){
	int n = (int)size(v);
	for(int len = 1, bit = 0; len < n; len *= 2, bit = (bit+1)%k){
		for(int pos = 0; pos < n; pos += len*2){
			for(int i = 0; i < len; i++){
				T &a = v[pos+i];
				T &b = v[pos+i+len];
				if(!inv)
					tie(a, b) = make_pair((M[bit].w*a+M[bit].x*b)%mod, (M[bit].y*a+M[bit].z*b)%mod);
				else
					tie(a, b) = make_pair((M[bit].z*a-M[bit].y*b)%mod * M[bit].det % mod, (M[bit].w*b-M[bit].x*a)%mod * M[bit].det % mod);
			}
		}
	}
}

template<class T> void mul(vector<T> &va, vector<T> &vb, int k){
	int n = (int)size(va);
	n = 2<<__lg(n-1);
	if(__builtin_ctz(n)&1)
		n <<= 1;
	va.resize(n), vb.resize(n);
	go(va, 0, k); go(vb, 0, k);
	for(int i = 0; i < n; i++){
		va[i] *= vb[i];
		va[i] %= mod;
	}
	go(va, 1, k);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin>>n;
	vector<ll> a(n), b(n);
	for(int i = 0; i < n; i++)
		cin>>a[i];
	for(int i = 0; i < n; i++)
		cin>>b[i];
	
	mul(a, b, 3);
	
	int m = (int)size(a);
	while(m and !a[m-1])
		m--;
	
	for(int i = 0; i < m; i++){
		if(a[i] < 0) a[i] += mod;
		cout<<a[i]<<' ';
	}
}