Basic FFT

#include <bits/stdc++.h>
#define endl '\n'

#define int long long
#define double long double

using namespace std;
const int MAXN = (1 << 20);
const double PI = acos(-1);

typedef vector<complex<double>> polynomial;

void print_poly(polynomial poly)
{
    bool f = false;
    for(int i = poly.size() - 1; i >= 0; i--)
        if(f || (int)(poly[i].real() + 0.5) != 0)
        {
            cout << (int)(poly[i].real() + 0.5) << " ";
            f = true;
        }

    if(!f) cout << 0;
    //cout << endl;
}

void print_poly(vector<int> poly)
{
    bool f = false;
    for(int i = poly.size() - 1; i >= 0; i--)
        if(f || poly[i] != 0)
        {
            cout << poly[i] << " ";
            f = true;
        }

    if(!f) cout << 0;
    //cout << endl;
}

void fft(polynomial &a)
{
    int n = a.size();
    if(n == 1) return;

    polynomial a0(n / 2), a1(n / 2);
    for(int i = 0; i < n / 2; i++)
    {
        a0[i] = a[2 * i];
        a1[i] = a[2 * i + 1];
    }

    fft(a0);
    fft(a1);

    double ang = 2.0 * PI / n;
    complex<double> w(1), wn(cos(ang), sin(ang));

    for(int i = 0; i < n / 2; i++)
    {
        a[i] = a0[i] + w * a1[i];
        a[i + n / 2] = a0[i] - w * a1[i];
        w *= wn;
    }
}

void inv_fft(polynomial &a)
{
    int n = a.size();
    if(n == 1) return;

    polynomial a0(n / 2), a1(n / 2);
    for(int i = 0; i < n / 2; i++)
    {
        a0[i] = a[2 * i];
        a1[i] = a[2 * i + 1];
    }

    inv_fft(a0);
    inv_fft(a1);

    double ang = -2.0 * PI / n;
    complex<double> w(1), wn(cos(ang), sin(ang));

    for(int i = 0; i < n / 2; i++)
    {
        a[i] = a0[i] + w * a1[i];
        a[i + n / 2] = a0[i] - w * a1[i];
        a[i] /= 2;
        a[i + n / 2] /= 2;
        w *= wn;
    }
}

polynomial multiply(vector<int> _a, vector<int> _b)
{
    polynomial ret, a(_a.begin(), _a.end()), b(_b.begin(), _b.end());

    int sz = 1;
    while(sz < max(a.size(), b.size()))
        sz <<= 1;
    sz <<= 1;

    a.resize(sz);
    b.resize(sz);
    ret.resize(sz);

    fft(a);
    fft(b);
    for(int i = 0; i < sz; i++)
        ret[i] = a[i] * b[i];

    inv_fft(ret);
    return ret;
}

vector<int> rebase(polynomial poly, int base)
{
    vector<int> ret;
    ret.resize(poly.size());

    int carry = 0;
    for(int i = 0; i < poly.size(); i++)
    {
        ret[i] = ((int)(poly[i].real() + 0.5) + carry) % base;
        carry = ((int)(poly[i].real() + 0.5) + carry) / base;
    }

    while(carry) ret.push_back(carry % 10), carry = carry / 10;
    return ret;
}

bool is_digit(char c)
{
    return c >= '0' && c <= '9';
}

polynomial from_string(string s)
{
    polynomial ret;
    ret.clear();
    for(int i = s.size() - 1; i >= 0; i--)
        if(is_digit(s[i])) ret.push_back(s[i] - '0');

    return ret;
}

void read()
{

}

void solve()
{

}

#undef int
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    while(true)
    {
        read();
        solve();
        cout << flush;
    }
    return 0;
}