Матричний шифр#7948
Увійти

Матричний шифр

1 секунда
128 мегабайтів
Складна

Аліса та Боб спілкуються через матричний канал. Аліса хоче надіслати повідомлення Бобу у вигляді бітового рядка, використовуючи алгоритм побітового кодування. Вона починає з одиничної матриці:

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

Аліса зчитує бітовий рядок зліва направо. Для кожного біта , вона множить матрицю справа на:

\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, тобто~A = A \cdot \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}

Для кожного біта , вона множить матрицю справа на:

\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, тобто~A = A \cdot \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}

Після цього результат передається.

Боб випадково видалив програму для розшифровки повідомлення від Аліси. Чи можете ви допомогти йому відновити її?

Вхідні дані

Вхідні дані складаються з двох рядків, кожен з яких містить два числа a_{i_1} і a_{i_2} (0 \le a_{i_1}, a_{i_2} \le 2^{128} - 1) для всіх  (1 \le i \le 2), де

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

це матриця, що містить закодоване повідомлення.

Бітовий рядок, що представляє повідомлення, містить не більше ніж символів.

Вихідні дані

Виведіть декодований бітовий рядок.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading