시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 93 43 40 45.455%

## 문제

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 0-bit she multiplies the matrix $A$ from the right with

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

For each 1-bit she multiplies the matrix $A$ from the right with

$A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \text{ , i.e. } A \leftarrow 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?

## 입력

The input consists of:

• two lines, the $i$-th of them with two integers $a_{i1}$ and $a_{i2}$ (0 ≤ $a_{i1}$, $a_{i2}$ ≤ 2128 − 1 for all 1 ≤ $i$ ≤ 2), where $\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 120 characters.

## 출력

Output the decoded bitstring.

## 예제 입력 1

2 1
3 2


## 예제 출력 1

010


## 예제 입력 2

18 29
13 21


## 예제 출력 2

10010101