The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 3:

- Kotlin 1.4.31

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. M-numbers

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFor a given positive integer $$$m$$$, a positive number is called a $$$m$$$-number if the product of its digits is $$$m$$$. For example, the beginning of a series of $$$24$$$-numbers are as follows: $$$38$$$, $$$46$$$, $$$64$$$, $$$83$$$, $$$138$$$, $$$146$$$, $$$164$$$, $$$183$$$, $$$226$$$ ...

You are given a positive integer $$$m$$$ and $$$k$$$. Print $$$k$$$-th among $$$m$$$-numbers if all $$$m$$$-numbers are sorted in ascending order.

Input

A single line of input contains two integers $$$m$$$ and $$$k$$$ ($$$2 \le m \le 10^9$$$, $$$1 \le k \le 10^9$$$).

Output

Print the desired number — $$$k$$$-th among all $$$m$$$-numbers if $$$m$$$-numbers are sorted in ascending order. If the answer does not exist, print -1.

Examples

Input

24 9

Output

226

Input

24 1

Output

38

Input

5040 1000000000

Output

111121111315213227111

Input

2020 2020

Output

-1

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/28/2022 04:52:03 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|