Four Operations

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.

Medium5BFSMathBrute forceNo attempts yetTime limit2sMemory limit512 MB

Problem

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

The available operations are:

  1. s = s + s; (output: +)
  2. s = s - s; (output: -)
  3. s = s * s; (output: *)
  4. s = s / s; (output: /) (allowed only when ss is not 0)

Input

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

Output

On the first line, print a way to turn ss into tt 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 ss and tt are equal, print 0. If ss cannot be turned into tt, print -1.

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