Problem K
Treasure Finding

Fred the Frog and his pirate gang have successfully plundered a treasure map from the Pink Swans. However, those darn Pink Swans were smart enough to encode their treasure’s coordinates. On the treasure map, there are a bunch of lines and curves that seem to be going everywhere and randomly. With some lines going diagonally, some lines curving up, and some lines curving down. Looking at this has given Fred a headache. However, Fred’s super-smart and loyal owl crewmate, Owlbert Einstein, has managed to figure out that those random lines are actually curves produced from graphing polynomials. Owlbert also figured out that the roots of these polynomials are the coordinates of the treasure! Owlbert begins to convert these polynomial plots to functions. Since he is busy doing that, he cannot solve them. Because Fred is a frog, he cannot even do basic arithmetic. So Fred has entrusted you, a 10x developer, to write a program to accurately find the roots of these polynomials.

Inputs

The first line of input contains a single integer, $n$ ($1 \leq n \leq 1 \cdot 10^5$), representing the number of polynomial functions on the map. The next $n$ lines each represent a polynomial function and follow this format:

Each line begins with an integer $p$ ($1 \leq p \leq 5$) which denotes the maximum power of the polynomial function. Following $p$, there are $p + 1$ integers representing the coefficients of the polynomial, in order from the constant term to the term with the highest power.

It is guaranteed that all roots will be an integer in the range [-10000, 10000].

It is guaranteed that the coefficients will be in the range [$-1 \cdot 10^{12}$, $1 \cdot 10^{12}$].

For example, for a given line of input: $3$ $1$ $2$ $3$ $4$ represents the polynomial: $1 + 2x + 3x^2 + 4x^3$

Outputs

Display $n$ lines, each line showing any single root of the polynomial function.

2
1 0 3
2 -6 1 1

0
-3

5
1 -5 5 
2 4 -5 1 
3 -6 3 -2 1 
4 2 -4 3 -2 1 
5 0 0 0 0 0 1 

1
4
2
1
0