eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Підрядки

Підрядки

Ліміт часу 20 секунд
Ліміт використання пам'яті 64 MiB

Задано рядок S, який складається з маленьких літер латинського алфавіту. Необхідно відповідати на запити наступного виду:

Задано два підрядки, сфоровані початковим і кінцевим індексами [i,j] і [k,l]. Необхідно вивести '1' якщо підрядок S, сформований індексами [i,j], дорівнює підрядку S,сформованому індексами [j,k], і 0 у противному випадку.

Гарантується, що [i,j] і [k,l] дійсно є підрядками S. Упом'януті індекси нумеруються з 0. Обидва кінці інтервалу входять у підрядки.

Вхідні дані

Перший рядок містить кількість тестів T. Перший рядок кожного тесту містить рядок S. Далі йде кількість запитів Q. Кожен з наступних Q рядків містить 4 цілих числа i, j, k, l, які відповідають одному запиту.

Відомо, щто 1T10, 1 ≤ |S| ≤ 100000, 1Q100000, 0ij ≤ |S|-1, 0kl ≤ |S|-1. Через |S| позначено довжину рядка S.

Вихідні дані

Для кожного тесту вивести один рядок з Q символів, який містить '1' і '0' - відповіді на відповідні запити.

Приклад

Вхідні дані #1
1
aaad
4
0 2 0 2
0 1 2 3
0 0 1 1
0 4 0 3
Вихідні дані #1
1010
Автор Аджай Сомані
Джерело Севастополь - 2010