Soit $X$ une séquence $(x_1, x_2, \dots, x_n)$. La fonction d'autocorrélation non périodique $N_X(s)$ est définie par :

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

où $s$ est un entier. Ici, nous supposons que $x_i = 0$ pour $i < 1$ et $i > n$.

Considérons quatre séquences $(A, B, C, D)$ de longueurs respectives $n, n, n$ et $n-1$, dont tous les éléments appartiennent à l'ensemble $\{-1, +1\}$. Ces quatre séquences forment une $TT$-séquence (séquence de type Turyn) si et seulement si :

$$N_A(s) + N_B(s) + 2N_C(s) + 2N_D(s) = 0, \text{ pour tout entier } s > 0.$$

Les $TT$-séquences sont très intéressantes car elles permettent de construire des matrices de Hadamard qui trouvent des applications dans des domaines tels que le traitement du signal et la théorie du codage. Par exemple, une $TT$-séquence pour $n = 36$ (découverte en 2005) a permis de construire pour la première fois une matrice de Hadamard d'ordre 428.

Étant donné une $TT$-séquence dont certains éléments sont manquants, restaurez la $TT$-séquence initiale.

Entrée

Les quatre lignes contiennent quatre chaînes de caractères de longueurs $n, n, n$ et $n-1$ ($2 \le n \le 36$, $n$ est pair) qui encodent les séquences $A, B, C$ et $D$. Le $i$-ième symbole encode le $i$-ième élément de la séquence correspondante. « - » désigne $-1$, « + » désigne $+1$, et « ? » désigne un élément manquant. Le nombre total d'éléments manquants n'excède pas 30.

Il est garanti qu'une solution unique existe pour les données fournies.

Sortie

Affichez quatre chaînes de caractères de longueurs $n, n, n$ et $n-1$ correspondant à la $TT$-séquence restaurée. Consultez les exemples pour mieux comprendre le format de sortie.

Exemples

Entrée 1

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

Sortie 1

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

Entrée 2

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

Sortie 2

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