Message

문제

Aisha and Basma are two friends who correspond with each other. Aisha has a message $MM$, which is a sequence of $SS$ bits (i.e., zeroes or ones), that she would like to send to Basma. Aisha communicates with Basma by sending her packets. A packet is a sequence of $3131$ bits indexed from $00$ to $3030$. Aisha would like to send the message $MM$ to Basma by sending her some number of packets.

Unfortunately, Cleopatra compromised the communication between Aisha and Basma and is able to taint the packets. That is, in each packet Cleopatra can modify bits on exactly $1515$ indices. Specifically, there is an array $CC$ of length $3131$, in which every element is either $00$ or $11$, with the following meaning:

• $C[i]=1C[i]\; =\; 1$ indicates that the bit with index $ii$ can be changed by Cleopatra. We call these indices controlled by Cleopatra.
• $C[i]=0C[i]\; =\; 0$ indicates that bit with index $ii$ cannot be changed by Cleopatra.

The array $CC$ contains precisely $1515$ ones and $1616$ zeroes. While sending the message $MM$, the set of indices controlled by Cleopatra stays the same for all packets. Aisha knows precisely which $1515$ indices are controlled by Cleopatra. Basma only knows that $1515$ indices are controlled by Cleopatra, but she does not know which indices.

Let $AA$ be a packet that Aisha decides to send (which we call the original packet). Let $BB$ be the packet that is received by Basma (which we call the tainted packet). For each $ii$, such that 0 &le; i < 31:

• if Cleopatra does not control the bit with index $ii$ ($C[i]=0C[i]\; =\; 0$), Basma receives bit $ii$ as sent by Aisha ($B[i]=A[i]B[i]\; =\; A[i]$),
• otherwise, if Cleopatra controls the bit with index $ii$ ($C[i]=1C[i]\; =\; 1$), the value of $B[i]B[i]$ is decided by Cleopatra.

Immediately after sending each packet, Aisha learns what the corresponding tainted packet is.

After Aisha sends all the packets, Basma receives all the tainted packets in the order they were sent and has to reconstruct the original message $MM$.

Your task is to devise and implement a strategy that would allow Aisha to send the message $MM$ to Basma, so that Basma can recover $MM$ from the tainted packets. Specifically, you should implement two procedures. The first procedure performs the actions of Aisha. It is given a message $MM$ and the array $CC$, and should send some packets to transfer the message to Basma. The second procedure performs the actions of Basma. It is given the tainted packets and should recover the original message $MM$.