Under construction

Still being built. Things may change

Room Number

Interview

Time limit1sMemory limit256 MB

Summary
Find natural numbers A and B with A + B = N, no leading zeros, and no digit repeated across both numbers, minimizing A.
Level

Medium6 of 10

Topics
Brute force, Math, Implementation, Backtracking
Solved
No attempts yet

Problem

Taekhee moved into room NN of the Yonsei Building in Yonsei-dong. He wants to put the room number on his door with digit stickers, but the sticker set holds exactly one sticker for each digit from 0 to 9. If the same digit appears twice in the room number, he cannot spell it out.

Instead of spelling NN itself, Taekhee decided to put up two natural numbers AA and BB with A+B=NA + B = N. Every digit used in AA and BB must be different, so each digit from 0 to 9 can appear at most once across the two numbers. The stickers have an unusual shape, so a 6 cannot be turned upside down and used as a 9. Both AA and BB are natural numbers written without leading zeros.

Take the room number 555. The split 123 + 432 fails because 2 and 3 are each used twice, and 99 + 456 fails because 9 is used twice. The split 512 + 43 uses no digit twice, so it works. A room number usually admits several such splits.

The room number is fairly large, so Taekhee cannot find AA and BB quickly. Help him.

Input

The first line contains the room number NN. (1≤N≤1091 \le N \le 10^9)

Output

If no AA and BB satisfy the condition, print -1 on the first line.

Otherwise, among all pairs that satisfy the condition, take the one with the smallest AA and print it in the form A + B, that is, AA, a space, a plus sign, a space, then BB. Since B=N−AB = N - A, exactly one answer follows this rule.

Examples2

  1. Example 1

    Input
    555
    
    Expected output
    6 + 549
    
  2. Example 2

    Input
    2
    
    Expected output
    -1