Niech $X$ będzie ciągiem $(x_1, x_2, \dots, x_n)$. Wówczas nieokresowa funkcja autokorelacji $N_X(s)$ jest zdefiniowana jako:

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

gdzie $s$ jest liczbą całkowitą. Przyjmujemy, że $x_i = 0$ dla $i < 1$ oraz $i > n$.

Rozważmy cztery ciągi $(A, B, C, D)$ o długościach odpowiednio $n, n, n$ oraz $n-1$, których wszystkie elementy należą do zbioru $\{-1, +1\}$. Te cztery ciągi tworzą $TT$-ciąg (ciąg typu Turyna) wtedy i tylko wtedy, gdy:

$$N_A(s) + N_B(s) + 2N_C(s) + 2N_D(s) = 0, \text{ dla każdej liczby całkowitej } s > 0.$$

$TT$-ciągi są bardzo interesujące, ponieważ pozwalają na konstruowanie macierzy Hadamarda, które znajdują zastosowanie w takich dziedzinach jak przetwarzanie sygnałów i teoria kodowania. Na przykład $TT$-ciąg dla $n = 36$ (odnaleziony w 2005 roku) pozwolił po raz pierwszy skonstruować macierz Hadamarda rzędu 428.

Mając dany $TT$-ciąg, w którym brakuje kilku elementów, odtwórz początkowy $TT$-ciąg.

Wejście

Cztery linie zawierają cztery ciągi znaków o długościach $n, n, n$ oraz $n-1$ ($2 \le n \le 36$, $n$ jest parzyste), które kodują ciągi $A, B, C$ oraz $D$. $i$-ty symbol koduje $i$-ty element odpowiedniego ciągu. „-” oznacza $-1$, „+” oznacza $+1$, a „?” oznacza brakujący element. Całkowita liczba brakujących elementów nie przekracza 30.

Gwarantuje się, że dla podanych danych istnieje dokładnie jedno rozwiązanie.

Wyjście

Wypisz cztery ciągi znaków o długościach $n, n, n$ oraz $n-1$ — odtworzony $TT$-ciąg. Zobacz przykłady, aby lepiej zrozumieć format wyjściowy.

Przykład

Wejście 1

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

Wyjście 1

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

Wejście 2

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

Wyjście 2

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