Automatic Trading

Time limit5sMemory limit128 MB

Summary

Given a string and pairs of positions, for each query find the length of the longest common prefix of the two suffixes starting at those positions.

Level: Hard8 of 10
Topics: String, String matching, Binary search, Hash map
Solved: No attempts yet

Problem

A brokerage firm wants to detect automatic trading. They believe a particular algorithm repeats itself, making the same sequence of trades again at a later time. The firm has identified 26 key stocks that are likely to be traded in concert, and it has encoded a series of trades as a string of letters: the letter identifies the stock, an upper-case letter means a buy, and a lower-case letter means a sell.

For any two starting positions, determine the length of the longest run of identical trades that begins at each of the two positions, counting the trade at each starting position as the first trade of the run.

Input

There are several test cases. Each test case begins with a line containing a string $s$ made up solely of upper- and lower-case letters ( $1 \le |s| \le 100{,}000$ ). The next line contains an integer $q$ , the number of queries ( $1 \le q \le 100{,}000$ ). Each of the following $q$ lines describes one query with two integers $i$ and $j$ , two zero-based positions in the string ( $0 \le i < j < |s|$ ).

The input ends with a line containing only an asterisk (*).

Output

For each query, output a single integer: the length of the longest run of trades starting at position $i$ that is identical to the run of trades starting at position $j$ . Print no spaces, and print no blank lines between output lines.

Examples5

Example 1

Input

ABABABcABABAbAbab
3
0 2
1 6
0 7
SheSellsSeashellsByTheSeaShore
4
8 22
1 20
8 25
0 1
*

Expected output

Example 2
Input
```
aaaaaaaa
3
0 1
2 5
0 7
*
```
Expected output
```
7
3
1
```
Example 3
Input
```
AaAaAa
2
0 2
0 1
*
```
Expected output
```
4
0
```
Example 4
Input
```
abcdefgh
2
0 4
2 5
*
```
Expected output
```
0
0
```
Example 5
Input
```
abcabcabcabc
3
0 3
0 6
1 4
*
```
Expected output
```
9
6
8
```