C. Arseniy's Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Arseniy the hamster was too bored in school lessons, so he came up with an interesting problem for himself. Arseniy wants to find the smallest $$$n$$$-digit number $$$x$$$ such that there exist $$$k$$$ $$$n$$$-digit numbers not exceeding $$$x$$$ with the same sum of digits. Help the hamster solve this problem.

An $$$n$$$-digit number is a non-negative integer whose representation in decimal consists of exactly $$$n$$$ digits and does not contain leading zeros.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^{6}$$$).

The second line contains a single integer $$$k$$$ ($$$1 \le k \le 10^{18}$$$).

Output

Output $$$x$$$. If $$$x$$$ does not exist, output "$$$-1$$$" (without quotes).

Scoring

The tests for this problem consist of nine groups. Points for each group are awarded only if all tests of the group, all tests necessary for it, and tests from the statement are passed.

GroupPointsAdditional constraints
112$$$n \le 3$$$, $$$k \le 100$$$–
215$$$n \le 9$$$, $$$k \le 10^9$$$1
311$$$n \le 18$$$1, 2
413$$$n \le 1000$$$1, 2, 3
512$$$k \le 20$$$–
710$$$k \le 10^6$$$5, 6
814$$$k \le 10^9$$$5, 6, 7
930–1–9
Examples
Input
3
18
Output
271
Input
1
1
Output
0
Note

In the first example, the following $$$18$$$ three-digit numbers not exceeding $$$271$$$ with the same sum of digits are suitable: 109, 118, 127, 136, 145, 154, 163, 172, 181, 190, 208, 217, 226, 235, 244, 253, 262, 271.