from math import pi, e, cos, sin
def FFT(array, n, inverse):
if n == 1:
return
theta = (pi*2) / n
if inverse:
Wn = pow(e, (-2*pi*1j)/ n)
else:
Wn = pow(e, (2*pi*1j)/ n)
W = 1
a = [0]* (n/2)
b = [0]* (n/2)
for i in xrange(n):
if (i & 1):
b[i/2] = array[i]
else:
a[i/2] = array[i]
FFT(a, n/2, inverse)
FFT(b, n/2, inverse)
for i in xrange(n/2):
array[i] = a[i] + W*b[i]
array[i+n/2] = a[i] - W*b[i]
W *= Wn
a = [1,1,2,0,0,0,0,0]
b = [1,3,0,0,0,0,0,0]
FFT(a, 8, 0)
FFT(b, 8, 0)
res = []
#print a
#print b
for i in xrange(8):
res.append(a[i]*b[i])
FFT(res, 8, 1)
for i in xrange(8):
res[i] /= 8
for i in res:
print i.real
ZnJvbSBtYXRoIGltcG9ydCBwaSwgZSwgY29zLCBzaW4KCmRlZiBGRlQoYXJyYXksIG4sIGludmVyc2UpOgogICAgaWYgbiA9PSAxOgogICAgICAgIHJldHVybgogICAgdGhldGEgPSAocGkqMikgLyBuCiAgICBpZiBpbnZlcnNlOgogICAgICAgIFduID0gcG93KGUsICgtMipwaSoxaikvIG4pCiAgICBlbHNlOgogICAgICAgIFduID0gcG93KGUsICgyKnBpKjFqKS8gbikKICAgICAgICAKICAgIFcgPSAxCgogICAgYSA9IFswXSogKG4vMikKICAgIGIgPSBbMF0qIChuLzIpCgogICAgZm9yIGkgaW4geHJhbmdlKG4pOgogICAgICAgIGlmIChpICYgMSk6CiAgICAgICAgICAgIGJbaS8yXSA9IGFycmF5W2ldCiAgICAgICAgZWxzZToKICAgICAgICAgICAgYVtpLzJdID0gYXJyYXlbaV0KCiAgICBGRlQoYSwgbi8yLCBpbnZlcnNlKQogICAgRkZUKGIsIG4vMiwgaW52ZXJzZSkKCiAgICBmb3IgaSBpbiB4cmFuZ2Uobi8yKToKICAgICAgICBhcnJheVtpXSA9IGFbaV0gKyBXKmJbaV0KICAgICAgICBhcnJheVtpK24vMl0gPSBhW2ldIC0gVypiW2ldCiAgICAgICAgVyAqPSBXbgogICAgICAgCmEgPSBbMSwxLDIsMCwwLDAsMCwwXQpiID0gWzEsMywwLDAsMCwwLDAsMF0KCkZGVChhLCA4LCAwKQpGRlQoYiwgOCwgMCkKCnJlcyA9IFtdCiNwcmludCBhCiNwcmludCBiCmZvciBpIGluIHhyYW5nZSg4KToKICAgIHJlcy5hcHBlbmQoYVtpXSpiW2ldKQpGRlQocmVzLCA4LCAxKQpmb3IgaSBpbiB4cmFuZ2UoOCk6CiAgICByZXNbaV0gLz0gOAoKZm9yIGkgaW4gcmVzOgogICAgcHJpbnQgaS5yZWFsCg==