Given positive integer k and the set of digits s. Find the minimum integer, bigger or equal to k, which decimal notation contains the digits from set s only. The decimal notation of a number must not contain two consecutive identical digits.

Input

First line contains the set of valid digits s in increasing order without spaces and repetitions. Second line contains number k (1 ≤ k ≤ 105).

Output

Print one required number. If the number does not exist, print -1.