중첩 팰린드롬

팰린드롬은 앞에서 읽으나 뒤에서 읽으나 똑같은 수다. 꿍은 그중에서도 중첩 팰린드롬이라고 부르는 수에 관심이 있다. 중첩 팰린드롬은 다음 세 조건을 모두 만족한다.

• 수 전체가 팰린드롬이다.
• 수를 반으로 나눴을 때 앞쪽 절반도 중첩 팰린드롬이다. 자리수가 홀수면 정가운데 한 자리를 빼고 나눈다. 한 자리 수는 앞쪽 절반이 비어 있으므로 언제나 중첩 팰린드롬이다.
• 이웃한 두 자리의 숫자는 서로 같으면 안 된다.

꿍은 중첩 팰린드롬을 하나 적었고, 첫 자리는 0이 아니다. 그 다음 몇몇 자리를 물음표로 가렸다. 물음표마다 숫자를 하나씩 채워서 만들 수 있는 중첩 팰린드롬 가운데 $k$번째로 작은 수를 구하자. 꿍이 잘못 적어서 어떻게 채워도 중첩 팰린드롬이 되지 않을 수도 있다.

입력은 여러 개의 테스트 케이스로 이루어지고, 각 테스트 케이스는 두 줄이다.

첫째 줄에 정수 $k$ ($1 \le k \le 10^{18}$)가 주어진다. 둘째 줄에 0부터 9까지의 숫자와 물음표로만 이루어진 길이 $1$ 이상 $10000$ 이하의 문자열이 주어진다.

입력의 마지막 줄에는 0 하나만 주어지며, 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 꿍이 찾는 중첩 팰린드롬을 한 줄에 하나씩 출력한다. 물음표를 채워서 만들 수 있는 중첩 팰린드롬이 $k$개보다 적으면 -1을 출력한다.