#include <algorithm>
#include<iostream>
#include <cstdio>
#include <ctime>
#include <vector>
#include <complex>
using namespace std;
#define cd complex<double>
#define vcd vector<cd>
#define si(n) scanf("%d",&n)
#define f(i,a,b) for(int i=a;i<b;i++)
#define pb push_back

vcd fft(const vcd &as) {
  int n = as.size();
  int k = 0;
  while ((1 << k) < n) k++;
  vector<int> rev(n);
  rev[0] = 0;
  int high1 = -1;
  for (int i = 1; i < n; i++) {
    if ((i & (i - 1)) == 0)
      high1++;
    rev[i] = rev[i ^ (1 << high1)];
    rev[i] |= (1 << (k - high1 - 1));
  }

  vcd roots(n);
  for (int i = 0; i < n; i++) {
    double alpha = 2 * M_PI * i / n;
    roots[i] = cd(cos(alpha), sin(alpha));
  }

  vcd cur(n);
  for (int i = 0; i < n; i++)
    cur[i] = as[rev[i]];

  for (int len = 1; len < n; len <<= 1) {
    vcd ncur(n);
    int rstep = roots.size() / (len * 2);
    for (int pdest = 0; pdest < n;) {
      int p1 = pdest;
      for (int i = 0; i < len; i++) {
        cd val = roots[i * rstep] * cur[p1 + len];
        ncur[pdest] = cur[p1] + val;
        ncur[pdest + len] = cur[p1] - val;
        pdest++, p1++;
      }
      pdest += len;
    }
    cur.swap(ncur);
  }
  return cur;
}

vcd fft_rev(const vcd &as) {
  vcd res = fft(as);
  for (int i = 0; i < (int)res.size(); i++) res[i] /= as.size();
  reverse(res.begin() + 1, res.end());
  return res;
}
//the coeffeciets of input polynomial are stored in a vector-> vcd
int power(int num,int n)
{
    if(n==1) return num;
    int p= power(num,n/2);
    p= (p*p);
    if(n%2!=0)
    {
        p=(p*num);
    }
    return p;
}

int main()
{
    //cout<<ceil(log2(5))<<"\n";
    cout<<"Input the degree of polynomials to be multiplied\n";
    int n,a;
    si(n);
    vcd P,Q;
    cout<<"Enter first polynomial coeffecients\n";
    f(i,0,n+1)
    {
        si(a);
        P.pb(cd(a,0));
    }
    cout<<"Enter second polynomial coeffecients\n";
    f(i,0,n+1)
    {
        si(a);
        P.pb(cd(a,0));
    }
    int t;
    t=n*2;
    int p=ceil(log2(t));
    t=power(2,p);
    f(i,n+1,t+1)
    {
        P.pb(0);
        Q.pb(0);
    }
    vcd P1,Q1;
    P1= fft(P);
    Q1= fft(Q);
    vcd E;
    f(i,0,t+1)
    {
        E.pb(P1[i]*Q1[i]);
    }
    vcd Res;
    Res= fft_rev(E);
    cout<<"the final product coeffeciets are: \n";
    f(i,0,t+1)
    {
        cout<<Res[i]<<" ";
    }
    cout<<"\n";
    return 0;
}