Daniel the monkey was hanging off his favourite branch while watching his favourite anime, when all of a sudden, a potato fell from the sky! Upon examining the potato, he notices distinct digits carved on it.
Daniel wants you to use some non-empty combination of digits from the potato to form a positive integer of length , with no leading zeros. He also tells you that you can use the same digit more than once. Additionally, Daniel doesn't remember if he should read numbers from left to right or right to left, so he tells you to make him an integer that reads the same either way!
In addition, Daniel doesn't like processing large integers, so he'll only accept the smallest possible answer. If it is impossible to satisfy this task, you'll have to tell him, and he will become a very sad monkey.
All are distinct.
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
The first line of input will contain and separated by a single space.
The next line will contain space-separated integers, denoting the digits that you can use to construct the integer.
Output the minimum positive integer of length using some non-empty combination of the digits, or
-1 if there is no valid answer.
Sample Input 1
5 6 3 1 2 5 4 9
Sample Output 1
Explanation for Sample 1
It can be proven that is the smallest valid positive -digit integer that can be formed with the digits .
Sample Input 2
1 1 1
Sample Output 2
Sample Input 3
6 1 0
Sample Output 3