Under construction

Still being built. Things may change

Solving a Cubic Equation

Time limit2sMemory limit128 MB

Summary
Find every distinct real root of each cubic with integer coefficients, printed in ascending order rounded to four decimals.
Level

Medium5 of 10

Topics
Math, Number theory
Solved
No attempts yet

Problem

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

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

AA, BB, CC, and DD are integers between -2,000,000 and 2,000,000, and AA is not 0. Every root is between -1,000,000 and 1,000,000. Two different roots of the same equation differ by more than 10−410^{-4}.

Input

The first line contains the number of test cases NN (0<N<1000 < N < 100). Each of the next NN lines contains the coefficients AA, BB, CC, and DD of one equation, separated by spaces.

Output

For each test case, print every real root of the equation in ascending order on one line. Round each root to four decimal places and put a single space between consecutive roots. Print a repeated root only once. A root that rounds to zero is written 0.0000, with no sign.

No root falls exactly on a rounding boundary at the fifth decimal place, so the rounding direction is never ambiguous.

Examples1

  1. Example 1

    Input
    2
    2 -7 7 -2
    2 0 0 0
    
    Expected output
    0.5000 1.0000 2.0000
    0.0000