Дискретне перетворення Фур`є

У цій задачі вам потрібно здійснити дискретне перетворення Фур'є для многочлену . Нагадаємо, що дискретне перетворення Фур'є - це вектор y = (y_0, y_1, ..., y_{n-1}), коефіцієнти якого обчислюються по формулі:

.

Вхідні дані

У першому рядку записано єдине ціле число n (1 ≤ n ≤ 1000). У другому рядку записано рівно n цілих чисел - коефіцієнти a_{k }(-1000 ≤ a_k ≤ 1000) у порядку від a_0 до a_{n-1}.

Вихідні дані

Вихідні дані повинні містити рівно n рядків. k-ий рядок повинен містити рівно два числа real(y_k) та imag(y_k), відокремлені пропуском і виведені з абсолютною чи відносною похибкою, яка не перевищує 10^{-6}, де real() позначає дійсну частину, а imag() - уявну.

Приклади