U319191 最长公共前缀
题目背景
你已经会了 SA，请尽情的切掉这道题吧！
题目描述
给定长度为 $n$ 的串 $S$，只有小写字母。
一共 $q$ 次询问，每次给定 $l1, r1, l2, r2$，求 $S[l1: r1], S[l2: r2]$ 的最长公共前缀。
输入格式
无
输出格式
无
说明/提示
$n, q \lt 5e5$，数据有一定梯度。