B. Is this FFT?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Tortles recently learned about FFT, or the Fast Fourier Transform algorithm, which can be used to multiply two polynomials together in $$$O(NlogN)$$$. He decided to play around with the algorithm for fun.

Tortles started with two polynomials $$$a$$$ and $$$b$$$, and then used FFT to multiply them together, forming a new polynomial $$$c$$$. However, his computer soon crashed, and he lost his edit history, meaning Tortles only knows his new polynomial $$$c$$$. Given $$$c$$$, please help Tortles find any possibility for what $$$a$$$ or $$$b$$$ could have been.

Input

The first line will contain an integer $$$l$$$ ($$$0 \le l \le 10^5$$$) denoting the degree of the polynomial.

The second line will contain $$$l + 1$$$ integers, $$$f_0, f_1, f_2, ..., f_{l}$$$ ($$$-10^5 \le f_i \le 10^5$$$), where $$$f_i$$$ is the coefficient of $$$x^i$$$ in the polynomial $$$c$$$.

Output

On the first line, output the degree $$$n$$$ ($$$0 \le n \le 10^5$$$) of $$$a$$$.

On the second line, output $$$n + 1$$$ integers $$$p_0, p_1, \ldots, p_n$$$ where $$$p_i$$$ is the coefficient of $$$x^i$$$ in $$$a$$$.

On the third line, print the degree $$$m$$$ ($$$0 \le m \le 10^5$$$) of $$$b$$$.

On the fourth line, output $$$m + 1$$$ integers $$$q_0, q_1, \ldots, q_m$$$ where $$$q_i$$$ is the coefficient of $$$x^i$$$ in $$$b$$$.

Example
Input
2
6 5 1
Output
1
3 1
1
2 1
Note

In this sample, $$$c$$$ is equal to $$$x^2 + 5x + 6$$$, which can be factored into $$$(x + 2)(x + 3)$$$.