题号：NC213805
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld
题目描述
本题中的定义：
- 字符串是由小写字母组成的序列，用
等大写字母表示；
-
（S 是字符串）表示 S 的长度；
-
（S 是字符串）表示将 S 的第
位字符按序取出，排列成的字符串。
- 两个字符串相同（用
表示），当且仅当他们长度相同且每一位相同。
- 字符串 T 为字符串 S 的子串，当且仅当存在
，使
。
- 字符串 S 是回文的，当且仅当它的逆序等于自身。
给出一个字符串 S，q 次询问，每次询问给出一个字符串 T 和一个区间 [l ,r]，求 S[l,r]（下标从 1 开始）与 T 的最长公共回文子串。
输入描述:
第一行一个字符串 S。
第二行一个正整数 q。接下来 q 行，每行先是两个正整数 l,r，然后一个字符串 T，描述一次询问。对于所有数据，，
，
，
，
。
输出描述:
对于每次询问，输出答案，即所求的最长公共回文子串的长度。