CF666E.Forensic Examination

The country of Reberland is the archenemy of Berland. Recently the authorities of Berland arrested a Reberlandian spy who tried to bring the leaflets intended for agitational propaganda to Berland illegally . The most leaflets contain substrings of the Absolutely Inadmissible Swearword and maybe even the whole word.

Berland legal system uses the difficult algorithm in order to determine the guilt of the spy. The main part of this algorithm is the following procedure.

All the m leaflets that are brought by the spy are numbered from 1 to m. After that it's needed to get the answer to q queries of the following kind: "In which leaflet in the segment of numbers [l, r] the substring of the Absolutely Inadmissible Swearword [p__l, p__r] occurs more often?".

The expert wants you to automate that procedure because this time texts of leaflets are too long. Help him!

雷贝尔兰国是贝尔兰国的宿敌。近日，贝尔兰当局逮捕了一名雷贝尔兰间谍，此人企图非法将用于煽动性宣传的传单带入贝尔兰。其中大多数传单包含“绝对禁止辱骂词”的子串，甚至可能完整包含该词。

贝尔兰法律体系采用一种复杂的算法来判定该间谍是否有罪。该算法的核心部分是如下过程：

间谍所携带的全部 $m$ 份传单编号为 $1$ 至 $m$。随后需回答 $q$ 个查询，每个查询形如：“在编号区间 $[l,\,r]$ 的传单中，‘绝对禁止辱骂词’的子串 $[p_l,\,p_r]$ 在哪一份传单中出现次数最多？”

专家希望你将该过程自动化，因为本次传单文本过长。请助他一臂之力！

The first line contains the string s (1 ≤ |s| ≤ 5·105) — the Absolutely Inadmissible Swearword. The string s consists of only lowercase English letters.

The second line contains the only integer m (1 ≤ m ≤ 5·104) — the number of texts of leaflets for expertise.

Each of the next m lines contains the only string t__i — the text of the i-th leaflet. The sum of lengths of all leaflet texts doesn't exceed 5·104. The text of the leaflets consists of only lowercase English letters.

The next line contains integer q (1 ≤ q ≤ 5·105) — the number of queries for expertise.

Finally, each of the last q lines contains four integers l, r, p__l, p__r (1 ≤ l ≤ r ≤ m, 1 ≤ p__l ≤ p__r ≤ |s|), where |s| is the length of the Absolutely Inadmissible Swearword.

第一行包含字符串 $s$（$1 \leq |s| \leq 5\cdot10^5$）——即“绝对禁止的辱骂词”。字符串 $s$ 仅由小写英文字母组成。

第二行包含唯一一个整数 $m$（$1 \leq m \leq 5\cdot10^4$）——待审核传单文本的数量。

接下来的 $m$ 行中，每行包含一个字符串 $t_i$ —— 第 $i$ 张传单的文本。所有传单文本长度之和不超过 $5\cdot10^4$。传单文本仅由小写英文字母组成。

下一行包含整数 $q$（$1 \leq q \leq 5\cdot10^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|$ 表示“绝对禁止的辱骂词”的长度。

Print q lines. The i-th of them should contain two integers — the number of the text with the most occurences and the number of occurences of the substring [p__l, p__r] of the string s. If there are several text numbers print the smallest one.

输出 q 行。其中第 i 行应包含两个整数：子串 [p__l, p__r] 在字符串 s 中出现次数最多的文本编号，以及该子串在该文本中的出现次数。若存在多个满足条件的文本编号，则输出最小的那个。