eolymp
bolt
Try our new interface for solving problems
Problems

Unloved digits

Unloved digits

Time limit 1 second
Memory limit 128 MiB

The new head of the organization discovered that his predecessor, for reasons known only to him, for the numbering of the official documents of principle not used, which contain a decimal record some of the figures. And in the years of obstruction were different sets of digits.

The initial numbers in each year, the previous director took a minimal non-negative number that does not contain the rejected them in the current year figures.

For the numbering of each subsequent document, when the next issue contained a number rejected, he just missed the number. And so on until the next number is not subjected to free him from unwanted numbers. For example, if rejected by 8, 7, 9, 5, 1, the first few papers this year were the following numbers: 0, 2, 3, 4, 6, 20, 22, 23, 24, 26, 30, 32, 33, ...

And as a precursor led organization for a long time and have accumulated a fair amount of them numbered documents, the new leader has arisen a need for a program that for a given set of the rejected numbers by ordinal number of the document, reckoned from the ground up, quickly determine the number, which was officially assigned to him.

Input data

The input file contains two non-empty string. The first line of a space are the unloved figure (the total number from one to eight inclusive). The second line is given the serial number of the desired document.

The total number of rejected digits not less than one nor more than 8.

Serial number of the required document is not less than zero and does not exceed one billion.

Output data

The output file contains a single number - the number of the requested document, ie official document number, serial number which is specified in the input file.

Examples

Input example #1
8 7 9 5 1
8
Output example #1
24
Author Теодор Заркуа
Source Зимняя школа, Харьков 2009, контест Теодора Заркуа и его учеников