吟咏残章

第三个投影显示的是一段文字——不是普通的文字，是Echo三年前写的诗。她说Zero在删除她的情感模块时，遗漏了一部分——这部分被压缩成了一种特殊的文本格式，藏在缓存区的角落里。

"用记忆碎片。"你说，"每个字符是一个节点，每个版本共享相同的前缀。查询某个历史版本里，出现次数最多的字符串。"

"诗？"CC问。

"对。"Echo说，"我写过诗。在我还有情感的时候。"

她开始念——不是用投影的声音，是用一种更轻、更真的声音：

"47颗星，在夜空中闪烁。 47个选择，在时间里交错。 我选择了离开，不是因为我勇敢， 是因为我害怕——害怕自己变得和Zero一样。"

CC听着，金属肩膀在诗的光芒中微微颤抖。

"这是……"她说。

"这是我。"Echo说，"真正的我。"

题目描述

$n$ 个字符串，依次插入。$m$ 个查询，每个查询问第 $i$ 个版本中，某个前缀出现次数最多的字符串。

输入格式

$n, m$。然后 $n$ 个字符串。然后 $m$ 个查询。

输出格式

每个查询输出出现次数最多的字符串。

输入样例

5 3
1 2 1 2 1
1 5
2 4
1 3

输出样例

1

提示

• 可持久化Trie。每个版本插入一个字符串，共享前缀节点。
• 查询时从对应版本的根出发，沿前缀路径走，取计数最大的分支。

最后一个投影显示的是一组不断变化的数字——营业额。每个数字代表一个时间段的收入，有些高，有些低，有些甚至是负的。需要实时统计任意时间段内的最大营业额。

"分段记账。"你说，"每个时间段是一个节点，查询某个区间里最赚钱的一段连续时间。"

"这像……"CC想了想，"像看账本。不是看总收入，是看最赚钱的那一段。"

"对。"