Harmonics with Interference

Time limit1sMemory limit1024 MB

Summary

Fill the * bits of M' and N' with 0 or 1 so that the binary value of M is divisible by the binary value of N.

Level: Medium6 of 10
Topics: Dynamic programming, Number theory, Brute force
Solved: No attempts yet

Problem

Transmitting messages by electromagnetic means presents several challenges, such as interference from other natural or artificial signals that can corrupt a transmission.

A common strategy is to send additional information so that a received message can be validated. Some more robust protocols can even correct some errors in the sent message.

Arthur and Bruna are testing a new transmission protocol on a device they have developed. A message $M$ , which is a sequence of bits, is sent from Arthur to Bruna, along with a control sequence $N$ , also a sequence of bits. By composing the message $M$ and choosing the bits of $N$ , Arthur ensures that the integer encoded by $M$ is divisible by the integer represented by $N$ .

For each bit received by Bruna, if the bit was transmitted without problems, the value 0 or 1 is stored in the receiving device. If there was any interference, the symbol * is stored in place of the bit. The result of the transmission is stored in the pair $(M', N')$ .

After the communication, if the message was sent successfully, Bruna can decode the original message $M$ (since $M = M'$ ). If there was a problem, the protocol may still allow decoding. If many bits were lost, Bruna discards the message. But for transmissions where at most $16$ bits of the original pair $(M, N)$ were lost, Bruna wants to recover the message without asking for a retransmission. She needs your help to recover one of the possible messages encoded by the received pair $(M', N')$ .

For example, suppose Bruna received $M'=$ 111* and $N'=$ 1*. Two transmissions could have been made.

$M=$ 1111 with $N=$ 11. In this case, $M$ and $N$ represent 15 and 3.
$M=$ 1110 with $N=$ 10. In this case, $M$ and $N$ represent 14 and 2.

Given the received information, find a message $M$ that Arthur could have sent. If more than one message is possible, you may print any of them.

Input

The first line contains the sequence of characters representing $M'$ , with $1 \le |M'| \le 500$ . The second line contains the sequence of characters representing $N'$ , with $1 \le |N'| \le 16$ . Every character in $M'$ and $N'$ is 0, 1, or *. The input contains at most 16 * characters in total. $N'$ always contains at least one bit $1$ .

Output

Print a single line containing a message $M$ that is compatible with the information Bruna received.

Examples2

Example 1
Input
```
111*
1*
```
Expected output
```
1111
```
Example 2
Input
```
101**
11
```
Expected output
```
10101
```