// Hello. This is pratiikgoogler here. This code is written in order to find the fast fourier transform of a polynomial.
// Special thanks to Cormen and Emaxx for elaborating the code and making life easy for me. hope this helps everyone.
#include<iostream>
#include<complex>
#include<vector>
#include<cmath>
#define PI acos(-1)
using namespace std;
void fft(vector<complex<double> >a,bool show ){ // we take the complex vector although the coefficient are passed as integers but we cannot be sure that the recursive calls would take just integers. Just to be on the saf side, we have taken complex data type.
    int n = a.size();
    if(n==1)
        return;
    vector<complex<double> >a1(n/2),a2(n/2);
    for(int i=0;i*2<n;i++){
        a1[i] =  a[2*i]; // As said in the blog, we take coefficients of even powers in one array and those of odd powers in another.
        a2[i] = a[2*i+1];// Done as said earlier.
    }
    fft(a1,0);// We compute the FFT of a1 recursively. Divide and Conquer.
    fft(a2,0);// We compute the FFT of a2 recursively. DAC .
    double angle = 2*PI/n; // initialise varaible to  2pi/n, to help in computing nth roots of unity.
    complex<double> w(1),wn(cos(angle),sin(angle));
    for(int i=0;i*2<n;i++){
        a[i] = a1[i] + w*a2[i];// one value of a[i]
        a[i+n/2] = a1[i] - w*a2[i];// rotate a[i] by 180 degrees and we get a[i+n/2]
    }
    w = w*wn;// we multiply with powers of omega hece this step.
    if(show)
        for(int i=0;i<n;i++)
            cout<<a[i]<<" ";// Display the values of the corresponding values of the fourier transform i.re, the points which satisfies the polynomial.
}
int main(){
    int n;
    cin>>n;
    vector<complex<double> >a;
    while(n--){
        int k;
        cin>>k;
        a.push_back(k);        
    }
    fft(a,1);
}

Ly8gSGVsbG8uIFRoaXMgaXMgcHJhdGlpa2dvb2dsZXIgaGVyZS4gVGhpcyBjb2RlIGlzIHdyaXR0ZW4gaW4gb3JkZXIgdG8gZmluZCB0aGUgZmFzdCBmb3VyaWVyIHRyYW5zZm9ybSBvZiBhIHBvbHlub21pYWwuCi8vIFNwZWNpYWwgdGhhbmtzIHRvIENvcm1lbiBhbmQgRW1heHggZm9yIGVsYWJvcmF0aW5nIHRoZSBjb2RlIGFuZCBtYWtpbmcgbGlmZSBlYXN5IGZvciBtZS4gaG9wZSB0aGlzIGhlbHBzIGV2ZXJ5b25lLgojaW5jbHVkZTxpb3N0cmVhbT4KI2luY2x1ZGU8Y29tcGxleD4KI2luY2x1ZGU8dmVjdG9yPgojaW5jbHVkZTxjbWF0aD4KI2RlZmluZSBQSSBhY29zKC0xKQp1c2luZyBuYW1lc3BhY2Ugc3RkOwp2b2lkIGZmdCh2ZWN0b3I8Y29tcGxleDxkb3VibGU+ID5hLGJvb2wgc2hvdyApeyAvLyB3ZSB0YWtlIHRoZSBjb21wbGV4IHZlY3RvciBhbHRob3VnaCB0aGUgY29lZmZpY2llbnQgYXJlIHBhc3NlZCBhcyBpbnRlZ2VycyBidXQgd2UgY2Fubm90IGJlIHN1cmUgdGhhdCB0aGUgcmVjdXJzaXZlIGNhbGxzIHdvdWxkIHRha2UganVzdCBpbnRlZ2Vycy4gSnVzdCB0byBiZSBvbiB0aGUgc2FmIHNpZGUsIHdlIGhhdmUgdGFrZW4gY29tcGxleCBkYXRhIHR5cGUuCiAgICBpbnQgbiA9IGEuc2l6ZSgpOwogICAgaWYobj09MSkKICAgICAgICByZXR1cm47CiAgICB2ZWN0b3I8Y29tcGxleDxkb3VibGU+ID5hMShuLzIpLGEyKG4vMik7CiAgICBmb3IoaW50IGk9MDtpKjI8bjtpKyspewogICAgICAgIGExW2ldID0gIGFbMippXTsgLy8gQXMgc2FpZCBpbiB0aGUgYmxvZywgd2UgdGFrZSBjb2VmZmljaWVudHMgb2YgZXZlbiBwb3dlcnMgaW4gb25lIGFycmF5IGFuZCB0aG9zZSBvZiBvZGQgcG93ZXJzIGluIGFub3RoZXIuCiAgICAgICAgYTJbaV0gPSBhWzIqaSsxXTsvLyBEb25lIGFzIHNhaWQgZWFybGllci4KICAgIH0KICAgIGZmdChhMSwwKTsvLyBXZSBjb21wdXRlIHRoZSBGRlQgb2YgYTEgcmVjdXJzaXZlbHkuIERpdmlkZSBhbmQgQ29ucXVlci4KICAgIGZmdChhMiwwKTsvLyBXZSBjb21wdXRlIHRoZSBGRlQgb2YgYTIgcmVjdXJzaXZlbHkuIERBQyAuCiAgICBkb3VibGUgYW5nbGUgPSAyKlBJL247IC8vIGluaXRpYWxpc2UgdmFyYWlibGUgdG8gIDJwaS9uLCB0byBoZWxwIGluIGNvbXB1dGluZyBudGggcm9vdHMgb2YgdW5pdHkuCiAgICBjb21wbGV4PGRvdWJsZT4gdygxKSx3bihjb3MoYW5nbGUpLHNpbihhbmdsZSkpOwogICAgZm9yKGludCBpPTA7aSoyPG47aSsrKXsKICAgICAgICBhW2ldID0gYTFbaV0gKyB3KmEyW2ldOy8vIG9uZSB2YWx1ZSBvZiBhW2ldCiAgICAgICAgYVtpK24vMl0gPSBhMVtpXSAtIHcqYTJbaV07Ly8gcm90YXRlIGFbaV0gYnkgMTgwIGRlZ3JlZXMgYW5kIHdlIGdldCBhW2krbi8yXQogICAgfQogICAgdyA9IHcqd247Ly8gd2UgbXVsdGlwbHkgd2l0aCBwb3dlcnMgb2Ygb21lZ2EgaGVjZSB0aGlzIHN0ZXAuCiAgICBpZihzaG93KQogICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICAgICAgICAgIGNvdXQ8PGFbaV08PCIgIjsvLyBEaXNwbGF5IHRoZSB2YWx1ZXMgb2YgdGhlIGNvcnJlc3BvbmRpbmcgdmFsdWVzIG9mIHRoZSBmb3VyaWVyIHRyYW5zZm9ybSBpLnJlLCB0aGUgcG9pbnRzIHdoaWNoIHNhdGlzZmllcyB0aGUgcG9seW5vbWlhbC4KfQppbnQgbWFpbigpewogICAgaW50IG47CiAgICBjaW4+Pm47CiAgICB2ZWN0b3I8Y29tcGxleDxkb3VibGU+ID5hOwogICAgd2hpbGUobi0tKXsKICAgICAgICBpbnQgazsKICAgICAgICBjaW4+Pms7CiAgICAgICAgYS5wdXNoX2JhY2soayk7ICAgICAgICAKICAgIH0KICAgIGZmdChhLDEpOwp9