U319191 最长公共前缀

你已经会了 SA，请尽情的切掉这道题吧！

给定长度为 $n$ 的串 $S$，只有小写字母。 一共 $q$ 次询问，每次给定 $l1, r1, l2, r2$，求 $S[l1: r1], S[l2: r2]$ 的最长公共前缀。

第一行两个数 $n, q$。 第二行一个字符串。 然后 $q$ 行，每行四个数字 $l1, r1, l2, r2$。

一共 $q$ 行，表示最长公共前缀的长度。

$n, q \lt 5e5$，数据有一定梯度。