这是一道模板题。记字符串下标从 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: 数据范围已修复