Sum of prime numbers#7407

Sum of prime numbers

1 second

128 megabytes

Medium

Represent the given positive integer $n$ as the sum of one or more primes $p_{1} + p_{2} + \dots + p_{k}$ p_1 + p_2 + \ldots + p_k so that the formed expression, if it is viewed as a string, would be lexicographically the smallest.

String should contain only digits from $0$ to $9$ and sign $+$ . Other symbols are not allowed. The numbers, written in the string, should not start with zero. Strings are compared in ASCII encoding. For example, the character $+$ is less than any digit.

Input

One integer $n$ ( $2 \leq n \leq 9 \cdot 1 0^{18}$ 2 \le n \le 9 \cdot 10^{18}).

Output

Print the required string, the length of which is no more than $10000$ characters.

Examples

Example 1

Loading

p_{1} + p_{2} + \dots + p_{k}

2 \leq n \leq 9 \cdot 1 0^{18}