Solving cubic equations 2

Find all real roots of a cubic with rational coefficients, printing them rounded to four decimals, using that at least one root is an integer.

Medium7MathBinary searchImplementationNumber theoryInterviewNo attempts yetTime limit2sMemory limit512 MB

Description

Examples2

Problem

Write a program that finds every real root of the cubic equation $Ax^3 + Bx^2 + Cx + D = 0$ .

Every equation in the input has at least one integer root.

The absolute value of $A$ , $B$ , $C$ , and $D$ is at most $2 \times 10^6$ , and $A$ is not zero. Every real root has absolute value at most $10^6$ . $A$ , $B$ , $C$ , and $D$ can carry up to 11 digits after the decimal point. Within one equation, two different roots differ by more than $10^{-9}$ .

Input

The first line contains the number of test cases $N$ ( $0 < N < 100$ ). Each of the next $N$ lines contains the coefficients $A$ , $B$ , $C$ , and $D$ of one equation, separated by spaces.

Output

For each equation, print all of its real roots in ascending order on one line. Separate two roots with a single space and round each root to four digits after the decimal point. Print a multiple root only once. If a root rounds to zero, print 0.0000 and not -0.0000.