행렬 암호

앨리스는 밥에게 보낼 메시지를 비트열로 들고 있고, 그것을 행렬로 인코딩한다. 인코딩은 단위행렬

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

에서 시작한다. 앨리스는 비트열을 가장 왼쪽 비트부터 한 자리씩 읽는다. 읽은 비트가 0이면 $A$의 오른쪽에

$\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$

을 곱한다. 즉 $A \leftarrow A \cdot \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$이다. 읽은 비트가 1이면 $A$의 오른쪽에

$\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$

을 곱한다. 즉 $A \leftarrow A \cdot \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$이다. 마지막 비트까지 읽고 남은 행렬 $A$를 밥에게 전송한다.

밥은 앨리스가 보낸 행렬을 복호화하는 프로그램을 실수로 지웠다. 전송된 행렬이 주어질 때 원래 비트열을 복원하라.

입력은 두 줄이다. $i$번째 줄에 두 정수 $a_{i1}$과 $a_{i2}$가 공백으로 구분되어 주어진다 ($0 \le a_{i1}, a_{i2} \le 2^{128} - 1$, $1 \le i \le 2$). 이때

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

이 인코딩된 메시지 행렬이다.

원래 비트열의 길이는 1 이상 120 이하이고, 입력 행렬은 항상 그런 비트열 하나를 인코딩한 결과다.

복호화한 비트열을 한 줄에 출력한다. 조건을 만족하는 비트열은 유일하다.