Description

A set is defined as follows: $1$ is an element of the set; if $P$ is an element of the set, then $2\times P+1$ and $4\times P+5$ are also elements of the set.

Take the smallest $k$ elements from this set, concatenate them in increasing order to form a multi-digit integer. You are required to delete $m$ digits from this integer so that the remaining number is as large as possible. Write a program to output the integer before deletion and the integer after deletion.

Note: It is guaranteed that not all digits are deleted.

Input Format

A single line with two integers representing $k$ and $m$.

Output Format

Output two lines. The first line is the number before deletion. The second line is the number after deletion.

5 4

137915
95

Hint

Constraints

• For $30\%$ of the testdata, it is guaranteed that $1 \le k, m \le 300$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le k, m \le 3\times 10^4$.

Translated by ChatGPT 5