这是一道模板题。记字符串下标从 $1$ 开始，定义串 $s$ 的第 $i$ 个前缀为子串 $s[1..i]$，第 $i$ 个后缀为子串 $s[i..n]$。定义 $lcp(i,j)$ 为后缀 $i,j$ 的最长公共前缀，$lcs(i,j)$ 为前缀 $i,j$ 的最长公共后缀。给定 $q$ 组询问，每次给定 $x,y$，求 $lcp(x,y),lcs(x,y)$。

输入一行一个只含小写字母的字符串 $s(2\le |s|\le 10^6)$。

接下来输入一行一个整数 $q(1\le q\le10^5)$。

接下来输入 $q$ 行，每行两个整数 $x,y(1\le x,y\le |s|,x\neq y)$。

输出 $q$ 行，每行两个整数，代表 $lcp(x,y)$ 和 $lcs(x,y)$。

对第一个询问，$lcp(1,5)=lcp(icpcicpc,icpc)=|icpc|=4$，$lcs(1,5)=lcs(i,icpci)=|i|=1$。

LCP: longest common prefix, LCS: longest common suffix

22/10/01: 数据范围已修复