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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @author Don Li
 */
public class PickingStrings {
    void solve() {
        char[] s = in.nextToken().toCharArray();
        char[] t = in.nextToken().toCharArray();
        int n = s.length, m = t.length;
        
        for (int i = 0; i < n; i++) if (s[i] == 'C') s[i] = 'B';
        for (int i = 0; i < m; i++) if (t[i] == 'C') t[i] = 'B';
        
        int[] s_cnt_b = new int[n], s_last_b = new int[n];
        for (int i = 0, last_b = -1; i < n; i++) {
            if (s[i] == 'B') {
                last_b = i;
                s_cnt_b[i]++;
            }
            s_last_b[i] = last_b;
        }
        int[] s_sum_b = new int[n + 1];
        for (int i = 0; i < n; i++) s_sum_b[i + 1] = s_sum_b[i] + s_cnt_b[i];
        
        int[] t_cnt_b = new int[m], t_last_b = new int[m];
        for (int i = 0, last_b = -1; i < m; i++) {
            if (t[i] == 'B') {
                last_b = i;
                t_cnt_b[i]++;
            }
            t_last_b[i] = last_b;
        }
        int[] t_sum_b = new int[m + 1];
        for (int i = 0; i < m; i++) t_sum_b[i + 1] = t_sum_b[i] + t_cnt_b[i];
        
        int Q = in.nextInt();
        while (Q-- > 0) {
            int l1 = in.nextInt() - 1, r1 = in.nextInt() - 1, l2 = in.nextInt() - 1, r2 = in.nextInt() - 1;
            int s_tot_b = s_sum_b[r1 + 1] - s_sum_b[l1], s_suffix_a = Math.min(r1 - s_last_b[r1], r1 - l1 + 1);
            int t_tot_b = t_sum_b[r2 + 1] - t_sum_b[l2], t_suffix_a = Math.min(r2 - t_last_b[r2], r2 - l2 + 1);
            if (s_tot_b > t_tot_b) {
                out.print(0);
            } else if (s_tot_b == t_tot_b) {
                if (s_suffix_a >= t_suffix_a && (s_suffix_a - t_suffix_a) % 3 == 0) out.print(1);
                else out.print(0);
            } else {
                if ((t_tot_b - s_tot_b) % 2 != 0 || s_suffix_a < t_suffix_a) {
                    out.print(0);
                } else {
                    int delta_a = s_suffix_a - t_suffix_a;
                    if (s_tot_b == 0) {
                        if (delta_a > 0) out.print(1);
                        else out.print(0);
                    } else {
                        out.print(1);
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new PickingStrings().solve();
        out.close();
    }
    
    static FastScanner in;
    static PrintWriter out;
    
    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;
        
        public FastScanner(BufferedReader in) {
            this.in = in;
        }
        
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        
        public long nextLong() {
            return Long.parseLong(nextToken());
        }
        
        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}
