Given a string $S$ and $q$ queries, each consisting of $l$ and $r$ ($1 \leq l \leq r \leq |S|$), you need to find the number of distinct substrings of $S[l:r]$.
Input
The first line contains a string $S$.
The next line contains an integer $q$.
The next $q$ lines each contain two integers $l$ and $r$, describing a query.
Output
Output $q$ lines, each containing an integer representing the answer.
Examples
Input 1
helloeveryonenationalolympiadininformaticswilltakeplaceinaugustgoodlucktoeveryonebythewaythisisejudgecontestadministrationsystem 5 1 58 18 46 35 57 25 40 55 56
Output 1
1662 420 267 129 3
Input 2
browseprivatelyexplorefreelydefendyourselfagainsttrackingandsurveillancecircumventcensorship 5 1 30 15 45 20 60 30 70 40 80
Output 2
447 476 830 832 832
Input 3
See the provided files.
Subtasks
For all data, $1 \leq |S| \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5$.
- Subtask 1 (5 Points): $|S|, q \leq 50$
- Subtask 2 (20 Points): $q \leq 50$
- Subtask 3 (26 Points): $S$ contains only 'a' and 'b'
- Subtask 4 (23 Points): $|S| \leq 2 \times 10^4, q \leq 4 \times 10^4$
- Subtask 5 (26 Points): No additional constraints.