Substrings
You are given a string S of lowercase letters. You need to answer the queries of following form:
Given a pair of substrings defined by starting and ending indices [i,j] and [k,l], you need to output '1' if Substring of S from [i,j] is equal to Substring of S from [j,k], and 0 otherwise.
You are guaranteed that both [i,j] and [k,l] will represent valid substrings of S. The indices mentioned in this problem are 0 based. Both ends of the range are included in the substrings.
Input
First line contains T, the number of test cases. For each test case, first line contains the string S. Next line contains Q, the number of queries. Next Q lines contains 4 integers i, j, k, l for the corresponding query.
It is known that 1 ≤ T ≤ 10, 1 ≤ |S| ≤ 100000, 1 ≤ Q ≤ 100000, 0 ≤ i ≤ j ≤ |S|-1, 0 ≤ k ≤ l ≤ |S|-1. Here |S| denotes the length of string S.
Output
For each test case, output one line containing a string of length Q containing '1' and '0' which are the answer of the queries for that test case.