Alice and Bob communicate via a matrix channel. Alice wants to send a message to Bob. She has a bitstring representing her message and performs a bitwise encoding algorithm: She starts with the identity matrix
and then reads the bitstring starting from the left-most bit. For each -bit she multiplies the matrix from the right with
For each -bit she multiplies the matrix from the right with
Then the result is transmitted.
Now Bob accidentally deleted the software to decrypt a message from Alice. Can you help him to rewrite it?
Consists of two lines, the -th of them with two integers and for all , where
is the matrix containing the encoded message.
The bitstring representing the message consists of at most characters.
Output the decoded bitstring.