/ 
Time Limit: 6 sec / Memory Limit: 256 MB
問題文
繰り返し文字列とは、ある空でない文字列 A があって A+A の形で表される文字列のことを表します。言語学では畳語ともいいます。日本語は畳語が非常に多く、通常の文章でも頻繁に出現します。今回はこれを数えてみたいと思います。小文字アルファベットからなる文字列 S と Q 個のクエリ [a_i,b_i] が与えられます。S[a_i,b_i] の全ての空でない部分文字列のうち、繰り返し文字列となっているものの長さの和を求めてください。同じ文字列が複数存在する場合も、それぞれ別の物として考えてください。
なお、文字列 A と B に対して、連結したものを A+B と表します。また S[x,y] とは、文字列 S の x 文字目から y 文字目までを切り取った部分文字列を表します。
入力
入力は以下の形式で標準入力から与えられる。
S Q a_1 b_1 ... a_Q b_Q
- 1 行目には、文字列 S\ (1 ≦ |S| ≦ 100000) が与えられる。（|S| は文字列 S の長さを表す）
- 2 行目には、クエリの数を表す整数 Q\ (1 ≦ Q ≦ 100000) が与えられる。
- 3 行目から Q 行は、クエリの情報が与えられる。 このうち i\ (1 ≦ i ≦ Q) 行目には、 i 番目のクエリの情報を表す整数 a_i, b_i\ (1 ≦ a_i ≦ b_i ≦ |S|) が、スペース区切りで与えられる。
出力
各クエリに対する答えを、 1 行ずつ Q 行で出力せよ。出力の末尾には改行をいれること。
部分点
1 ≦ |S| ≦ 1000 のテストケースに全て正解した場合 、部分点として 100 点が与えられる。
1 ≦ |S| ≦ 20000 のテストケースに全て正解した場合 、部分点としてさらに 100 点が与えられる。
全てのテストケースに正解すると、さらに 150 点が与えられる。
入力例1
kokoropyonpyon 3 1 14 2 14 1 13
出力例1
12 8 4
kokoとpyonpyonが繰り返し文字列に相当します。
1 つ目のクエリでは、kokoropyonpyonについて考えます。koko、pyonpyonの 2つの繰り返し文字列が存在するので、答えは 12 です。
2 つ目のクエリでは、okoropyonpyonについて考えます。pyonpyonが存在するので、答えは 8 です。
3 つ目のクエリでは、kokoropyonpyoについて考えます。kokoが存在するので、答えは 4 です。
入力例2
rattatta 5 2 7 3 8 3 4 3 3 1 8
出力例2
10 10 2 0 16
attatt, ttatta, tt, ttが、繰り返し文字列に該当します。tt 2 個は別物とします。
入力例3
aaaaaaaaaa 1 1 10
出力例3
110
大量の繰り返し文字列が発生するケースが存在することに注意してください。