← 返回题目列表

Codeforces · 666/E

E. 法医检验

中文机器翻译题面 查看原题

雷伯兰国是贝尔兰的宿敌。最近伯兰当局逮捕了一名雷伯兰间谍,他试图非法将用于煽动宣传的传单带到伯兰。大多数传单包含“绝对不允许的脏话”的子串,甚至可能包含整个单词。

Berland 法律系统使用复杂的算法来确定间谍的罪行。该算法的主要部分是以下过程。

间谍带来的所有 m 张传单的编号从 1 到 m。之后,需要获得以下类型的 q 个查询的答案:“在数字 [l, r] 段中的哪个传单中,绝对不允许的脏话 [pl, pr] 的子字符串出现得更频繁?”。

专家希望您自动化该过程,因为这次传单的文本太长。帮助他!

输入

第一行包含字符串 s (1 ≤ |s| ≤ 5·105) — 绝对不可接受的脏话。字符串 s 仅由小写英文字母组成。

第二行包含唯一的整数m(1≤m≤5·104)——专业知识传单的文本数量。

接下来的 m 行中的每一行都包含唯一的字符串 ti — 第 i 张传单的文本。所有传单文本的长度总和不超过5·104。传单的文字仅由小写英文字母组成。

下一行包含整数 q (1 ≤ q ≤ 5·105) — 专业知识的查询次数。

最后,最后 q 行每行包含四个整数 l、r、pl、pr(1 ≤ l ≤ r ≤ m,1 ≤ pl ≤ pr ≤ |s|),其中 |s|是绝对不可接受的脏话的长度。

输出

打印 q 行。其中第 i 个应该包含两个整数——出现次数最多的文本的数量和字符串 s 的子串 [pl, pr] 出现的次数。如果有多个文本编号,则打印最小的一个。

示例

输入 #1

suffixtree
3
suffixtreesareawesome
cartesiantreeisworsethansegmenttree
nyeeheeheee
2
1 2 1 10
1 3 9 10

输出 #1

1 1
3 4