В этой задаче вам требуется провести дискретное преобразование Фурье для многочлена . Напомним, дискретное преобразование Фурье - это вектор 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() - мнимую.