Nested Palindrome

A palindrome reads the same forward and backward. Kkung likes one special kind of palindrome, which he calls a nested palindrome. A number is a nested palindrome when all three conditions hold.

• The whole number is a palindrome.
• Cut the number in half, and the front half is again a nested palindrome. When the number of digits is odd, drop the single middle digit before cutting. A one-digit number has an empty front half, so it is always a nested palindrome.
• No two adjacent digits are equal.

Kkung wrote down one nested palindrome, and its first digit is not 0. He then covered some of the digits with question marks. Fill every question mark with a single digit and collect every nested palindrome you can make that way. Kkung wants the $k$-th smallest of them. He may have written the number wrong, so it can happen that no filling produces a nested palindrome.

The input holds several test cases, and each test case is two lines.

The first line has an integer $k$ ($1 \le k \le 10^{18}$). The second line has a string of length $1$ to $10000$ that consists only of the digits 0 to 9 and question marks.

The last line of the input is a single 0, and it is not a test case.

For each test case, print the nested palindrome Kkung is looking for on its own line. If fewer than $k$ nested palindromes can be made from the question marks, print -1.