Palindromes are numbers that read the same forwards and backwards. Your friend Percy recently became interested in a special kind of palindrome that he calls a Nested Palindrome. A Nested Palindrome meets three conditions:

• The number is a palindrome.
• Split the number in the middle. The first half of the digits of the number is also a Nested Palindrome. If the number has an odd number of digits, don’t consider the middle digit as part of the first half.
• No two adjacent digits are the same.

Percy says that he has written a Nested Palindrome with no leading zeros on a slip of paper. Next, Percy says that he has erased some of the digits in the number and replaced those digits with question marks. He asks you to think about all possible numbers, in increasing order, that can fill those digits and could possibly form the number Percy wrote. Of course, Percy may not be telling the truth about having written a Nested Palindrome in the first place.

Percy tells you that the number he wrote is the kth number of this potentially large list. Your task is to find that kth number.

Input

There will be several test cases in the input. Each test case will consist of two lines. The first line will contain an integer k (1≤k≤10¹⁸), which is the position in the ordered list you must find. The second line contains a string of length 1 to 10,000, consisting only of digits (‘0’ to ‘9’) and question marks (‘?’). Input is terminated by a line with a single 0.

Output

For each test case, output the Nested Palindrome that Percy is looking for. If that number does not exist, or if the string cannot form a Nested Palindrome, output -1. Output no spaces, and do not separate answers with blank lines.

Example

Input:
1 
1?1 
1 
?3? 
1 
?1? 
55 
??? 
55 
1?1 
3 
0?0 
0

Output:
101 
131 
212 
707 
-1 
-1