It's My Derivative

Time limit1sMemory limit128 MB

Summary

For each polynomial, print its derivative and the step-by-step evaluation of that derivative at a given x, matching the input's terse notation.

Level: Easy3 of 10
Topics: String, Implementation, Math, Simulation
Solved: No attempts yet

Problem

An unnamed space agency, still mocked for its infamous metric/imperial unit-conversion blunder, vowed never to let that error happen again. Unfortunately, it over-hired struggling college students who are excellent at metric/imperial unit conversion but hopeless at calculus. In fact, nobody at the agency can now remember how to differentiate a polynomial, let alone evaluate that derivative at a given value of $x$ .

So, as any good government agency would, they have decided to outsource the task — to you. And they don't just want the answer: they want you to show every step of the calculation so that they can re-learn the skill.

Input

The first line contains a single integer $n$ , the number of polynomials.

Each of the next $n$ lines contains two things separated by a space:

an integer value of $x$ at which the first derivative of the polynomial is to be evaluated;
the polynomial itself.

Every polynomial is written in terms of $x$ , using single-digit integer coefficients (positive or negative) and non-negative single-digit integer powers of $x$ . A polynomial contains no spaces. Coefficients and powers equal to $1$ (and powers equal to $0$ ) are omitted from the notation, as is any leading "+" sign. The leading term has the highest power, followed by the term with the next-highest power, and so on in descending order.

Output

For each polynomial in the input, output the following lines:

the string "POLYNOMIAL N", where $N$ is $1$ for the first polynomial, $2$ for the second, and so on;
the polynomial, exactly as given in the input;
the first derivative of that polynomial;
the derivative from line 3 with every $x$ replaced by the given value of $x$ in parentheses (for example, if $x$ is $6$ , then "2x^3" becomes "2(6)^3");
the expression from line 4 with each term fully evaluated;
the resulting integer, which equals $f'(x)$ evaluated at the given value of $x$ .

All output follows the same notation as the input: a leading "+" is dropped, later terms are separated by "+" or "-", and coefficients or powers equal to $1$ (and powers equal to $0$ ) are omitted. In lines 3 and 4 the sign between terms follows each term's coefficient; in line 5 each term has been reduced to a single signed integer, so the signs follow those evaluated values. If the derivative has no terms (the polynomial is constant), print "0" for each of lines 3, 4, 5, and 6.

Examples1

Example 1

Input

3
5 2x^7+x^2+3x-9
0 -5x^7+x^3+1
-3 5

Expected output

POLYNOMIAL 1
2x^7+x^2+3x-9
14x^6+2x+3
14(5)^6+2(5)+3
218750+10+3
218763
POLYNOMIAL 2
-5x^7+x^3+1
-35x^6+3x^2
-35(0)^6+3(0)^2
0+0
0
POLYNOMIAL 3
5
0
0
0
0