// FFT with complex:
// Don’t use for long long values
// Except for some special cases
// Precalc roots of -1
typedef complex<double> base;
const int LEN  = 1<<20; // max length, power of 2
base PW[LEN];           // LEN-th roots of -1
void fft(vector<base>& a, bool invert)
{
    int lg = 0;
    while((1<<lg) < SZ(a)) lg++;
    FOR (i, 0, SZ(a))
    {
        int x=0;
        FOR (j, 0, lg)
            x |= ((i>>j)&1)<<(lg-j-1);
        if(i<x)
            swap(a[i], a[x]);
    }
    for (int len = 2; len <= SZ(a); len *= 2)
    {
        int diff = LEN / len;
        if (invert) diff = LEN - diff;
        for (int i = 0; i < SZ(a); i += len)
        {
            int pos = 0;
            FOR (j, 0, len/2)
            {
                base v = a[i+j];
                base u = a[i+j+len/2] * PW[pos];

                a[i+j] = v + u;
                a[i+j+len/2] = v - u;

                pos += diff;
                if (pos >= LEN) pos -= LEN;
            }
        }
    }
    if (invert)
        FOR (i, 0, SZ(a))
            a[i] /= SZ(a);
}
void initFFT()
{
    double angle = 2 * PI / LEN;
    FOR (i, 0, LEN)
    {
        double ca = angle * i;
        PW[i] = base(cos(ca), sin(ca));
    }
}