#include <complex>

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

const int maxlog = 17, maxn = 1 << maxlog;

typedef std::complex<double> num;

num root[maxn];
int rev[maxn];

void fft( const num *a, num *res ) {
	forn(i, maxn)
		res[rev[i]] = a[i];
	for (int k = 1; k < maxn; k *= 2)
		for (int i = 0; i < maxn; i += 2 * k)
			forn(j, k) {
				num tmp = root[k + j] * res[i + j + k];
				res[i + j + k] = res[i + j] - tmp;
				res[i + j] = res[i + j] + tmp;
			}
}

void precalc() {
	forn(i, maxn)
		rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (maxlog - 1));
	for (int k = 1; k < maxn; k *= 2) {
		num tmp(M_PI / k);
		root[k] = {1, 0};
		for (int i = 1; i < k; i++)
			root[k + i] = (i & 1) ? root[(k + i) >> 1] * tmp : root[(k + i) >> 1]; // Way #2
	}
}