Sea $X$ una secuencia $(x_1, x_2, \dots, x_n)$. Entonces, la función de autocorrelación no periódica $N_X(s)$ es:

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

donde $s$ es un número entero. Aquí asumimos que $x_i = 0$ para $i < 1$ e $i > n$.

Consideremos cuatro secuencias $(A, B, C, D)$ de longitudes $n, n, n$ y $n-1$ respectivamente, cuyos elementos pertenecen al conjunto $\{-1, +1\}$. Estas cuatro secuencias forman una $TT$-secuencia (secuencia de tipo Turyn) si y solo si:

$$N_A(s) + N_B(s) + 2N_C(s) + 2N_D(s) = 0, \text{ para todo entero } s > 0.$$

Las $TT$-secuencias son muy interesantes porque permiten construir matrices de Hadamard, las cuales encuentran aplicaciones en campos como el procesamiento de señales y la teoría de códigos. Por ejemplo, una $TT$-secuencia para $n = 36$ (que fue encontrada en 2005) permitió construir una matriz de Hadamard de orden 428 por primera vez.

Dada una $TT$-secuencia donde faltan varios elementos, restaure la $TT$-secuencia inicial.

Entrada

Las cuatro líneas contienen cuatro cadenas de longitud $n, n, n$ y $n-1$ ($2 \le n \le 36$, $n$ es par) que codifican las secuencias $A, B, C$ y $D$. El $i$-ésimo símbolo codifica el $i$-ésimo elemento de la secuencia correspondiente. "-" denota $-1$, "+" denota $+1$, y "?" denota un elemento faltante. El número total de elementos faltantes no excede 30.

Se garantiza que para los datos proporcionados existe una única solución.

Salida

Imprima cuatro cadenas de longitud $n, n, n$ y $n-1$ — la $TT$-secuencia restaurada. Consulte los ejemplos para una mejor comprensión del formato de salida.

Ejemplos

Entrada 1

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

Salida 1

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

Entrada 2

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

Salida 2

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