Expression

Here is a puzzle. Can you write a mathematical expression that evaluates to $113$ and uses nothing but common mathematical symbols and four copies of the digit $4$?

One answer is

$113 = \frac{\sqrt{4} + (\sqrt{4} + 4!)\%}{\sqrt{4}\%}$

Here ! is the factorial sign and % is the percent sign, so 11% = 0.11.

Four fours is an arithmetic puzzle whose goal is to produce a given number from four copies of the digit $4$ and common mathematical symbols. Some numbers are easy: $16 = 4 + 4 + 4 + 4$. Others are not, as the expression for $113$ shows. Can you produce $2016$ from four fours?

This problem is a variation of that puzzle. You are given two integers $x$ and $y$, and you have to write an expression whose value is $y$ under these rules.

• The only constant allowed in the expression is the integer $x$.
• The only operations allowed are addition, subtraction, multiplication and division.
• The expression uses at most $28$ operations.
• No intermediate result exceeds $10^{18}$ in absolute value.
• Every division is exact, so the divisor is not zero and the quotient is an integer.

Many expressions can satisfy these rules at once. The output section fixes one of them, and that is the expression you print.

The first line contains an integer $T$, the number of test cases.

Each of the next $T$ lines contains two integers $x$ and $y$ separated by a space.

• $1 \le T \le 212121$
• $0 \le x, y < 1212$

For each test case print one line.

An expression is written in postfix notation as a string over the five characters x, +, -, * and /. It is evaluated with a stack that starts empty, reading the string from left to right.

• x pushes the number $x$ onto the stack.
• + pops two numbers $b$ and $a$ in that order, then pushes $a + b$.
• - pops $b$ and $a$, then pushes $a - b$.
• * pops $b$ and $a$, then pushes $a \times b$.
• / pops $b$ and $a$, then pushes $a / b$.

After the last character the stack must hold exactly one number, and that number is the value of the expression. If an operator is read while the stack holds fewer than two numbers, or the stack does not hold exactly one number at the end, the evaluation fails.

Print the expression that this rule selects.

• If $x = 0$ and $y > 0$, print IMPOSSIBLE.
• If $y = 0$, print xx-.
• Otherwise print $S(y)$ followed by x/.

$S(n)$ is defined for $1 \le n \le 1211$ and is a postfix string whose value is $n \times x$. Let $c(n)$ be the number of x characters in $S(n)$. The base string for $n = 1$ is x, so $c(1) = 1$. Three rules build the other strings.

• Product: if $n = a \times b$ with $2 \le a \le b \le 1211$, concatenate $S(a)$, then $S(b)$, then *x/. The result holds $c(a) + c(b) + 1$ characters x.
• Sum: if $n = a + b$ with $1 \le a \le b \le 1211$, concatenate $S(a)$, then $S(b)$, then +. The result holds $c(a) + c(b)$ characters x.
• Difference: if $n = a - b$ with $1 \le b < a \le 1211$, concatenate $S(a)$, then $S(b)$, then -. The result holds $c(a) + c(b)$ characters x.

$c(n)$ is the smallest number of x characters over every string these rules build for $n$, and $S(n)$ is a string that reaches $c(n)$. When several strings reach it, take a product first, then a sum, then a difference, and inside one kind take the smallest $a$. The two parts of such a string always satisfy $c(a) < c(n)$ and $c(b) < c(n)$, so $S(n)$ is determined for every $n$.

The expression printed this way uses at most $28$ operations.