Four Operations

Time limit2sMemory limit512 MB

Summary

Starting from s, apply +, -, *, / (each replacing s with s+s, s-s, s*s, or s/s) to reach t in the fewest steps, ties broken lexicographically.

Level: Medium5 of 10
Topics: BFS, Math, Brute force
Solved: No attempts yet

Problem

You are given an integer $s$ . Write a program that finds the minimum number of operations needed to turn the value of $s$ into $t$ .

The available operations are:

s = s + s; (output: +)
s = s - s; (output: -)
s = s * s; (output: *)
s = s / s; (output: /) (allowed only when $s$ is not 0)

Input

The first line contains two integers $s$ and $t$ separated by a space. ( $1 \le s, t \le 10^9$ )

Output

On the first line, print a way to turn $s$ into $t$ as the string formed by concatenating the output characters of the operations in the order they are applied. Only a way with the minimum number of operations counts as an answer. If $s$ and $t$ are equal, print 0. If $s$ cannot be turned into $t$ , print -1.

If several ways use the minimum number of operations, print the lexicographically smallest one. In ASCII order the operation characters are *, +, -, /.

Examples6

Example 1
Input
```
7 392
```
Expected output
```
+*+
```
Example 2
Input
```
7 256
```
Expected output
```
/+***
```
Example 3
Input
```
4 256
```
Expected output
```
**
```
Example 4
Input
```
7 7
```
Expected output
```
0
```
Example 5
Input
```
7 9
```
Expected output
```
-1
```
Example 6
Input
```
10 1
```
Expected output
```
/
```