U103231 【模板】最长公共前缀

Yazid 对编程的态度精益求精，他固执地认为求两个字符串的最长公共前缀居然是 $O(n)$ 的，这令他十分抓狂。

现在有一个字符串，你要求它的任意两个子串的 $lcp$ (最长公共前缀) 的长度。

第一行一个整数 $n$，表示**询问个数**。 接下来一行一个字符串，为母串 $S$。 接下来 $n$ 行，每行四个整数 $a_x,a_y,b_x,b_y$，分别表示第一个子串在母串中的起始与终止位置，第二个子串在母串中的起始与终止位置。

$n$ 行，每行一个整数，表示两个子串的 $lcp$ 的长度。

#### 样例解释 对于第一个询问，第一个子串为 aba，第二个子串也为 aba， 它们的 $lcp$ 就是 aba，故答案为 $3$。 对于第二个询问，第一个子串为 abab，第二个子串为 ab， 它们的 $lcp$ 是 ab，故答案为 $2$。 ------------ #### 数据范围 对于 $40\%$ 的数据，满足 $n \le 10^4$，$|S| \le 10^4$。 对于 $100\%$ 的数据，满足 $n \le 5 \times 10^5$，$|S| \le 10^6$， 且 $1 \le a_x \le a_y \le |S|$，$1 \le b_x \le b_y \le |S|$。 **母串的位置从 $1$ 开始，同时注意使用较快的 IO 方式。**