Given a string S = s
1s
2...s
n and a set of queries like (l
1, r
1, l
2, r
2). For each query, it is required to answer whether the substrings s
l1...s
r1 and s
l2...s
r2 are equal .
Input:
The first line contains the string S (1 <= |S| <= 10
5) consisting of lowercase Latin letters.
The second line contains a natural number q (1 <= q <= 10
5) - the number of requests.
The next q lines contain 4 natural numbers each - l
1, r
1, l
2, r
2 ( 1 <= l
1 <= r
1 <= |S|, 1 <=l
2 <= r< sub>2 <= |S|).
Output:
For each query, print '+' if the substrings are equal, and '-' otherwise.
Examples:
| Input |
Output |
abacaba
4
1 1 7 7
1 3 5 7
3 4 4 5
1 7 1 7
| ++-+ |