#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
#define complex complex<double>
#define polynomial vector<complex>
const int maxn = 2100005;
const double PI = acos(-1.0);
polynomial va, vb;
int rev[maxn];
void DFT(polynomial &a, bool inv) {
int n = a.size();
for (int i = 0; i < n; ++i) if (rev[i] < i) swap(a[i], a[rev[i]]);
double pi = inv ? -PI : PI;
for (int step = 1; step < n; step <<= 1) {
double theta = pi / step;
for (int k = 0; k < step; ++k) {
complex omega_k = exp(complex(0, theta * k));
for (int ek = k; ek < n; ek += step << 1) {
int ok = ek + step;
complex t = a[ok] * omega_k;
a[ok] = a[ek] - t;
a[ek] += t;
}
}
}
if (inv) for (int i = 0; i < n; ++i) a[i] /= n;
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
int t, bit;
for (t = 2, bit = 1; t < n + m + 2; t <<= 1, ++bit);
rev[0] = 0;
for (int i = 1; i < t; ++i) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
}
va.resize(t, 0);
vb.resize(t, 0);
for (int i = 0; i <= n; ++i) va[i] = a[i];
for (int i = 0; i <= m; ++i) vb[i] = b[i];
DFT(va, false);
DFT(vb, false);
for (int i = 0; i < t; ++i) va[i] *= vb[i];
DFT(va, true);
for (int i = 0; i <= n + m; ++i) c[i] = int(va[i].real() + 0.5);
}