#include <cmath>
#include <complex>
#include <iostream>
#include <vector>
using namespace std;

int const logLimit = 3;
int const limit = 1 << logLimit;

vector <int> rev;

void calcRev () {
    rev = vector <int> (limit, 0);
    for (int i = 0; i < limit; i++)
        for (int k = 0; k < logLimit; k++)
            if (i & (1 << k))
                rev[i] ^= 1 << (logLimit - k - 1);
    for (int i = 0; i < limit; i++)
        cout << "rev[" << i << "] = " << rev[i] << endl;
}

using Num = complex <double>;

double const Pi = acos (-1.0);

vector <Num> z;

void calcZ () {
    z = vector <Num> (limit);
    for (int i = 0; i < limit; i++)
        z[i] = Num (cos (i * 2 * Pi / limit),
                    sin (i * 2 * Pi / limit));
    for (int i = 0; i < limit; i++)
        cout << "z[" << i << "] = " << z[i] << endl;
}

vector <Num> fftSlow (const vector <Num> & a0) {
    vector <Num> res (limit, Num (0));
    for (int i = 0; i < limit; i++)
        for (int j = 0; j < int (a0.size ()); j++)
            res[i] += a0[j] * z[(j * i) % limit];
    return res;
}

vector <Num> fft (const vector <Num> & a0) {
    vector <Num> a = a0;
    for (int i = 0; i < limit; i++)
        if (i < rev[i])
            swap (a[i], a[rev[i]]);
    for (int k = 0, span = 1, step = limit / 2; k < logLimit;
      k++, span *= 2, step /= 2) {
        cout << "k = " << k << ", span = " << span <<
          ", step = " << step << endl;
        for (int i = 0; i < limit; i += 2 * span)
            for (int j = 0; j < span; j++) {
                int u = i + j;
                int v = i + j + span;
                Num x = a[u] + a[v] * z[j * step];
                Num y = a[u] + a[v] * z[j * step + limit / 2];
                cout << "a[" << u << "] = a[" << u <<"] + a[" <<
                  v << "] * z[" << j * step << "]" << endl;
                cout << "a[" << v << "] = a[" << u <<"] + a[" <<
                  v << "] * z[" << j * step + limit / 2 << "]" << endl;
                a[u] = x;
                a[v] = y;
            }
    }
    return a;
}

int main () {
    calcRev ();
    calcZ ();
    vector <Num> a (limit, Num (0));
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        a[i] = Num (x);
    }
    auto res = fft (a);
    cout << "fft result:" << endl;
    for (int i = 0; i < limit; i++)
        cout << res[i] << endl;
    auto res2 = fftSlow (a);
    cout << "fftSlow result:" << endl;
    for (int i = 0; i < limit; i++)
        cout << res2[i] << endl;
    return 0;
}