题目描述

X, Y からなる長さ $N$ の文字列 $S,\ T$ が与えられます． 各 $i\ =\ 1,\ 2,\ \dots,\ N$ に関して，$S$ の $i$ 文字目と $T$ の $i$ 文字目を入れ替えるかどうかを自由に選べます． このとき，結果として得られる文字列の組はのべ $2^N$ 通りありますが，そのいずれかの共通部分列（連続とは限らない）となる文字列のうち最長のものを求めてください． ただし，そのような文字列が複数ある場合，そのうち辞書順で最初に現れるものを求めてください．

共通部分列とは 文字列 $S$ の部分列とは，$S$ から $0$ 個以上の文字を削除して，残った文字を元の順で並べて得られる文字列のことをいいます． 文字列 $S,\ T$ の共通部分列とは，$S$ と $T$ のどちらの部分列でもあるような文字列のことをいいます． （出力例 1 の説明も参考にしてください．）

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $S$ $T$

输出格式

入れ替え後の文字列の組の共通部分列としてあり得る最長の文字列のうち，辞書順で最初に現れるものを出力せよ．

题目大意

给定两个长度为 $n$，且仅包含 X 或 Y 的字符串 $S,T$。对于每个整数 $i\in [1,n]$，你都可以选择交换 $S_i,T_i$ 或者不交换。

请你最大化交换完后的最长公共子序列长度，并输出一组合法的最长公共子序列。如果有多种合法答案，请输出 字典序最小的。$n\le 50$。

3
XXX
YYY

XY

1
X
Y

4
XXYX
YYYY

XYY

提示

制約

• $1\ \leq\ N\ \leq\ 50$
• $S,\ T$ はそれぞれ X, Y からなる長さ $N$ の文字列である．

Sample Explanation 1

- どの文字も入れ替えない場合，XXX と YYY の共通部分列は空文字列のみです． - $1$ 文字目だけを入れ替えた場合，YXX と XYY の共通部分列は，空文字列, X, Y です． - $2$ 文字目だけを入れ替えた場合，XYX と YXY の共通部分列は，空文字列, X, Y, XY, YX です． - $3$ 文字目だけを入れ替えた場合，XXY と YYX の共通部分列は，空文字列, X, Y です． $2$ 文字以上の入れ替えは，$S$ と $T$ 自体を入れ替えて考えれば上記のいずれかに該当します． したがって，共通部分列としてあり得る最長の文字列は XY と YX であり，辞書順で最初に現れる XY が答えとなります．

Sample Explanation 2

答えが空文字列となることもあります．

Sample Explanation 3

たとえば $2$ 文字目だけを入れ替えた場合に XYY が共通部分列となります． より長い文字列，あるいは，同じ長さであって辞書順でより早く現れる文字列は，どのように入れ替えたとしても共通部分列にはなり得ないため，これが答えとなります．