Problema G: O Génio da Lâmpada


image aladin

Génio da Lâmpada: 541?

Xico Marado: X-X!
Falhaste! Mas o 4 faz parte do número.

Génio da Lâmpada: 374?

Xico Marado: -7-!
Falhaste outra vez! O 7 faz parte do número e está na posição correta. O 3 e o 4 também fazem parte; só que as posições não estão bem...
Última tentativa.

Como chegamos aqui? É uma longa longa história; mas, como estão com pressa, vamos simplificar. Temos um Génio da Lâmpada e temos o Xico. Sabem qual foi o terceiro desejo do Xico? Imaginem! Virar, ele próprio, Génio da Lâmpada!!!
— Não, não e não! Não posso aceitar!
E o Xico, que gosta de desafios contrapôs:
— Para eu mudar de ideias tens três tentativas para acertar.
— Acertar em quê?, questionou o Génio. E o Xico ripostou:
— Acertar no número em que estou a pensar.

Será que o Génio é capaz?

Tarefa

Escreva um programa que, dada uma sequência constituída pelas tentativas de acerto do Génio da Lâmpada no número pensado pelo Xico e pelo feedback do Xico a essas tentativas, indique, tendo em consideração o feedback, se se pode determinar o número pensado pelo Xico ou se não há certezas sobre qual esse número seja. O número é uma sequência de D algarismos, que pode começar por 0 (zero), assim como cada tentativa.

Input

A primeira linha do input contém dois inteiros D e T, que representam, respetivamente, o número de dígitos do número N pensado pelo Xico e o número de tentativas dadas ao Génio para adivinhar esse número. Seguem-se T pares de linhas em que a primeira de cada par contém um inteiro com D algarismos, que representa a tentativa do Génio, e a segunda contém o feedback do Xico.

O feedback é uma sequência com D caracteres. Se a posição P da sequência contiver:

  • um dígito, esse dígito é igual ao que está na posição P do número N (logo, um acerto);
  • o carácter X, então o dígito na posição P da tentativa não ocorre em nenhuma posição do número N;
  • o carácter - (sinal menos), então o dígito na posição P da tentativa ocorre no número N, não se encontrando, no entanto, na posição P de N.

Assim, se a tentativa fosse 04402 e o número pensado pelo Xico fosse 04314, o feedback seria 04--X. O dígito 2 não ocorre em nenhuma posição. Para cada um dos dígitos 0 e 4, assinalou-se um acerto e uma posição incorreta. Mas, note que 4 ocorre duas vezes no número e 0 ocorre uma vez apenas.

Restrições

  1≤D≤5 Número de dígitos de N
  1≤T≤10 Número de tentativas de acerto

Output

O output tem uma única linha com:
  • RESPOSTA  N, em que N é o número pensado pelo Xico, se for possível determiná-lo;
  • AINDA NAO SEI, se não for possível determinar o número pensado pelo Xico.

Exemplo 1

Input 

3 2
541
X-X
374
-7-

Output 

RESPOSTA 473

Exemplo 2

Input 

3 2
541
X-X
498
4XX

Output 

AINDA NAO SEI

Exemplo 3

Input 

5 4
84293
X4XX-
34761
-4XX-
54134
X4--4
14304
-43-4

Output 

RESPOSTA 04314

Exemplo 4

Input 

5 5
04402
04--X
89567
XXXXX
04301
043--
04310
0431-
04313
0431-

Output 

RESPOSTA 04314


ToPAS'2023
193.136.122.94