Longest Match

Time Limit : 4 sec, Memory Limit : 131072 KB

文字列 S と, m 個のクエリが与えられる.i 番目のクエリは二つの文字列 xi, yi で与えられる.

各クエリについて,文字列 S の部分文字列であり, xi で始まり yi で終わるものの中で,最長の長さを答えよ.

文字列 S について, |S|S の長さを表す.また,文字列 T が文字列 S の部分文字列であるとは,ある整数 i が存在して, 1 ≤ j|T| に対して Tj = Si+j を満たすことを言う.ただし TjTj 番目の文字を表す.

Input

入力は以下の形式で与えられる.

S
m
x1 y1
x2 y2
:
xm ym
  • 1 行目には,文字列 S が与えられる.
  • 2 行目には,クエリの個数 m が与えられる.
  • 3 行目からの m 行のうち i 行目には i 番目のクエリ文字列 xi, yi が空白区切りで与えられる.

Constraints

  • 1 ≤ |S| ≤ 2 × 105
  • 1 ≤ m ≤ 105
  • 1 ≤ |xi|, |yi|
  • $\sum^m_{i=1}$ (|xi| + |yi|) ≤ 2 × 105
  • S 及び xi, yi は,半角の英小文字のみからなる.

Output

以下の形式で最大の部分文字列の長さを答えよ.

len1
len2
:
lenm

1 行目からの m 行のうち i 行目には, i 番目のクエリについて,条件を満たす最長の部分文字列の長さ leni を出力せよ.そのような部分文字列がない場合,0 を出力せよ.

Sample Input 1

abracadabra
5
ab a
a a
b c
ac ca
z z

Output for the Sample Input 1

11
11
4
3
0

文字列 S として,abracadabra が与えられる.

  • "ab" で始まり "a" で終わる部分文字列は,"abra" や "abraca", "abracada", "abracadabra" の4 種類があるが,最長の部分文字列は "abracadabra" で,長さは 11 である.
  • "a" で始まり "a" で終わる最長の部分文字列も同様に "abracadabra" で,長さは 11 である.
  • "b" で始まり "c" で終わる最長の部分文字列は "brac" で,長さは 4 である.
  • "ac" で始まり "ca" で終わる最長の部分文字列は "aca" で,長さは 3 である.
  • "z" で始まり "z" で終わる部分文字列は存在しない.よって0 を出力する.

Sample Input 2

howistheprogress
4
ist prog
s ss
how is
the progress

Output for the Sample Input 2

9
12
5
11

Sample Input 3

icpcsummertraining
9
mm m
icpc summer
train ing
summer mm
i c
i i
g g
train i
summer er

Output for the Sample Input 3

2
10
8
0
4
16
1
6
6

Source: ACM-ICPC Japan Alumni Group Summer Camp 2014 , Day 4, Tokyo, Japan, 2014-09-15
http://acm-icpc.aitea.net/
http://jag2014summer-day4.contest.atcoder.jp/