\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()} - мнимую.