Cho một dãy $X = (x_1, x_2, \dots, x_n)$. Hàm tự tương quan phi tuần hoàn $N_X(s)$ được định nghĩa là:

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

trong đó $s$ là một số nguyên. Ở đây ta giả định $x_i = 0$ với $i < 1$ và $i > n$.

Xét bốn dãy $(A, B, C, D)$ có độ dài lần lượt là $n, n, n$ và $n-1$, với tất cả các phần tử thuộc tập $\{-1, +1\}$. Bốn dãy này tạo thành một $TT$-sequence (dãy kiểu Turyn) khi và chỉ khi:

$$N_A(s) + N_B(s) + 2N_C(s) + 2N_D(s) = 0, \text{ với mọi số nguyên } s > 0.$$

Các $TT$-sequence rất thú vị vì chúng cho phép xây dựng các ma trận Hadamard, vốn có ứng dụng trong các lĩnh vực như xử lý tín hiệu và lý thuyết mã hóa. Ví dụ, một $TT$-sequence với $n = 36$ (được tìm thấy vào năm 2005) đã cho phép xây dựng ma trận Hadamard bậc 428 lần đầu tiên.

Cho một $TT$-sequence bị thiếu một số phần tử, hãy khôi phục lại $TT$-sequence ban đầu.

Dữ liệu vào

Bốn dòng chứa bốn chuỗi có độ dài $n, n, n$ và $n-1$ ($2 \le n \le 36$, $n$ là số chẵn) mã hóa các dãy $A, B, C$ và $D$. Ký tự thứ $i$ mã hóa phần tử thứ $i$ của dãy tương ứng. "-" biểu thị $-1$, "+" biểu thị $+1$, và "?" biểu thị một phần tử bị thiếu. Tổng số phần tử bị thiếu không vượt quá 30.

Đảm bảo rằng với dữ liệu đã cho, luôn tồn tại một lời giải duy nhất.

Dữ liệu ra

In ra bốn chuỗi có độ dài $n, n, n$ và $n-1$ — là $TT$-sequence đã được khôi phục. Xem các ví dụ để hiểu rõ hơn về định dạng đầu ra.

Ví dụ

Ví dụ 1

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

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

Ví dụ 2

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

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