Задана строка 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, соответствующих одному запросу.
Известно, что 1 ≤ T ≤ 10, 1 ≤ |S| ≤ 100000, 1 ≤ Q ≤ 100000, 0 ≤ i ≤ j ≤ |S|-1, 0 ≤ k ≤ l ≤ |S|-1. Через |S| обозначена длина строки S.
Для каждого теста вывести одну строку из Q символов, содержащую '1' и '0' - ответы на соответствующие запросы.