Discrete Fourier Transform

In this problem, your task is to compute the discrete Fourier transform (DFT) of a polynomial. The DFT is represented as a vector (y = (y_0, y_1, ..., y_n-1)), where each coefficient is determined by the formula:

.

Input

The input begins with a single integer (n) ((1 $\le$ n $\le$ 1000)). The following line contains exactly (n) integers, which are the coefficients (a_k) ((-1000 $\le$ a_k $\le$ 1000)), listed in order from (a_0) to (a_n-1).

Output

The output should consist of exactly (n) lines. Each line (k) should display two numbers: (real(y_k)) and (imag(y_k)), separated by a space. These values must be presented with an absolute or relative error not exceeding (10^-6). Here, (real()) refers to the real part, and (imag()) refers to the imaginary part of the complex number.

Examples