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.

제한

힌트