23535번 - Broken Sequence 스페셜 저지다국어

Let $X$ be a sequence $(x_1, x_2, \dots , x_n)$. Then the nonperiodic autocorrelation function $N_X(s)$ is: $$N_X(s) = \sum_{i=-\infty}^{\infty} x_i x_{i+s},$$ where $s$ is an integer. Here we assume that $x_i=0$ for $i<1$ and $i>n$.

Consider four sequences $(A,B,C,D)$ of length $n$, $n$, $n$, and $n-1$ correspondingly, all elements of which are from set $\{ -1, +1 \}$. These four sequences form the $TT$-sequence (Turyn-Type sequence) if and only if $$N_A(s) + N_B(s) + 2N_C(s) + 2N_D(s) = 0,\text{ for all integer }s>0.$$

$TT$-sequences are very interesting because they allow building Hadamard matrices which find applications in such fields as signal processing and coding theory. For example, a $TT$-sequence for $n=36$ (which has been found in 2005) allowed to construct a Hadamard matrix of order $428$ for the first time.

Given a $TT$-sequence where several elements are missing, restore the initial $TT$-sequence.

The four lines contain four strings of length $n$, $n$, $n$ and $n-1$ ($2 \le n \le 36$, $n$ is even) which encode sequences $A$, $B$, $C$ and $D$. The $i$-th symbol encodes the $i$-th element of the corresponding sequence. "-" denotes $-1$, "+" denotes $+1$, and "?" denotes a missing element. The total number of the missing elements does not exceed $30$.

It is guaranteed that for the given data a single solution exists.

Output four strings of length $n$, $n$, $n$ and $n-1$ --- the restored $TT$-sequence. See samples for better understanding of output format.