Problema A - Quase Capicuas

A Alice adora curiosidades numéricas e está mesmo interessada em capicuas (ou palíndromos), ou seja, números cujo inverso é igual a ele próprio. Dito de outra forma, são números que ficam iguais quando são lidos da direita para a esquerda ou da esquerda para a direita. Por exemplo, todos os seguintes números são capicuas: 1221, 27872, 4, 909 ou 827343728. Nota que os zeros à esquerda não contam e por isso mesmo um número como 10 não é considerado uma capicua.

Por vezes os números que a Alice encontra são "quase" uma capicua. Formalmente, uma K-capicua é um número tal que se alterarmos um máximo de K dígitos o conseguimos transformar numa capicua. Por exemplo, o número 432 é uma 1-capicua, pois basta alterar um dígito (ex: mudando o 4 para um 2, o número fica 232, que é uma capicua). Nota que esta definição significa que uma 0-capicua é uma capicua "normal" (sem ser necessário mudar nenhum dígito).

A Alice começou a escrever todas as K-capicuas numa folha de papel, por ordem crescente, obtendo uma sequência de números. Por exemplo, para as 0-capicuas, os primeiros 20 elementos da sequência são os seguintes:

1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111

Rapidamente a Alice se cansou, mas ficou curiosa em saber qual será a N-ésima K-capicua. Por exemplo, a 20ª 0-capicua é o número 111, pois é o 20º elemento da sequência ordenada das 0-capicuas. Já a 100ª 0-capicua seria o número 919. Claro que o valor de K influencia a sequência. Por exemplo, a 20ª 1-capicua é o numero 20, pois todos os números com 2 ou menos dígitos são 1-capicuas.

Será que podes ajudar a Alice para que ela não tenha de encher as folhas com números?

O Problema

Dado um número K e um conjunto de P perguntas, cada uma indicando um número inteiro N_i, a tua tarefa é, para cada pergunta, descobrir qual a N_i-ésima K-capicua, ou seja, o número que aparece na posição N_i na sequência ordenada de K-capicuas.

Input

A primeira linha contém dois inteiros K e P, separados por um único espaço, indicando respectivamente o tipo de capicuas e o número de perguntas. Seguem-se P linhas, cada uma contendo um único inteiro N_i indicando qual número de ordem que desejamos saber nessa pergunta.

Output

O output é constituído por P linhas, cada um com um único número R_i, a resposta para a pergunta i, ou seja, qual a N_i-ésima K capicua, tal como atrás descrito.

Restrições

São garantidos os seguintes limites em todos os casos de teste:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 35% dos pontos, acontece sempre que P≤30 e R_i≤100 000.

Para um outro conjunto de casos de teste valendo mais 30% dos pontos, K é sempre igual a zero.

Exemplo de Input 1

0 5
20
100
762
1526
81

Exemplo de Output 1

111
919
66366
527725
727

Explicação do Input/Output 1

A sequência que interessa é a das 0-capicuas. 0 20º número dessa sequência é o 111. O 100º é o 919. O 762º é o 66366. O 1526º é o 527725. Finalmente, o 81º é o 727.

Exemplo de Input 2

1 5
20
100
762
1526
81

Exemplo de Output 2

20
100
762
3776
81