Sums of 1, 2, 3 (2)

Interview

Time limit1sMemory limit512 MB

Summary

Find the k-th composition of n using parts 1, 2 and 3 in lexicographic order, or print -1 when it does not exist.

Level: Easy3 of 10
Topics: Backtracking, Dynamic programming
Solved: No attempts yet

Problem

There are 7 ways to write the integer 4 as a sum of 1, 2, and 3. Every sum uses at least one number.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

Sorted in lexicographic order, they come out in this order.

1+1+1+1
1+1+2
1+2+1
1+3
2+1+1
2+2
3+1

Given integers $n$ and $k$ , write a program that finds the expression ranked $k$ -th in lexicographic order among the ways to write $n$ as a sum of 1, 2, and 3.

Input

The first line contains two integers $n$ and $k$ separated by a space. $n$ is a positive integer smaller than 11, and $k$ is a natural number at most $2^{31}-1$ .

Output

Print the expression ranked $k$ -th in lexicographic order among the ways to write $n$ as a sum of 1, 2, and 3. Do not put spaces around the plus signs. If there is no $k$ -th expression, print -1.

Examples4

Example 1
Input
```
4 3
```
Expected output
```
1+2+1
```
Example 2
Input
```
4 5
```
Expected output
```
2+1+1
```
Example 3
Input
```
4 7
```
Expected output
```
3+1
```
Example 4
Input
```
4 8
```
Expected output
```
-1
```