Дана строка S = s
1s
2...s
n и множество запросов вида (l
1, r
1, l
2, r
2). Для каждого запроса требуется ответить, равны ли подстроки s
l1...s
r1 и s
l2...s
r2.
Входные данные:
В первой строке дана строка S (1 <= |S| <= 10
5), состоящая из строчных латинских букв.
Во второй строке дано натуральное число q (1 <= q <= 10
5) - количество запросов.
В следующих q строках дано по 4 натуральных числа - l
1, r
1, l
2, r
2 (1 <= l
1 <= r
1 <= |S|, 1 <=l
2 <= r
2 <= |S|).
Выходные данные:
Для каждого запроса выведите '+', если подстроки равны, и '-', в противном случае.
Примеры:
| Входные данные |
Выходные данные |
abacaba
4
1 1 7 7
1 3 5 7
3 4 4 5
1 7 1 7 |
++-+ |