Secret Polynomial

Time limit1sMemory limit128 MB

Summary
Given f(1) and f(f(1)) for an unknown polynomial with non-negative integer coefficients, recover it or report IMPOSSIBLE or AMBIGUOUS.
Level

Medium6 of 10

Topics
Math, Brute force, Implementation
Solved
No attempts yet

Problem

You may have seen IQ-test questions such as: find the next number in the sequence 1, 2, 3, __. Supposedly the intended answer is 1616, because the sequence lists f(1),f(2),f(3),f(4),…f(1), f(2), f(3), f(4), \dots for the polynomial f(x)=2x3−12x2+23x−12f(x) = 2x^3 - 12x^2 + 23x - 12. More generally, given some information about the values of a polynomial, can you recover the polynomial? Here we restrict our attention to polynomials whose coefficients are all non-negative integers.

Input

The first line contains an integer nn (0<n≤100000 < n \le 10000), the number of polynomials to identify. Each of the next nn lines contains two integers, the values f(1)f(1) and f(f(1))f(f(1)), where ff is the polynomial to be found. Each of these values fits within the range of a signed two's-complement 32-bit integer.

Output

For each polynomial, output a single line listing its coefficients separated by spaces. If the polynomial has degree dd, list its d+1d+1 coefficients in descending order of power — starting with the coefficient of xdx^d and ending with the coefficient of x0x^0. If the polynomial is the zero polynomial, output just 00. If no polynomial ff has the requested values of f(1)f(1) and f(f(1))f(f(1)), output a line containing the word IMPOSSIBLE instead. If more than one polynomial ff has the requested values, output a line containing the word AMBIGUOUS instead.

Examples1

  1. Example 1

    Input
    1
    3 5
    
    Expected output
    1 2