Problem Description

You are given a string $ S $. Let $ S[i:j] $ denote the substring of $ S $ from the $ i $-th character to the $ j $-th character.

A string $ T $ is defined as a good string if it satisfies all of the following conditions:

• $1 \leq |T| \leq |S|$
• There exists exactly one integer $ i $ such that $ S[i:i+|T|-1] = T $

For example, if $ S $ is abcbabc, then cb, abcb, and abcbabc are good strings, but abc and zyx are not.

You are given $ Q $ queries to process. In the $ i $-th query, you are given integers $ L_i $ and $ R_i $ that satisfy $1 \leq L_i \leq R_i \leq |S|$. For each query, output the answer to the following problem:

• Consider two integers $ l $ and $ r $ such that $1 \leq l \leq L_i$ and $R_i \leq r \leq |S|$, and $ S[l:r] $ is a good string. What is the minimum value of $ r-l+1 $?

Input Format

The input is given from the standard input in the following format:

$ S $ $ Q $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $\vdots$ $ L_Q $ $ R_Q $

Output Format

Output $ Q $ lines. The $ i $-th line should contain the answer to the $ i $-th query.

Sample Input and Output

Sample Input #1

abcbabc
5
2 3
2 5
1 7
4 4
6 6

Sample Output #1

3
4
7
2
3

Sample Input #2

yyxxzzyyxx
5
3 3
1 1
10 10
5 5
7 7

Sample Output #2

3
5
5
2
2

Sample Input #3

qprrrrrpprqrrppq
20
7 8
6 8
4 7
7 12
6 7
5 5
6 8
4 6
4 4
2 3
7 11
8 9
6 7
11 12
11 15
5 6
4 5
13 13
9 13
5 7

Sample Output #3

4
4
5
6
4
4
4
5
3
3
5
3
4
2
5
4
4
3
5
4

Notes/Hints

Constraints

• $ S $ consists of lowercase English letters.
• $1 \leq |S| \leq 2 \cdot 10^5$
• $1 \leq Q \leq 2 \cdot 10^5$
• $1 \leq L_i \leq R_i \leq |S|$ for $1 \leq i \leq Q$

Sample Explanation 1

For the first query, if $ l=2 $ and $ r=4 $, then $ r-l+1=3 $, which is the minimum. Note that $ l=2 $ and $ r=3 $ is not possible because bc is not a good string. For the second query, if $ l=2 $ and $ r=5 $, then $ r-l+1=4 $, which is the minimum. For the third query, if $ l=1 $ and $ r=7 $, then $ r-l+1=7 $, which is the minimum. Note that $ S $ itself is always a good string.

Sample Explanation 3

Original idea: Forested

见题面 Input 部分

见题面 Output 部分