### Нерекурсивное БПФ

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


struct Number {
    double real, imag;
    Number(double a, double b) :
        real(a),
        imag(b) {}
    Number() :
        Number(0, 0) {}
};

Number operator*(const Number a, const Number b) {
    return Number(a.real * b.real - a.imag * b.imag, a.real * b.imag + a.imag * b.real);
}
Number operator+(const Number &a, const Number &b) {
    return Number(a.real + b.real, a.imag + b.imag);
}
Number operator-(const Number &a, const Number &b) {
    return Number(a.real - b.real, a.imag - b.imag);
}
void operator/=(Number &a, int n) {
    a.real /= n;
    a.imag /= n;
}

const int N = 1 << 21;
const double PI = acos(-1);
Number w[N];

void init_fft() {
    w[0] = Number(1, 0);
    w[1] = Number(cos(2 * PI / N), sin(2 * PI / N));
    for (int i = 0; i < N; i += 1024) {
        w[i] = Number(cos(2 * PI * i / N), sin(2 * PI * i / N));
        for (int j = i + 1; j < i + 1024; ++j) {
            w[j] = w[j - 1] * w[1];
        }
    }
}

int rev[N];

void fft_no_rec(Number *a, int k) {
    int n = 1 << k;
    rev[0] = 0;
    for (int i = 1; i < n; ++i) {
        rev[i] = rev[i >> 1] >> 1;
        if (i & 1) {
            rev[i] |= 1 << (k - 1);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i < rev[i]) {
            swap(a[i], a[rev[i]]);
        }
    }
    for (int l = 1; l < n; l *= 2) {
        for (int i = 0; i < n; i += 2 * l) {
            for (int j = 0; j < l; ++j) {
                Number x = a[i + j], y = w[j * (N / (2 * l))] * a[i + j + l];
                a[i + j]     = x + y;
                a[i + j + l] = x - y;
            }
        }
    }
}

Number arr[N];

void fft(Number *a, int k, int type) {
    int n = 1 << k;
    fft_no_rec(a, k);
    if (type == -1) {
        reverse(a + 1, a + n);
        for (int i = 0; i < n; ++i) {
            a[i] /= n;
        }
    }
}

vector<int> mul(vector<int> a, vector<int> b) {
    int k = 0;
    while ((1ULL << k) <= (a.size() + b.size())) {
        ++k;
    }
    a.resize(1 << k);
    b.resize(1 << k);
    for (int i = 0; i < (1 << k); ++i) {
        arr[i].real = a[i];
        arr[i].imag = b[i];
    }
    fft(arr, k, 1);
    for (int i = 0; i < (1 << k); ++i) {
        arr[i] = arr[i] * arr[i];
    }
    fft(arr, k, -1);
    vector<int> res(1 << k);
    for (int i = 0; i < (1 << k); ++i) {
        res[i] = (int)(arr[i].imag / 2 + 0.5);
    }
    while (res.size() && res.back() == 0) {
        res.pop_back();
    }
    return res;
}


int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init_fft();

    return 0;
}