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 { 
   public static void main(String[] args) {
      MyScanner sc = new MyScanner();
      out = new PrintWriter(new BufferedOutputStream(System.out));
      
      // Start -------------------------------------
 
      String s = sc.nextLine(),t = sc.nextLine();
      int l= s.length(),k= t.length();
      int[] total_S = new int [l+10];
      int[] total_T = new int [k+10];
      int[] lastB_S = new int [l+10];
      int[] lastB_T = new int [k+10];
      total_S[0]=0; total_T[0]=0;
      lastB_S[0]=0; lastB_T[0]=0;
      for(int i=0; i<l; ++i) {
    	  if(s.charAt(i)== 'A') {
    		  total_S[i+1] = total_S[i]+1;
    		  lastB_S[i+1]=lastB_S[i];
    	  }else{
    		  total_S[i+1]=total_S[i];
    		  lastB_S[i+1]=i+1;
    	  }
      }
      for(int i=0; i<k; ++i) {
    	  if(t.charAt(i)== 'A') {
    		  total_T[i+1] = total_T[i]+1;
    		  lastB_T[i+1]= lastB_T[i];
    	  }else{
    		  total_T[i+1]=total_T[i];
    		  lastB_T[i+1]=i+1;
    	  }
      }
      int q=sc.nextInt(),a,b,c,d;
      char[] ans= new char [q];
      for(int i=0;i<q;++i) {
    	  a=sc.nextInt();b=sc.nextInt();c=sc.nextInt();d=sc.nextInt();
    	  int x=total_S[b]-total_S[a-1],y=total_T[d]-total_T[c-1];
    	  int tx=b-Math.max(a-1, lastB_S[b]),ty=d-Math.max(c-1, lastB_T[d]);
//    	  if(s.charAt(b-1)!='A') tx=0;
//    	  if(t.charAt(d-1)!='A') ty=0;
    	  //out.println(x+" X "+y+" Y "+tx+" T "+ty);
    	  if((b-a-x-d+c+y)%2!=0) {
    		  ans[i]='0';
    		  continue;
    	  }
    	  if(b-a+1-x==d-c+1-y) {
    		  if (ty>tx || (tx-ty)%3!=0 ) {
    			  ans[i]='0';
    		  }else {
    			  ans[i]='1';
    		  }
    	  }else if(b-a+1==x) {
    		  if(tx>ty) {
    			  ans[i]='1';
    		  }else {
    			  ans[i]='0';
    		  }
    	  }else if(b-a-x<d-c-y){
    		  if(ty>tx) {
    			  ans[i]='0';
    		  }else ans[i]='1';
    	  }else {
    		  ans[i]='0';
    	  }
      }
      out.println(ans);
      // End  -------------------------------------
      out.close();
   }

   
   //-----------IO---------------------------------
   public static PrintWriter out;      
   public static class MyScanner {
      BufferedReader br;
      StringTokenizer st; 
      public MyScanner() {
         br = new BufferedReader(new InputStreamReader(System.in));
      }
      String next() {
          while (st == null || !st.hasMoreElements()) {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }
      int nextInt() {
          return Integer.parseInt(next());
      }
      long nextLong() {
          return Long.parseLong(next());
      }
      double nextDouble() {
          return Double.parseDouble(next());
      }
      String nextLine(){
          String str = "";
	  try {
	     str = br.readLine();
	  } catch (IOException e) {
	     e.printStackTrace();
	  }
	  return str;
      }
   }
}