J. Polycarp and Dividend
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp have free time, collection of N decimal digits c1, ... , cN and positive integer A. He wants to find positive integer B, such that A divides B and B contains only digits from collection c1, ... , cN. Each digit from collection can be used any times. It is not required to use all the digits.

Input

The first line contains N — the number of digits in collection, 1 ≤ N ≤ 10. The second line contains N integer numbers ci (0 ≤ ci ≤ 9). Each digit can be there at most one time. The third line contains integer A, 1 ≤ A ≤ 105.

Output

Output B. If you cannot find it, then output -1.

Examples
Input
3
3 5 7
123
Output
5535
Input
1
1
1230
Output
-1