Harmônicos Interferentes

A transmissão de mensagens por meios eletromagnéticos apresenta diversos desafios, como interferência de outros sinais, naturais ou artificiais, que podem corromper uma transmissão. Uma estratégia comum é o envio de informações adicionais que permitam validar uma mensagem recebida. Alguns protocolos mais robustos permitem até mesmo corrigir alguns erros da mensagem enviada.

Arthur e Bruna estão testando um novo protocolo de transmissão em um dispositivo que eles desenvolveram. Uma mensagem $M$ , que é uma sequência de bits, é enviada de Arthur para Bruna, juntamente com uma sequência de controle $N$ , também representada como uma sequência de bits. Ao compor a mensagem $M$ e escolher os bits de $N$ , Arthur se certifica que o inteiro codificado por $M$ seja divisı́vel pelo inteiro representado por $N$ .

Para cada bit recebido por Bruna, caso o bit tenha sido transmitido sem problemas, o valor 0 ou 1 será armazenado no dispositivo receptor. Caso tenha havido alguma interferência, o sı́mbolo * é armazenado no lugar do bit. O resultado da transmissão será armazenado no par $(M′ , N′ )$. Após a comunicação, caso a mensagem tenha sido enviada com sucesso, Bruna consegue decodificar a mensagem $M$ original (pois $M = M′$ ). Caso tenha havido algum problema, por conta da forma como o protocolo funciona, pode ainda ser possı́vel decodificar a mensagem. Caso muitos bits tenham sido perdidos, Bruna simplesmente descarta a mensagem. Mas para transmissões onde no máximo 16 bits do par $(M, N )$ original tenham sido perdidos, Bruna gostaria de tentar recuperar a mensagem, evitando restransmissões. Ela precisa de sua ajuda para recuperar uma das possiveis mensagens codificadas pelo par $(M′ , N′ )$ recebido.

Por exemplo, suponha que Bruna tenha recebido $M′$ =111* e $N′$ =1*. Duas transmissões poderiam ter sido realizadas:

1. $M$ =1111 com $N$ =11. Neste caso, os números 15 e 3 estão representados em $M$ e $N$ , respectivamente.

2. $M$ =1110 com $N$ =10. Neste caso, os números 14 e 2 estão representados em $M$ e $N$ , respectivamente.

Sua tarefa é: dadas as representações das informações recebidas, encontrar uma mensagem $M$ que possa ter sido enviada por Arthur. Caso mais de uma mensagem exista, você pode imprimir qualquer mensagem que possa ter sido transmitida por Arthur.

A primeira linha da entrada conterá uma sequência de caracteres representando $M′$ , com $1 ≤ |M ′| ≤ 500$. A segunda linha da entrada conterá uma sequência de caracteres representando $N′$ , com $1 ≤ |N ′ | ≤ 16$. Todos os caracteres de $N′$ e $M′$ serão 0, 1 ou *. No total, nunca haverá mais de 16 caracteres * na entrada.

Uma única linha deve ser impressa, contendo uma mensagem $M$ , compatı́vel com a informação recebida por Bruna.