## NESPALIN - Nested Palindromes

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 **k**th number of this potentially large list. Your task is to find that **k**th 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^{18}), 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

0Output:101

131

212

707

-1

-1

hide comments

:D:
2019-10-19 19:45:21
This problem is definitively easy enough to have 100+ solutions after 5 years, not 10. Please try it. |

Added by: | Joshua Kirstein |

Date: | 2014-11-01 |

Time limit: | 5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 GOSU |

Resource: | ACM SER 2013 |