#include <complex>

using namespace std;

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

typedef complex <double> num;

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

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

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

void init()
{
  forn(i, maxn)
    rev[i] = (rev[i / 2] / 2) + ((i % 2) << (maxlog - 1));
  forn(i, maxn)
    root[i] = num(cos(2 * M_PI * i / maxn), sin(2 * M_PI * i / maxn));
}