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 utkarsh {

    InputStream is;
    PrintWriter out;
    
    void solve(){
        //Enter code here utkarsh
        char[] s = ns().toCharArray();
        char[] t = ns().toCharArray();
        int n = s.length;
        int m = t.length;
        int a[] = new int[n+1];
        for(int i = 0; i < n; i++) {
            a[i+1] = a[i] + (s[i] != 'A' ? 1 : 0);
        }
        int ax[] = new int[n+1];
        for(int i = 0; i < n; i++) {
            if(s[i] == 'A') ax[i+1] = ax[i] + 1;
        }
        int b[] = new int[m+1];
        for(int i = 0; i < m; i++) {
            b[i+1] = b[i] + (t[i] != 'A' ? 1 : 0);
        }
        int bx[] = new int[m+1];
        for(int i = 0; i < m; i++) {
            if(t[i] == 'A') bx[i+1] = bx[i] + 1;
        }
        int q = ni();
        while(q-- > 0) {
            int x = ni();   int y = ni();
            int u = ni();   int v = ni();
            int aa = a[y] - a[x-1];
            int bb = b[v] - b[u-1];
            if(aa > bb || (aa%2 != bb%2)) {
                out.print(0);
                continue;
            }
            int axx = ax[y];
            if(axx > (y - x + 1))   axx = y - x + 1;
            int bxx = bx[v];
            if(bxx > (v - u + 1))   bxx = v - u + 1;
            if((axx%3 != bxx %3 && aa + 2 > bb) || axx < bxx || (axx == bxx && axx == (y - x + 1) && bxx != (v - u + 1))) {
                out.print(0);
            } else {
                out.print(1);
            }
        }
    }
    
    public static void main(String[] args) { new utkarsh().run();
    }
    void run(){ is = System.in; out = new PrintWriter(System.out); solve(); out.flush();
    }
    
    byte input[] = new byte[1024];
    int len = 0, ptr = 0;
    
    int readByte(){ if(ptr >= len){ ptr = 0; try{ len = is.read(input); }catch(IOException e){ throw new InputMismatchException(); } if(len <= 0){ return -1; } } return input[ptr++];
    }
    boolean isSpaceChar(int c){ return !( c >= 33 && c <= 126 ); 
    }
    int skip(){ int b = readByte(); while(b != -1 && isSpaceChar(b)){ b = readByte(); } return b;
    }
    
    char nc(){ return (char)skip();
    }
    String ns(){ int b = skip(); StringBuilder sb = new StringBuilder(); while(!isSpaceChar(b)){ sb.appendCodePoint(b); b=readByte(); } return sb.toString();
    }
    int ni(){ int n = 0,b = readByte(); boolean minus = false; while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')){ b = readByte(); } if(b == '-'){ minus = true; b = readByte(); } if(b == -1){ return -1; } while(b >= '0' && b <= '9'){ n = n * 10 + (b - '0'); b = readByte(); } return minus ? -n : n;
    }
    long nl(){ long n = 0L; int b = readByte(); boolean minus = false; while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')){ b = readByte(); } if(b == '-'){ minus = true; b = readByte(); } while(b >= '0' && b <= '9'){ n = n * 10 + (b - '0'); b = readByte(); } return minus ? -n : n;
    }
    double nd(){ return Double.parseDouble(ns());
    }
    float nf(){ return Float.parseFloat(ns());
    }
    int[] na(int n){ int a[] = new int[n]; for(int i = 0; i < n; i++){ a[i] = ni(); } return a;
    }
    char[] ns(int n){ char c[] = new char[n]; int i,b = skip(); for(i = 0; i < n; i++){ if(isSpaceChar(b)){ break; } c[i] = (char)b; b = readByte(); } return i == n ? c : Arrays.copyOf(c,i);
    }
}