Matrix Cypher#7948
Sign in

Matrix Cypher

1 second
128 megabytes
Hard

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

A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}

and then reads the bitstring starting from the left-most bit. For each -bit she multiplies the matrix from the right with

\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, i.e.~A = A \cdot \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}

For each -bit she multiplies the matrix from the right with

\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, i.e.~A = A \cdot \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}

Then the result is transmitted.

Now Bob accidentally deleted the software to decrypt a message from Alice. Can you help him to rewrite it?

Input

Consists of two lines, the -th of them with two integers a_{i_1} and a_{i_2} (0 \le a_{i_1}, a_{i_2} \le 2^{128} - 1) for all  (1 \le i \le 2), where

A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}

is the matrix containing the encoded message.

The bitstring representing the message consists of at most characters.

Output

Output the decoded bitstring.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading