Equal substrings#4843
Given a string S = s_1s_2\dots s_n and a set of queries of the form (l_1, r_1, l_2, r_2).
For each query, determine whether the substrings s_{l_1}\dots s_{r_1} and s_{l_2}\dots s_{r_2} are equal.
The first line contains the string , consisting of lowercase Latin letters. The string is non-empty and has length at most 10^5.
The second line contains an integer (1 \leq q \leq 50000) — the number of queries.
Each of the following lines contains four integers l_1, r_1, l_2, r_2 (1 \leq l_1 \leq r_1 \leq |S|, 1 \leq l_2 \leq r_2 \leq |S|).
For each query, print "+" if the corresponding substrings are equal, and "-" otherwise.
Esempio 1