Partition and Reverse String Matching

You are given a string S. For each query, you are provided with two substrings defined by indices: S[l₁, r₁] and S[l₂, r₂]. Determine the number of ways to partition the first substring into three parts A, B, and C (each of which can be empty) such that:

\(S[l₁, r₁] = A + B + C\)

and

\(C + B^R + A = S[l₂, r₂]\)

Here, B^R denotes the reversal of string B, and the operator \( + \) denotes string concatenation. The notation S[l, r] represents the substring of S from the l^th to the r^th character (1-indexed).

Note: If the lengths of the two substrings are not equal, then the answer is 0.

inputFormat

The first line contains the string S.

The second line contains an integer Q indicating the number of queries.

Each of the following Q lines contains four integers l₁, r₁, l₂, r₂ separated by spaces.

outputFormat

For each query, output a single integer representing the number of valid partitioning ways.

sample

abcabc
1
1 3 1 3

2