#include <bits/stdc++.h>
#define dbg(x) cerr<<#x<<" = "<<x<<endl;
#define dbg_v(v,n) {cerr<<#v<<" = [";for(int III=0;III<=n;III++)cerr<<v[III]<<(III!=n?",":"]\n");}
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define MOD 1000000007
#define zeros(x) x&(x-1)^x
#define fi first
#define se second
#define Nmax 500005
#define cd complex<double>
using namespace std;

int rev(int x, int lg){
	int ans = 0;
	for (int i=0;i<lg;i++) if (x & (1<<i)) ans += (1<<(lg-i-1));
	return ans;
}

void FFT(vector<cd> &A, bool inv){
	int sz = A.size();
	int lg = 1;
	while (1<<lg < sz) lg++;
	for (int i=0;i<A.size();i++) if (i < rev(i,lg)) swap(A[i],A[rev(i,lg)]);

	for (int len = 2;len<=sz;len *= 2){
		double ang = 2 * acos(-1) / len * (inv ? -1 : 1);
		cd d(cos(ang), sin(ang));
		for (int i = 0;i<sz;i+=len){
			cd w(1,0);
			for (int j=0;j<i/2;j++){
				cd u = A[i+j], v = w * A[i+j+len/2];
				A[i+j] = u + v;
				A[i+j+len/2] = u - v;
				w *= d;
			}
		}
	}

	for (int i=0;i<sz && inv;i++) A[i] /= sz;
}


vector<int> mult(vector<int> A, vector<int> B){
	int sz = A.size() * 2;
	vector<cd> X,Y,Z;
	X.resize(sz); Y.resize(sz),Z.resize(sz);
	for (int i=0;i<A.size();i++) X[i] = (A[i], 0);
	for (int i=0;i<B.size();i++) Y[i] = (B[i], 0);


	FFT(X, 0); FFT(Y, 0);
	for (int i=0;i<Z.size();i++) Z[i] = X[i] * Y[i];
	FFT(Z, 1);

	vector<int> C;
	C.resize(A.size() + B.size() - 1);
	for (int i=0;i<C.size();i++){
		C[i] = Z[i].real() + 0.5;
	}

	return C;
}


int main(){
    ios::sync_with_stdio(false);

    return 0;
}