FFT

typedef long double ld;
typedef complex<ld> cmpl;

const ld PI = atan2(0, -1);

int rev(int i, int k)
{
    int j = 0;
    for (int l = 0; l < k; l++)
        j += (((i >> l) & 1) << (k - l - 1));
    return j;
}

void fft(vector<cmpl> &a, bool invert)
{
    int n = (int)a.size();
    int k = 0;
    while ((1 << k) < n)
        k++;
    for (int i = 0; i < n; i++)
    {
        int j = rev(i, k);
        if (j < i)
            swap(a[i], a[j]);
    }
    for (int l = 1; l < n; l *= 2)
    {
        ld al = (ld)(invert ? -1 : 1) * PI / (ld)(l);
        cmpl wn = cmpl(cos(al), sin(al));
        for (int i = 0; i < n; i += 2 * l)
        {
            cmpl w = cmpl(1, 0);
            for (int j = 0; j < l; j++)
            {
                cmpl y = a[i + j], z = a[i + j + l] * w;
                a[i + j] = y + z;
                a[i + j + l] = y - z;
                w *= wn;
            }
        }
    }
    if (invert)
    {
        for (int i = 0; i < n; i++)
            a[i] /= (ld)n;
    }
}

const ld eps = 1e-2;

ld Abs(ld x)
{
    if (x < 0)
        return -x;
    return x;
}

vector<ll> mult(vector<ll> a, vector<ll> b)
{
    if (!a.size() || !b.size())
        return vector<ll>(1, 0);
    int k = 1;
    while (k <= a.size() + b.size() + 5)
        k *= 2;
    vector<cmpl> x(k, 0), y(k, 0);
    for (int i = 0; i < a.size(); i++)
        x[i] = a[i];
    for (int i = 0; i < b.size(); i++)
        y[i] = b[i];
    fft(x, 0);
    fft(y, 0);
    for (int i = 0; i < k; i++)
        x[i] *= y[i];
    fft(x, 1);
    vector<ll> c(k);
    for (int i = 0; i < k; i++)
    {
        ld cur = x[i].real();
        ll bst = cur - 5;
        for (ll ch = cur - 5; ch < cur + 5; ch++)
            if (Abs((ld)bst - cur) > Abs((ld)ch - cur))
                bst = ch;
        c[i] = bst;
    }
    while (c.size() > (int)a.size() + (int)b.size() - 1)
        c.pop_back();
    return c;
}