Alice 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 <image> BC
  * B <image> AC
  * C <image> AB
  * AAA <image> 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| ≤ 105). The second line contains a string T (1 ≤ |T| ≤ 105), 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 ≤ 105).

The following Q lines describe queries. The i-th of these lines contains four space separated integers ai, bi, ci, di. These represent the i-th query: is it possible to create T[ci..di] from S[ai..bi] 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 <image>.

The third query asks for changing AAB to A — but in this case we are not able to get rid of the character 'B'.
import java.io.BufferedReader;
// import java.io.FileInputStream;
// import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;

import static java.lang.Math.min;
import static java.util.Arrays.copyOf;
import static java.util.Arrays.fill;
import static java.util.Arrays.sort;
import static java.util.Collections.reverseOrder;
import static java.util.Collections.sort;

public class Main {
    FastScanner in;
    PrintWriter out;

    private void solve() throws IOException {
        char[] s = in.next().toCharArray();
        int[] prefS = new int[s.length + 1];
        int[] suffS = new int[s.length + 1];
        for (int i = 0; i < s.length; i++) {
            prefS[i + 1] = prefS[i] + (s[i] != 'A' ? 1 : 0);
            suffS[i + 1] = s[i] == 'A' ? suffS[i] + 1 : 0;
        }

        char[] t = in.next().toCharArray();
        int[] prefT = new int[t.length + 1];
        int[] suffT = new int[t.length + 1];
        for (int i = 0; i < t.length; i++) {
            prefT[i + 1] = prefT[i] + (t[i] != 'A' ? 1 : 0);
            suffT[i + 1] = t[i] == 'A' ? suffT[i] + 1 : 0;
        }

        int sl, sr, tl, tr;
        int cntS, cntT;
        int sufS, sufT;
        for (int q = in.nextInt(); q-- > 0; ) {
            sl = in.nextInt();
            sr = in.nextInt();
            tl = in.nextInt();
            tr = in.nextInt();
            cntS = prefS[sr] - prefS[sl - 1];
            cntT = prefT[tr] - prefT[tl - 1];

            if (cntS > cntT || cntS % 2 != cntT % 2)
                out.print(0);
            else {
                sufS = min(suffS[sr], sr - sl + 1);
                sufT = min(suffT[tr], tr - tl + 1);

                if (sufS > sufT)
                    out.print(cntS < cntT ? 1 : (sufS - sufT) % 3 == 0 ? 1 : 0);
                else
                    out.print(sufS == sufT && (sufS < sr - sl + 1 || cntS == cntT) ? 1 : 0);
            }
        }
    }

    class FastScanner {
        StringTokenizer st;
        BufferedReader br;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        boolean hasNext() throws IOException {
            return br.ready() || (st != null && st.hasMoreTokens());
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next().replace(',', '.'));
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

        boolean hasNextLine() throws IOException {
            return br.ready();
        }
    }

    private void run() throws IOException {
        in = new FastScanner(System.in); // new FastScanner(new FileInputStream(".in"));
        out = new PrintWriter(System.out); // new PrintWriter(new FileOutputStream(".out"));

        solve();

        out.flush();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}
