Məsələlər
Матричный шифр
Матричный шифр
Алиса и Боб общаются через матричный канал. Алиса хочет отправить сообщение Бобу. У нее есть сообщение в виде битовой строки, и она выполняет алгоритм побитового кодирования. Алиса начинает с единичной матрицы.
$$
A = \begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}
$$
Затем Алиса считывает битовую строку, начиная с самого левого бита. Для каждого $0$-бита она умножает матрицу $A$ справа на
$$
\begin{pmatrix}
1 & 0 \\
1 & 1
\end{pmatrix}, i.e.~A = A \cdot
\begin{pmatrix}
1 & 0 \\
1 & 1
\end{pmatrix}
$$
Для каждого $1$-бита она умножает матрицу $A$ справа на
$$
\begin{pmatrix}
1 & 1 \\
0 & 1
\end{pmatrix}, i.e.~A = A \cdot
\begin{pmatrix}
1 & 1 \\
0 & 1
\end{pmatrix}
$$
Затем результат передается.
Боб случайно удалил программу для расшифровки сообщения Алисы. Можете ли Вы помочь ему написать ее заново?
\InputFile
Состоит из двух строк, $i$-ая из них содержит два числа $a_{i_1}$ и $a_{i_2}~(0 \le a_{i_1}, a_{i_2} \le 2^{128} - 1$ для всех $i~(1 \le i \le 2)$, где
$$
A = \begin{pmatrix}
a_{11} & a_{12} \\
a_{21} & a_{22}
\end{pmatrix}
$$
матрица, содержащая закодированное сообщение.
Битовая строка, представляющая сообщение, состоит из не более чем $120$ символов.
\OutputFile
Выведите декодированную битовую строку.
Giriş verilənləri #1
2 1 3 2
Çıxış verilənləri #1
010
Giriş verilənləri #2
18 29 13 21
Çıxış verilənləri #2
10010101