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 0-bit she multiplies the matrix A from the right with
For each 1-bit she multiplies the matrix A 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 i-th of them with two integers ai1 and ai2 (0≤ai1,ai2≤2128−1 for all i (1≤i≤2), where
is the matrix containing the encoded message.
The bitstring representing the message consists of at most 120 characters.
Output the decoded bitstring.