CF666E Forensic Examination

Reberland 是 Berland 的宿敌国家。最近，Berland 当局逮捕了一名试图将用于煽动宣传的小册子非法带入 Berland 的 Reberland 间谍。这些小册子中的大多数都包含了“绝对禁止的脏话”的子串，甚至可能包含整个词语。 Berland 的法律体系采用了一种复杂的算法来判断该间谍是否有罪。该算法的主要部分如下。 所有被间谍带来的 $m$ 本小册子都按 $1$ 到 $m$ 编号。接下来需要回答 $q$ 个查询，每个查询如下：“在编号区间 $[l, r]$ 的小册子中，字符串 $s$ 的子串 $[p_l, p_r]$ 出现次数最多的是哪本小册子？它出现了多少次？” 现在，鉴于这次的小册子文字内容过长，专家希望你能自动化这个过程。请帮帮他！

第一行包含字符串 $s$（$1 \leq |s| \leq 5 \cdot 10^5$）——“绝对禁止的脏话”。字符串 $s$ 仅由小写英文字母组成。 第二行包含一个整数 $m$（$1 \leq m \leq 5 \cdot 10^4$）——需要鉴定的小册子数。 接下来的 $m$ 行，每行包含一个字符串 $t_i$——第 $i$ 本小册子的文本。所有小册子文本总长度不超过 $5 \cdot 10^4$。小册子文本仅由小写英文字母组成。 下一行包含一个整数 $q$（$1 \leq q \leq 5 \cdot 10^5$）——需要鉴定的查询数。 最后 $q$ 行，每行包含四个整数 $l$、$r$、$p_l$、$p_r$（$1 \leq l \leq r \leq m, 1 \leq p_l \leq p_r \leq |s|$），其中 $|s|$ 是“绝对禁止的脏话”的长度。

输出 $q$ 行，每行包含两个整数，分别代表出现该子串次数最多的小册子的编号（如有多个则输出编号最小者）以及该子串的出现次数。

由 ChatGPT 5 翻译