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.*;
import java.util.*;

public class Main extends Thread {

    private static FastScanner scanner = new FastScanner(System.in);
    private static PrintWriter writer = new PrintWriter(System.out);
    //    private static Scanner scanner = new Scanner(System.in);
    private static char[] S;
    private static char[] T;
    private static int[] bSCount;
    private static int[] aSLastPos;
    private static int[] bTCount;
    private static int[] aTLastPos;

    //AAAAAAABBBAABBBB AB BBAAAAAABBBBBA AAAABB
    public static void main(String[] args) throws IOException {
        S = scanner.next().toCharArray();
        T = scanner.next().toCharArray();
        bSCount = preComputeB(S);
        aSLastPos = preComputeA(S);
        bTCount = preComputeB(T);
        aTLastPos = preComputeA(T);
        int n = scanner.nextInt();
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; i++) {
            ans.append(
                    solve(scanner.nextInt() - 1, scanner.nextInt() - 1, scanner.nextInt() - 1, scanner.nextInt() - 1)
                            ? 1 : 0);
        }
        System.out.println(ans);


    }

    private static int[] preComputeA(char[] s) {
        int aPos = -1;
        int[] ans = new int[s.length];
        for (int i = 0; i < s.length; i++) {
            if (s[i] == 'A') {
                ans[i] = aPos == -1 ? aPos = i : aPos;
            } else {
                ans[i] = aPos = -1;
            }
        }
        return ans;
    }

    private static int[] preComputeB(char[] s) {
        int[] ans = new int[s.length];
        ans[0] = s[0] == 'B' || s[0] == 'C' ? 1 : 0;
        for (int i = 1; i < s.length; i++) {
            ans[i] = ans[i - 1] + (s[i] == 'B' || s[i] == 'C' ? 1 : 0);
        }
        return ans;
    }

    private static boolean solve(int s1, int s2, int t1, int t2) {
        int bS = countB(bSCount, s1, s2);
        int aS = countA(aSLastPos, s1, s2);
        int bT = countB(bTCount, t1, t2);
        int aT = countA(aTLastPos, t1, t2);

        if (aS < aT ||
                bS > bT ||
                (bT - bS) % 2 != 0) return false;

        if (bS == bT) {
            return (aS - aT) % 3 == 0;
        } else if (bS == 0) {
            return aS > aT;
        } else if (bS < bT) {
            return true;
        }

        return false;
    }

    private static int countA(int[] a, int s1, int s2) {
        if (a[s2] == -1) return 0;
        return s2 - Integer.max(a[s2], s1) + 1;
    }

    private static int countB(int[] s, int s1, int s2) {
        return s[s2] - (s1 == 0 ? 0 : s[s1 - 1]);
    }


    static 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();
        }
    }

    static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
        public U first;
        public V second;

        public Pair(U first, V second) {
            this.first = first;
            this.second = second;
        }

        public int hashCode() {
            return (first == null ? 0 : first.hashCode() * 31) +
                    (second == null ? 0 : second.hashCode());
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pair<U, V> p = (Pair<U, V>) o;
            return (first == null ? p.first == null : first.equals(p.first)) &&
                    (second == null ? p.second == null : second.equals(p.second));
        }

        public int compareTo(Pair<U, V> b) {
            int cmpU = first.compareTo(b.first);
            return cmpU != 0 ? cmpU : second.compareTo(b.second);
        }

    }


}