\includegraphics{https://static.e-olymp.com/content/94/9499ac0aa6dda316af271877aef40b08af5638a6.jpg} У цій задачі вам потрібно здійснити дискретне перетворення Фур'є для многочлену . Нагадаємо, що дискретне перетворення Фур'є - це вектор \textbf{y = (y_0, y_1, ..., y_\{n-1\})}, коефіцієнти якого обчислюються по формулі: \includegraphics{https://static.e-olymp.com/content/e4/e4dd00c2ac6fffc3e69c12fe0976ee1393499b50.jpg} . \InputFile У першому рядку записано єдине ціле число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000}). У другому рядку записано рівно \textbf{n} цілих чисел - коефіцієнти \textbf{a}_\{k \}(\textbf{-1000} ≤ \textbf{a}_k ≤ \textbf{1000}) у порядку від \textbf{a_0} до \textbf{a_\{n-1\}}. \OutputFile Вихідні дані повинні містити рівно \textbf{n} рядків. \textbf{k}-ий рядок повинен містити рівно два числа \textbf{real(y_k)} та \textbf{imag(y_k)}, відокремлені пропуском і виведені з абсолютною чи відносною похибкою, яка не перевищує \textbf{10^\{-6\}}, де \textbf{real()} позначає дійсну частину, а \textbf{imag()} - уявну.