Sums of 1, 2, 3 (2)

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

Easy3BacktrackingDynamic programmingInterviewNo attempts yetTime limit1sMemory limit512 MB

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
  2. 1+1+2
  3. 1+2+1
  4. 1+3
  5. 2+1+1
  6. 2+2
  7. 3+1

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

Input

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

Output

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