Problems
Equal substrings
Equal substrings
Given a string S = s1s2...sn
and a set of queries like (l1
, r1
, l2
, r2
).
For each query answer whether the substrings sl1
...sr1
and sl2
...sr2
are equal.
Input
The first line contains the string S, consisting of lowercase Latin letters. This string is non-empty and has a maximum length of 105
characters. The second line contains an integer q (1 ≤ q ≤ 50000) - the number of queries. Each of the following q lines contains the numbers l1
, r1
, l2
, r2
(1 ≤ l1
≤ r1
≤ |S|, 1 ≤ l2
≤ r2
≤ |S|).
Output
For each query print "+" if the corresponding substrings are equal, and "-" otherwise.
Input example #1
abacaba 4 1 1 7 7 1 3 5 7 3 4 4 5 1 7 1 7
Output example #1
++-+