Restoring Calculation Expressions

Time limit1sMemory limit128 MB

Summary
Insert +, -, or * between digits of a string (length up to 9, no leading zero numbers) to produce all expressions evaluating to 2000, sorted lexicographically.
Level

Medium6 of 10

Topics
Backtracking, Brute force, String
Solved
No attempts yet

Problem

A teacher wrote arithmetic expressions whose value is 2,000. During printing, every operator disappeared, leaving only one concatenated digit string.

Insert one or more binary operators between digits so that the expression evaluates to 2,000 under the usual precedence rules. The only operators that may be used are +, -, and *.

Each expression must follow these rules.

  1. A multi-digit number may not start with 0. The value zero must be written as the single digit 0.
  2. Every operator must be a binary operator placed between two operands. Unary + or unary - before a number is not allowed.
  3. * is evaluated before + and -; operators with the same precedence are evaluated from left to right.

Write a program that prints every valid expression that can be made from the given digit string and has value 2,000.

Input

The first line contains the digit string with no spaces. Its length is at most 9.

Output

Print one expression per line whose value is 2,000. If there are multiple expressions, print them in lexicographic order as strings.

Examples1

  1. Example 1

    Input
    2100100
    Expected output
    2*100*10+0
2*100*10-0
2100-100