# Front compression

Time Limit: 5000/5000 MS (Java/Others)

Memory Limit: 102400/102400 K (Java/Others)

## Description

Front compression is a type of delta encoding compression algorithm whereby common prefixes and their lengths are recorded so that they need not be duplicated. For example:

The size of the input is 43 bytes, while the size of the compressed output is 40. Here, every space and newline is also counted as 1 byte.
Given the input, each line of which is a substring of a long string, what are sizes of it and corresponding compressed output?

## Input

There are multiple test cases. Process to the End of File.
The first line of each test case is a long string S made up of lowercase letters, whose length doesn't exceed 100,000. The second line contains a integer 1 ≤ N ≤ 100,000, which is the number of lines in the input. Each of the following N lines contains two integers 0 ≤ A < B ≤ length(S), indicating that that line of the input is substring [A, B) of S.

## Output

For each test case, output the sizes of the input and corresponding compressed output.

## Sample Input

frcode
2
0 6
0 6
unitedstatesofamerica
3
0 6
0 12
0 21
myxophytamyxopodnabnabbednabbingnabit
6
0 9
9 16
16 19
19 25
25 32
32 37

## Sample Output

14 12
42 31
43 40

zhuyuanchen520

## Source

2013 Multi-University Training Contest 9