FFT

//Luogu3803
#include<cstdio>
#include<cmath>
#include<algorithm>

const double PI = acos(-1.0);
const int DFT = 2;
const int IDFT = -2;

struct Complex {
  Complex(double real = 0, double imag = 0) : real(real), imag(imag) {  }
  double real;
  double imag;
  Complex operator*(const Complex &cmplx) const {
    return (Complex){real * cmplx.real - imag * cmplx.imag,
                     real * cmplx.imag + imag * cmplx.real};
  }
  Complex operator+(const Complex &cmplx) const {
    return (Complex){real + cmplx.real, imag + cmplx.imag};
  }
  Complex operator-(const Complex &cmplx) const {
    return (Complex){real - cmplx.real, imag - cmplx.imag};
  }
};

void FFT(Complex arr[], int limit, int mode) {

  for(int i = 0, j = 0; i < limit; ++i) {
    if(i > j) std::swap(arr[i], arr[j]);
    int bin = limit >> 1;
    while((j ^= bin) < bin) bin >>= 1;
  }

  for(int len = 2; len <= limit; len <<= 1) {
    Complex lenUnitRoot(std::cos(2 * PI / len), sin(mode * PI / len));
    int mid = len >> 1;
    for(int i = 0; i < limit; i += len) {
      Complex nowX(1, 0);
      for(int j = i; j < i + mid; ++j) {
        Complex left = arr[j];
        Complex right = nowX * arr[j + mid];
        arr[j] = left + right;
        arr[j + mid] = left - right;
        nowX = nowX * lenUnitRoot;
      }
    }
  }

  if(mode == IDFT) {
    for(int i = 0; i < limit; ++i) {
      arr[i].real = int(arr[i].real / limit + 0.5);
      arr[i].imag = 0;
    }
  }
  return;
}

int main() {
  int len1, len2;
  scanf("%d%d", &len1, &len2);

  int limit = 1;
  while(limit <= len1 + len2) {
    limit <<= 1;
  }

  Complex *arr1 = new Complex[limit];
  Complex *arr2 = new Complex[limit];
  for(int i = 0; i <= len1; ++i) {
    scanf("%lf", &arr1[i].real);
  }
  for(int i = 0; i <= len2; ++i) {
    scanf("%lf", &arr2[i].real);
  }

  FFT(arr1, limit, DFT);
  FFT(arr2, limit, DFT);

  for(int i = 0; i < limit; ++i) {
    arr1[i] = arr1[i] * arr2[i];
  }

  FFT(arr1, limit, IDFT);

  for(int i = 0; i <= len1 + len2; ++i) {
    printf("%d ", (int)(arr1[i].real));
  }
  return 0;
}