UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3741. 基于位运算的最长公共子序列

Statistics 下载数据

Description

小欣在公园玩时发现有个玩小游戏的地方,小游戏的规则是:有两排标有字符的球,字符属于{ATCG},第1排有N1个球,第2排有N2个球(1<=N1,N2<=50000),在第1排的球中选出1些来和第2排的配对,每配出1对就得1分,已经配对了的就不能再用了。小欣觉得这个游戏太简单了,不就是用个就可以了吗?但他发现规则的最后1行说:配对的连线不能相交,相交的概念就是对于第1排的IJ2个球,它们配对的分别是F[I]F[J],它们相交当且仅当I<J and F[I]>F[J]。这就难倒小欣了,现在请你帮助小欣编程求出最大得分。

Input

1两个数: N1N2

2行:N1个字符

3行:N2个字符

Output

2 2

CT

AG

Sample Input

0

Sample Output

Hint

Source