Kelly is drawing pictures with circles. In order to draw a picture, she does the following:
For example, this is the picture she would draw for the sequence “left, right, left”. Circles were drawn in the order red, orange, green, blue. (The blue one is quite tiny, don’t miss it!)
As boys often do, Kevin forgot his compass at home. But he also likes pretty pictures, so he decided that he will do the same with squares (rotated 45 degrees, so that their diagonals are parallel to the coordinate axes). For example, for the sequence “left, right, left” Kevin would draw this:
The “circles-to-squares” function c is defined as the only continuous function on [0, 1] with the following property: For any sequence of directions, if Kelly drew her picture and the last circle touches the segment at xc, and Kevin drew his picture and the last square touches the segment at xs, then let c(xc)=xs.
You will be given a collection of inputs for c. Compute the corresponding outputs.
The first line of the input file contains an integer t ≤ 100 specifying the number of test cases. Each test case is preceded by a blank line and consists of a single line.
Each test specifies the number xc for which you must compute c(xc). Decimal numbers are not exact, so the inputs are specified as roots of polynomials. Each test case has the form “p k”, where p is a polynomial with integer coefficients (see below) and k is a positive integer. Find the k-th smallest distinct real root of p and use that value as xc. It is guaranteed that it exists and lies in [0, 1].
In the easy subproblem K1 each p is linear. (Therefore, every xc is a rational number.)
In the hard subproblem K2 each p is either linear or quadratic.
Additionally, the input will be such that each line of correct output will have fewer than 40,000 characters.
For each test case, output a single line. If the corresponding xs = c(xc) is an algebraic number (i.e., it can be expressed as a root of a polynomial with integer coefficients), output it using the same formatting as in the input. You must output the polynomial with the smallest possible positive degree. If the corresponding xs is transcendental, output the line “
nare integers, except that
a*x^1is written as just
Examples of correctly formatted polynomials include “
1*x^3+0*x^2+0*x-0” and “
7*x^2-47*x+123456”. For more examples see the input files directly.
2 2*x-1 1 3*x-1 1
2*x-1 1 4*x-1 1