E - 田端でバタバタ

Time Limit: 6 sec / Memory Limit: 256 MB

問題文

繰り返し文字列とは、ある空でない文字列 A があって A+A の形で表される文字列のことを表します。言語学では畳語ともいいます。日本語は畳語が非常に多く、通常の文章でも頻繁に出現します。今回はこれを数えてみたいと思います。

小文字アルファベットからなる文字列 SQ 個のクエリ [a_i,b_i] が与えられます。S[a_i,b_i] の全ての空でない部分文字列のうち、繰り返し文字列となっているものの長さの和を求めてください。同じ文字列が複数存在する場合も、それぞれ別の物として考えてください。

なお、文字列 AB に対して、連結したものを A+B と表します。また S[x,y] とは、文字列 Sx 文字目から 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

kokopyonpyonが繰り返し文字列に相当します。

1 つ目のクエリでは、kokoropyonpyonについて考えます。kokopyonpyon2つの繰り返し文字列が存在するので、答えは 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

大量の繰り返し文字列が発生するケースが存在することに注意してください。


Source Name

天下一プログラマーコンテスト2014 本戦