Longest Common Border of Two Prefixes

Given a string \(s\), we define its \(k\) prefix \(\mathit{pre}_k\) as the substring \(s_{1\dots k}\) and its \(k\) suffix \(\mathit{suf}_k\) as the substring \(s_{|s|-k+1\dots |s|}\), where \(1 \le k \le |s|\).

Define \(\mathbf{Border}(s)\) as the set of all proper prefixes \(\mathit{pre}_i\) (with \(1 \le i < |s|\)) such that \(\mathit{pre}_i = \mathit{suf}_i\). Each element in \(\mathbf{Border}(s)\) is called a border of \(s\>.

You are given \(m\) queries. Each query contains two integers \(p\) and \(q\). For each query, consider the two prefixes \(s[1\dots p]\) and \(s[1\dots q]\). Your task is to find and output the length of the longest common border shared by these two strings. If no common border exists, output 0.

inputFormat

The first line contains the string \(s\) consisting of lowercase letters.

The second line contains an integer \(m\) denoting the number of queries.

Each of the following \(m\) lines contains two integers \(p\) and \(q\) (\(1 \le p,q \le |s|\)), representing the lengths of the two prefixes of \(s\) to be considered.

outputFormat

For each query, output one integer on a separate line indicating the length of the longest common border of the \(p\)-prefix and \(q\)-prefix of \(s\). If there is no common border, output 0.

sample

ababa
2
5 3
3 3

1
1