Problem Statement

$s$ and $t$ are strings consisting of A, C, G, T. We denote $i$-th characters of $s$ and $t$ by s\[i\] and t\[i\], respectively. We define the following score $S_{sop}$ and aim to maximize it by adding blank symbols to $s$ and $t$ at appropriate positions. Note that lengths of $s$ and $t$ after adding blank symbols should be the same, and $N$ denotes the length. A blank symbol is denoted by -.

$S_{sop}$ = $\\sum_{i=1}^{N}$ sim(s\[i\], t\[i\])

$sim(x,y)$ is a function for calculating the similarity of $x$ and $y$, and the following table defines its output.

$x$ ＼ $y$

A

C

G

T

-

A

1

-3

-3

-3

-5

C

-3

1

-3

-3

-5

G

-3

-3

1

-3

-5

T

-3

-3

-3

1

-5

-

-5

-5

-5

-5

-5

For example when $s$=CTCGGT and $t$=CATCC, $S_{sop}$ is maximized if - is added right after the first character of $s$, and is added twice right after the last character of $t$.

$S_{sop}$ = $sim($C, C$)+sim($-,A$)+sim($T,T$)+sim($C,C$)+sim($G,C$)+sim($G,-$)+ sim($T,-$) = 1 + (-5) + 1 + 1 + (-3) + (-5) + (-5) = -15$

Note that $s$ and $t$ with balnk symbols are aligned such that same character appears at same position in each string for many positions.

C-TCGGT
CATCC--

We call this task pairwise alignment and described it as strings in two lines.

Given two strings, output its pairwise alignment such that it maximizes $S_{sop}$.

Constraints

• $s$ and $t$ are strings consisting of A, C, G, T.
• $10 \\leq |s|, |t| \\leq 400$ (length of a string $x$ is denoted by $|x|$.)

---

Input

Input is given from Standard Input in the following format:

$s$ $t$

Output

Print a pairwise alignment of input strings such that $S_{sop}$ is maximized. After inserting - in $s$ and $t$,

$s$ should be printed in the first line, and $t$ should be printed in the second line. If there is more than one alignment that maximizes $S_{sop}$, you can print any one of them.

The judging system can only accept user's output when: - The first line/second line is equal to the first line/second line of the input if - is removed. - The length of the first line is equal to that of the second line.

---

Sample Input 1

AGTTGAATTT
GTCGGACTTT

Sample Output 1

AGT-TGAATTT
-GTCGGACTTT