U552570 最长公共子串

给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其子串 $s[l: r]$（$1 \leq l \leq r \leq n$）为选择 $s[l], s[l+1], \dots, s[r]$, 将其顺次拼接得到的新字符串。 你需要处理 $q$ 次询问： 给定两个子串 $s[l_1:r_1]$ 和 $s[l_2:r_2]$，求出它们的最长公共子串。即若存在 $s[l_3:r_3]=s[l_4:r_4]$，满足 $l_1\leq l_3 \leq r_3 \leq r_1$ 且 $l_2 \leq l_4 \leq r_4 \leq r_2$，你需要输出 $r_3-l_3+1$ 可能的最大值；否则输出 $0$。

无

无

对于 $100\%$ 的数据，$1\leq n,q\leq10^5$，保证 $s$ 仅由小写英文字母构成。 因为出题人懒得卡常，$s$ 保证每一个字符从小写英文字母中均匀随机生成，询问的所有子串保证从 $\frac {n(n+1)} 2$ 种子串里均匀随机生成。