eolymp
bolt
Try our new interface for solving problems
Problems

Substrings

Substrings

Time limit 20 seconds
Memory limit 64 MiB

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 data

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 1T10, 1 ≤ |S| ≤ 100000, 1 Q100000, 0ij ≤ |S|-1, 0kl ≤ |S|-1. Here |S| denotes the length of string S.

Output data

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.

Examples

Input example #1
1
aaad
4
0 2 0 2
0 1 2 3
0 0 1 1
0 4 0 3
Output example #1
1010
Author Ajay Somani
Source Sevastopol - 2010