간섭이 있는 하모닉스

전자기적 수단으로 메시지를 보내면 다른 자연 신호나 인공 신호의 간섭 때문에 전송 내용이 손상되는 등 여러 어려움이 있다.

보통은 받은 메시지를 검증할 수 있도록 추가 정보를 함께 보낸다. 더 견고한 프로토콜은 보낸 메시지의 일부 오류를 정정하기도 한다.

Arthur와 Bruna는 자신들이 개발한 장치에서 새 전송 프로토콜을 시험하고 있다. 비트열인 메시지 $M$을 Arthur가 Bruna에게 보내며, 역시 비트열인 제어 수열 $N$도 함께 보낸다. Arthur는 메시지 $M$을 구성하고 $N$의 비트를 골라서, $M$이 나타내는 정수가 $N$이 나타내는 정수로 나누어떨어지도록 한다.

Bruna가 받은 각 비트에 대해, 비트가 문제없이 전송되었다면 수신 장치에 0 또는 1이 저장된다. 간섭이 있었다면 해당 자리에 * 기호가 저장된다. 전송 결과는 쌍 $(M', N')$에 저장된다.

통신이 끝난 뒤 메시지가 제대로 전송되었다면 Bruna는 원래 메시지 $M$을 해독할 수 있다 ($M = M'$). 문제가 있었더라도 프로토콜에 따라 해독이 가능한 경우가 있다. 잃어버린 비트가 많으면 Bruna는 메시지를 버린다. 하지만 원래 쌍 $(M, N)$에서 잃어버린 비트가 최대 $16$개인 전송이라면, Bruna는 재전송을 요청하지 않고 메시지를 복구하고 싶어 한다. 그녀는 받은 쌍 $(M', N')$이 나타낼 수 있는 메시지 중 하나를 복구하는 데 도움이 필요하다.

예를 들어 Bruna가 $M'=$111*, $N'=$1*을 받았다고 하자. 가능한 전송은 두 가지다.

1. $M=$1111, $N=$11인 경우. 이때 $M$과 $N$은 각각 15와 3을 나타낸다.
2. $M=$1110, $N=$10인 경우. 이때 $M$과 $N$은 각각 14와 2를 나타낸다.

받은 정보로부터 Arthur가 보냈을 수 있는 메시지 $M$을 찾으라. 가능한 메시지가 여럿이면 그중 아무것이나 출력해도 된다.

첫 번째 줄에는 $M'$을 나타내는 문자열이 주어진다. $1 \le |M'| \le 500$이다. 두 번째 줄에는 $N'$을 나타내는 문자열이 주어진다. $1 \le |N'| \le 16$이다. $M'$과 $N'$의 모든 문자는 0, 1, * 중 하나다. 입력 전체에서 * 문자는 최대 16개다. $N'$에는 항상 1인 비트가 하나 이상 있다.

Bruna가 받은 정보와 호환되는 메시지 $M$을 한 줄에 출력한다.