Problema A - Trinta e Três

Certamente te recordas da Ana e do Aniceto, os dois amigos que gostam de matemática. Eles estão agora ocupados com o jogo do 33. O desafio consiste em ir escrevendo números (sem repetir) que tenham exactamente duas ocorrências do algarismo 3 (nem mais nem menos):

133 653783 76338 433 3763 993734

A Ana e o Aniceto repararam que os números não estavam a aparecer por nenhuma ordem específica. Decidiram então fazer um jogo onde cada um tinha de dizer o número que vinha a seguir na sequência ordenada de forma crescente de todos os números com duas ocorrências do algarismo 3.

                      Ordem na sequência:  1   2   3   4   5   6   7 
Números com 2 ocorrências do algarismo 3: 33 133 233 303 313 323 330 (...)

As mentes matemáticas dos dois amigos queriam ainda um desafio maior. E em vez de dizerem simplesmente o próximo número, o desafio passou a ser descobrir qual o N-ésimo número da sequência de números com exactamente duas ocorrências do algarismo 3, ou seja, qual o número cuja ordem nessa sequência é N. Por exemplo, se a pergunta fosse qual o 7º número, isto é, o número de ordem 7, a resposta seria 330. Já se a pergunta fosse qual o 5º número, a resposta seria 313.

Com todas estas ideias ainda na cabeça eles pensaram então em generalizar o problema. Dados dois inteiros A e C, eles querem pensar na sequência de números com exactamente C ocorrências do algarismo A. E naturalmente, querem saber, dado um número N, qual o N-ésimo número dessa sequência. Por exemplo, se a sequência for a dos números com uma ocorrência do algarismo 5 temos:

                     Ordem na sequência: 1  2  3  4  5  6  7  8  9
Números com 1 ocorrência do algarismo 5: 5 15 25 35 45 50 51 52 53 (...)

Tens de ajudá-los criando um programa para jogar este jogo!

O Problema

Dados um algarismo A, um número inteiro C e uma sequência de Q números inteiros N_i, a tua tarefa é calcular uma sequência de números S_i tal que N_i é o seu número de ordem na sequência ordenada de números com exactamente C ocorrências do algarismo A.

Input

Na primeira linha do input vêm um algarismo A e um número inteiro C, separados por um espaço, indicando que queremos números com exactamente C ocorrências do algarismo A.

Segue-se uma linha com um único número inteiro Q, indicando a quantidade de casos a considerar.

Seguem-se exactamente Q linhas, cada uma contendo um único número inteiro N_i, indicando que deves calcular o número cuja ordem na sequência de números com C ocorrências do algarismo A é N_i.

Output

O output deve ser constituído exactamente por Q linhas, cada uma delas no formato "N_i: S_i", onde S_i é o N-ésimo número da sequência que estamos a considerar. Estas linhas devem vir pela mesma ordem em que aparecem no input.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 40% dos pontos, acontece sempre que N_i≤100, Q≤100 e S_i≤100 000. Para um conjunto de casos de teste valendo 60% dos pontos, acontece sempre que N_i≤500 000 e S_i≤1 000 000.

Exemplo de Input 1

3 2
7
1
2
3
7
6
5
4

Exemplo de Output 1

1: 33
2: 133
3: 233
7: 330
6: 323
5: 313
4: 303

Exemplo de Input 2

5 1
4
1
3
20
10

Exemplo de Output 2

1: 5
3: 25
20: 115
10: 54