题目描述

本题中的定义：

• 字符串是由小写字母组成的序列，用 $S,T$ 等大写字母表示；
• $|S|$（$S$ 是字符串）表示 $S$ 的长度；
• $S[l,r]$（$S$ 是字符串）表示将 $S$ 的第 $l,l+1,\dots,r$ 位字符按序取出，排列成的字符串。
• 两个字符串相同（用 $=$ 表示），当且仅当他们长度相同且每一位相同。
• 字符串 $T$ 为字符串 $S$ 的子串，当且仅当存在 $1\le l\le r\le |S|$，使 $S[l,r]=T$。
• 字符串 $S$ 是回文的，当且仅当它的逆序等于自身。

给出一个字符串 $S$，$q$ 次询问，每次询问给出一个字符串 $T$ 和一个区间 $[l ,r]$，求 $S[l,r]$（下标从 $1$ 开始）与 $T$ 的最长公共回文子串。

输入格式

第一行一个字符串 $S$。

第二行一个正整数 $q$。

接下来 $q$ 行，每行先是两个正整数 $l,r$，然后一个字符串 $T$，描述一次询问。

输出格式

对于每次询问，输出答案，即所求的最长公共回文子串的长度。

样例

样例输入

abaabaaa
3
1 4 bbaba
3 8 bababbaabaababababaaabaa
2 5 babbbbabaaabbbb

样例输出

3
5
2

样例解释

三个询问的答案串分别为：aba，aabaa，aa。

数据范围

对于所有数据，$1\le |S|\le 2\times 10^5$，$1\le |T|\le 2\times 10^5$，$1\le q\le 10^5$，$\sum |T|\le 10^6$，$1\le l\le r\le |S|$。