TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

50.0% (6/12)

Submission's AC Ratio

25.3% (19/75)

Description

一陣炫目的閃光。(詳情請見Problem C)
你,妹可,因為不願意面對實驗結果而手踐真的把能量棒丟進反應爐裡,和小蘿莉,夏梨,想要阻止你卻被你害的跌坐在地。
因為這陣爆炸所產生的「萌」衝擊,你們的記憶片段逐漸浮現在腦中。

那是497年前的一個和平下午,2015年3月18日,硬佛石帝國駐美利堅合眾國宣傳大使妹可、也是「萌」燃料電池的研究者,身兼美宣和學術研究的你,與你的助手,實體化AI夏梨,在硬佛大樓地下2217層,準備將你的工作交給新上任的研究員。
但是,你一個不注意,誤傳了一個表情符號,引發了世界大戰,間接導致「萌」極度不穩定,終於引發了「萌爆」,半個地球上的萌元素順間以 e=mc2 的方式轉換成能量,一瞬間就讓硬佛帝國失去了所有的「萌」,變成了廢墟。在爆炸發生前幾分鐘,你的助手,夏梨,把你推入了「萌」力場保護的冷凍艙中......。

「夏梨...妳!」
「夏梨已經壞掉了呦...現在...只是靠著剩下的能量...。」
「什麼!...但是...可是...橘子...」
「我只是...想讓妹可喔膩醬可以恢復記意喔!因為所有關於『萌』的記憶都不見了啊...現在...我的時間也差不多到了...」
「不!夏梨!」
「...喔膩醬...夏梨會盡全力...保護喔膩醬的...,就算...壞掉也沒關係,所以...不要管夏梨了...」
「不!...怎麼辦...」

你看著懷中那逐漸冷卻的身體,忍受著爐心熔解帶來的高熱,你驚人的推理(DP)能力也無能為力了,你只能眼睜睜的再一次失去夏梨......你本來是這麼想的,但是好死不死你驚人的推理(DP)能力又發現,逐漸失去意識的夏梨,是因為其腦中的記憶片段,與自己的記憶片段有違和重疊,導致於「萌」能量不穩定(簡單說就是妹可是魯蛇不可能發生這種這麼帥氣又溫拿的事),只要將妹可和夏梨記憶中最長的違和重疊鍊找出來再加以消除,就可以整救眼前這個夏梨的生命了,你毅然決然的決定冒著被「γ萌」射線奪去性命的風險,坐上了一旁的實驗儀器上,因為已經沒有時間寫程式了,你準備直接在你腦中DP。

「死掉也好壞掉也好,沒有夏梨的世界,留著有什麼意思!!!」妹可發出了溫拿的吶喊。

對了忘了說所謂的最長的違和重疊鍊,如果我們把記憶當做一個很長的字串,從裡面任意取幾個字按照原本的順序排列,叫做子序列,從兩個字串裡找出一樣的子序列就是一條違和重疊鍊,你一定要找出最長的喔!如果一樣長,那就是字典序最小的喔!

『所以說,我是蘿莉控囉?可是我明明比較喜歡傲嬌。夏梨到底是誰的興趣呢?喔對了還有,表情符號的事好像是真的。』---妹可。

Input Format

由於你的腦容量有限,你把你和夏梨的記憶分成了數塊。
輸入的第一行有一個正整數 T ( T ≤ 10 ),表示接下來有幾組破碎的記憶片段。
每組記憶片段有兩行,第1行是妹可的記憶,第2行是夏梨的記憶。
每一段記憶長得就像一段不超過 N 個字元的字串,而且字串不包含空白字元。

對於33%的記憶,由於反應爐核心冷卻水尚未外洩,滿足 夏梨的記憶 ∩ 妹可的記憶 = ∅。
對於66%的記憶,由於「αβ萌」射線溢出但是「γ萌」射線尚未外洩,滿足 不會出現複數的最長違和重疊鍊。
對於100%的記憶,由於 妹可好想CP但是被已讀導致 世界毀滅了,滿足 N≤1000,以上限制都不再適用。

Output Format

對於每組破碎的記憶片段,請輸出「妹可和夏梨記憶中的最長違和重疊鍊」。
若存在多個「最長違和重疊鍊」,請輸出字典序最小的那段。
若不存在「最長違和重疊鍊」,請輸出 "妹萌えこそ正義なのさ!"。

Sample Input

3
#\$#*^
*(&&*\$#
hfd;iHWjfr8Q0na
WWWjlEMMads[jpa
niconiconi
NICONICONI

Sample Output

\$#
Wja
妹萌えこそ正義なのさ!

Hints

妹萌えこそ正義なのさ!
マグルの世界では,「最長違和重疊鍊」が「最長共通部分列」と呼ばれている。

Problem Source

資訊社 28屆C/C++學術考試 by果茶妹可

Subtasks

For Testdata: 0 ~ 2, Score: 33
For Testdata: 3 ~ 5, Score: 33
For Testdata: 6 ~ 10, Score: 34
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536
5 1000 65536
6 1000 65536
7 1000 65536
8 1000 65536
9 1000 65536
10 1000 65536