破坏队形

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

(这可能是本场比赛里唯一的题面无坑点且好做的题了 2333)

水群是青少年喜闻乐见的娱乐活动,在群聊中,经常能看到多条相同且连续的聊天信息,我们称之为「队形」,而往往会有一个人出现,发一条与前面队形不同的消息,这种行为我们称之为「破坏队形」。

现在,给你一段按时间顺序的群聊记录,请你统计最长的队形及其长度,如果最长队形被破坏,还要输出破坏队形的人是谁。

注意:必须有至少 2 条相同且连续的消息,才能看做队形。

Input

输入数据有多组(数据组数不超过 100),到 EOF 结束。

对于每组输入,首先输入 1 行,包含 1 个整数 n (1 <= n <= 100),表示消息条数。

接下来有 n 行,每行包含 2 个以空格隔开的字符串(不含空格且长度不超过 30),分别表示消息的发送者和消息内容。

Output

对于每组数据:

  • 如果聊天中没有出现队形,则输出一行 "None"
  • 如果聊天中出现了队形,且最长队形未被破坏,则输出一行 "s (xn)" (s 表示队形的内容,n 表示队形长度)
  • 如果聊天中出现了队形,且最长队形已被破坏,则输出一行 "s (xn) destroyed by p" (s 表示队形的内容,n 表示队形长度,p 表示破坏队形者的名字)

注意:输出均不包含引号。如果答案有并列,则输出时间最靠前的(输入顺序最先出现的)。

Sample Input

3
QAQ I'mNotFitToDoTarining
cyk I'mNotFitToDoTarining
Johsnows I'mNotFitToDoTarining
2
cyk QAQ'sPower!
QAQ ???
7
ldq yxcWillWin
ljf yxcWillWin
yxc1 ???
ly yxcWillWin
ldq yxcWillWin
ldq yxcWillWin
yxc2 ???
6
xry huaji.jpg
qsz huaji.jpg
lxh WillBeRemoved,PleaseCooperate
lq huaji.png
zhy huaji.png
txc huaji.png

Sample Output

I'mNotFitToDoTarining (x3)
None
yxcWillWin (x3) destroyed by yxc2
huaji.png (x3)

Hint

本题的题号是 3866,这个题号也可以在地址栏中看到。

Source

【SDUT Round #3 - 2017 愚人节专场】by bLue