题目描述

$s$ 和 $t$ 是由 A、C、G、T 组成的字符串。我们用 s\[i\] 和 t\[i\] 来分别表示 $s$ 和 $t$ 的第 $i$ 个字符。我们定义以下得分 $S_{sop}$，并通过在适当位置添加空白符号到 $s$ 和 $t$ 中来使其最大化。注意，添加空白符号后的 $s$ 和 $t$ 的长度应相同，$N$ 表示长度。空白符号用 - 来表示。

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

$sim(x,y)$ 是一个用于计算 $x$ 和 $y$ 相似性的函数，下表定义了它的输出。

$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

例如，当 $s$=CTCGGT 和 $t$=CATCC 时，如果在 $s$ 的第一个字符后面添加 -，并在 $t$ 的最后一个字符后面连续添加两个 -，$S_{sop}$ 最大化。

$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$

注意：添加空白符号的 $s$ 和 $t$ 是对齐的，使得许多位置上相同的字符出现在每个字符串的相同位置。

C-TCGGT
CATCC--

我们称此任务为两两对齐，并将其描述为两行字符串。

给定两个字符串，输出它们的两两对齐，并使 $S_{sop}$ 最大化。

约束条件

• $s$ 和 $t$ 是由 A、C、G、T 组成的字符串。
• $10 \leq |s|, |t| \leq 400$（字符串 $x$ 的长度用 $|x|$ 表示）。

---

输入

输入以以下格式从标准输入给出：

$s$ $t$

输出

打印输入字符串的两两对齐，使 $S_{sop}$ 最大化。在 $s$ 和 $t$ 中插入 - 之后，

$s$ 应该打印在第一行，$t$ 应该打印在第二行。如果有多个使 $S_{sop}$ 最大化的对齐方式，则可以打印任意一种。

只有当满足以下条件时，判题系统才能接受用户的输出： - 如果删除 - ，第一行/第二行与输入的第一行/第二行相等。 - 第一行的长度与第二行的长度相等。

---

示例输入 1

AGTTGAATTT
GTCGGACTTT

示例输出 1

AGT-TGAATTT
-GTCGGACTTT