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());
}