Many number

Given a positive integer K and a set of numbers S. Required to find the minimal positive integer divisible by K, in decimal notation that there are only numbers from the set S. Also in the desired number of decimal should not be two consecutive identical digits.

Input

The first line contains a set of allowable numbers of S in ascending order without gaps and without repetition. A set of numbers may be empty. The second line contains the number of K (1 <= K <= 10^5).

Output

Remove one of the required number. If the desired number does not exist, output a –1.

Examples