Пусть $X$ — последовательность $(x_1, x_2, \dots, x_n)$. Тогда непериодическая автокорреляционная функция $N_X(s)$ определяется как:

$$N_X(s) = \sum_{i=-\infty}^{\infty} x_i x_{i+s},$$

где $s$ — целое число. Мы предполагаем, что $x_i = 0$ при $i < 1$ и $i > n$.

Рассмотрим четыре последовательности $(A, B, C, D)$ длины $n, n, n$ и $n-1$ соответственно, все элементы которых принадлежат множеству $\{-1, +1\}$. Эти четыре последовательности образуют $TT$-последовательность (последовательность типа Тьюрина) тогда и только тогда, когда

$$N_A(s) + N_B(s) + 2N_C(s) + 2N_D(s) = 0, \text{ для всех целых } s > 0.$$

$TT$-последовательности представляют большой интерес, так как они позволяют строить матрицы Адамара, которые находят применение в таких областях, как обработка сигналов и теория кодирования. Например, $TT$-последовательность для $n = 36$ (найденная в 2005 году) позволила впервые построить матрицу Адамара порядка 428.

Дана $TT$-последовательность, в которой некоторые элементы пропущены. Восстановите исходную $TT$-последовательность.

Входные данные

Четыре строки содержат четыре строки длины $n, n, n$ и $n-1$ ($2 \le n \le 36$, $n$ — четное), которые кодируют последовательности $A, B, C$ и $D$. $i$-й символ кодирует $i$-й элемент соответствующей последовательности. «-» обозначает $-1$, «+» обозначает $+1$, а «?» обозначает пропущенный элемент. Общее количество пропущенных элементов не превышает 30.

Гарантируется, что для данных входных данных существует единственное решение.

Выходные данные

Выведите четыре строки длины $n, n, n$ и $n-1$ — восстановленную $TT$-последовательность. Обратитесь к примерам для лучшего понимания формата вывода.

Примеры

Входные данные 1

++-+-?-+
+----?-+
+--++?+-
+++-+?-

Выходные данные 1

++-+-+-+
+------+
+--++++-
+++-++-

Входные данные 2

+++----++-+-+?-?--++++-++-++++----+-
+-+++++?-+-+--+--++--?+++-++++---++-
+-+++++-+--?+++-+?+-++--+++-+--+-?-+
+++-+?----++--+-+++?-+-+-+++-+?++-+

Выходные данные 2

+++----++-+-+-----++++-++-++++----+-
+-+++++--+-+--+--++--++++-++++---++-
+-+++++-+--++++-+++-++--+++-+--+---+
+++-+-----++--+-+++--+-+-+++-++++-+