Labels Without a Forbidden Digit

Interview

Time limit2sMemory limit128 MB

Summary

Given N and a forbidden digit L, find the N-th smallest positive integer whose decimal digits never contain L.

Level: Medium5 of 10
Topics: Math, Combinatorics, Number theory, Implementation
Solved: No attempts yet

Problem

Minseung wants to assign one positive integer label to each of (N) students, where (1 \le N \le 1,000,000). No label may contain the decimal digit (L), where (0 \le L \le 9).\n\nAmong all positive integers whose decimal representation does not contain (L), take the smallest (N) values as the labels. Find the largest label among them.

Input

The first line contains two integers (N) and (L), separated by a space.

Output

Print the largest label that will be used.

Hint

When (N = 10) and (L = 1), the 10 smallest usable labels are (2, 3, 4, 5, 6, 7, 8, 9, 20, 22). Therefore, the largest label is (22).

Examples1

Example 1
Input
```
10 1
```
Expected output
```
22
```