Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

D. Picking Strings

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlice has a string consisting of characters 'A', 'B' and 'C'. Bob can use the following transitions on any substring of our string in any order any number of times:

- A BC
- B AC
- C AB
- AAA empty string

Note that a substring is one or more consecutive characters. For given queries, determine whether it is possible to obtain the target string from source.

Input

The first line contains a string *S* (1 ≤ |*S*| ≤ 10^{5}). The second line contains a string *T* (1 ≤ |*T*| ≤ 10^{5}), each of these strings consists only of uppercase English letters 'A', 'B' and 'C'.

The third line contains the number of queries *Q* (1 ≤ *Q* ≤ 10^{5}).

The following *Q* lines describe queries. The *i*-th of these lines contains four space separated integers *a*_{i}, *b*_{i}, *c*_{i}, *d*_{i}. These represent the *i*-th query: is it possible to create *T*[*c*_{i}..*d*_{i}] from *S*[*a*_{i}..*b*_{i}] by applying the above transitions finite amount of times?

Here, *U*[*x*..*y*] is a substring of *U* that begins at index *x* (indexed from 1) and ends at index *y*. In particular, *U*[1..|*U*|] is the whole string *U*.

It is guaranteed that 1 ≤ *a* ≤ *b* ≤ |*S*| and 1 ≤ *c* ≤ *d* ≤ |*T*|.

Output

Print a string of *Q* characters, where the *i*-th character is '1' if the answer to the *i*-th query is positive, and '0' otherwise.

Example

Input

AABCCBAAB

ABCB

5

1 3 1 2

2 2 2 4

7 9 1 1

3 4 2 3

4 5 1 3

Output

10011

Note

In the first query we can achieve the result, for instance, by using transitions .

The third query asks for changing AAB to A — but in this case we are not able to get rid of the character 'B'.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 18:37:19 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|