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