typedef std::complex<double> cd;

const int LOG = 19;
const int N = 1 << LOG;
const double pi = std::acos(-1);

cd W[N];
int rev[N];

void precalc() {
    int last = 0;
    for (int i = 1; i != N; ++i) {
        if (i == (2 << last))
            last += 1;
        rev[i] = rev[i ^ (1 << last)] | (1 << (LOG - 1 - last));
    }

    for (int i = 0; i != N; ++i)
        W[i] = cd(std::cos(2 * pi * i / N), std::sin(2 * pi * i / N));
}

void fft(vector<cd>& a) {
    for (int i = 0; i != N; ++i)
        if (i < rev[i])
            std::swap(a[i], a[rev[i]]);

    for (int lvl = 0; lvl <= LOG - 1; ++lvl) {
        int len = (1 << lvl); // len + len => 2len
        for (int st = 0; st != N; st += 2 * len)
            for (int i = 0; i != len; ++i) {
                cd first  = a[st + i];
                cd second = a[st + i + len] * W[i << (LOG - (lvl + 1))];

                a[st + i] = first + second;
                a[st + i + len] = first - second;
            }
    }
}

void inv_fft(vector<cd>& a) {
    fft(a);
    for (cd& el: a)
        el /= N;
    std::reverse(a.begin() + 1, a.end());
}