P401363 - GYM100418 C Substrings - SSOJ - 省实信息奥赛评测系统

Memory Limit：64 MB Time Limit：3 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

上一题 Submit 下一题 Submit Record Statistics MD

C. Substringstime limit per test3 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

You are given a string S consisting of capital Latin letters. Consider the queries consisting of pairs of integer numbers L_i and R_i. For each of them you should find the number of substrings which are less than substring S[L_i...R_i].

Input

The first line contains the string S(1 ≤ |S| ≤ 10⁵). The second line contains the number N (1 ≤ N ≤ 10⁵), denoting the number of queries. The next N lines contain pairs of numbers L_i, R_i (1 ≤ L_i ≤ R_i ≤ |S|).

Output

For each query you should output the number of substrings which satisfy specified conditions.

ExamplesInput

BSUIROPENPROGRAMMINGCHAMPIONSHIP
1
1 15

Output

2013-2014 BSUIR Open Programming Championship. Final

401363: GYM100418 C Substrings

Description

Source/Category

加入题单