The problem asks you to write code to implement the recursive FFT algorithm and FFT inverse algorithm. Your program should first take an input 0 or 1.

If input is 0, the following input must be accepted and the FFT algorithm must be run. The input will be of the form n, a_0, b_0, a_1, b_1, ..., a_n-1, b_n-1. Here, n denotes the degree bound of the input polynomial, and the pair a_j, b_j will denote the complex number c_j = a_j + ib_j as the coefficient of x^j of the input polynomial. Note that n will be an integer, and a_j, b_j will be floating point numbers.

If the first input is 1, the inverse FFT algorithm must be run. The input that follows is n, y_0, z_0, y_1, z_1, ... y_n-1, z_n-1. The pair y_j, z_j specifies the complex number y_j + iz_j to be A(w^j) for some polynomial A, that is, it is the jth coordinate of a given DFT.

Once the input is specified, your program should compute the FFT or the inverse FFT as requested and present the output in vector form.

Example Input :

0 4 0 0 1.0 0 2.0 0 3.0 0

Example output:

4 6.0 0 -2.0 -2.0 -2.0 0 -2.0 2.0

That is, the DFT of x + 2x^2 + 3x^3 is the vector [6, -2 - 2i, -2, -2 + 2i]

Example Input :

1 4 6.0 0 -2.0 -2.0 -2.0 0 -2.0 2.0

Example output:

4 0 0 1.0 0 2.0 0 3.0 0

That is, the inverse DFT of the vector [6, -2 - 2i, -2, -2 + 2i] is the polynomial x + 2x^2 + 3x^3