Problem:


Score : 600 points

Problem Statement

Let us consider the following operations on a string consisting of A and B:

Select a character in a string. If it is A, replace it with BB. If it is B, replace with AA.

Select a substring that is equal to either AAA or BBB, and delete it from the string.

For example, if the first operation is performed on ABA and the first character is selected, the string becomes BBBA.
If the second operation is performed on BBBAAAA and the fourth through sixth characters are selected, the string becomes BBBA.

These operations can be performed any number of times, in any order.

You are given two string S and T, and q queries a_i, b_i, c_i, d_i.
For each query, determine whether S_{a_i} S_{{a_i}+1} ... S_{b_i}, a substring of S, can be made into T_{c_i} T_{{c_i}+1} ... T_{d_i}, a substring of T.

Constraints

1 \leq |S|, |T| \leq 10^5

S and T consist of letters A and B.

1 \leq q \leq 10^5

1 \leq a_i \leq b_i \leq |S|

1 \leq c_i \leq d_i \leq |T|

Input

Input is given from Standard Input in the following format:

S
T
q
a_1 b_1 c_1 d_1
...
a_q b_q c_q d_q

Output

Print q lines. The i-th line should contain the response to the i-th query. If S_{a_i} S_{{a_i}+1} ... S_{b_i} can be made into T_{c_i} T_{{c_i}+1} ... T_{d_i}, print YES. Otherwise, print NO.

Sample Input 1

BBBAAAABA
BBBBA
4
7 9 2 5
7 9 1 4
1 7 2 5
1 7 2 4

Sample Output 1

YES
NO
YES
NO

The first query asks whether the string ABA can be made into BBBA.
As explained in the problem statement, it can be done by the first operation.

The second query asks whether ABA can be made into BBBB, and the fourth query asks whether BBBAAAA can be made into BBB.
Neither is possible.

The third query asks whether the string BBBAAAA can be made into BBBA.
As explained in the problem statement, it can be done by the second operation.

Sample Input 2

AAAAABBBBAAABBBBAAAA
BBBBAAABBBBBBAAAAABB
10
2 15 2 13
2 13 6 16
1 13 2 20
4 20 3 20
1 18 9 19
2 14 1 11
3 20 3 15
6 16 1 17
4 18 8 20
7 20 3 14

Sample Output 2

YES
YES
YES
YES
YES
YES
NO
NO
NO
NO



Sample input:
BBBAAAABA
BBBBA
4
7 9 2 5
7 9 1 4
1 7 2 5
1 7 2 4


Sample output:
YES
NO
YES
NO

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    s = input()
    t = input()
    ns = len(s)+1
    nt = len(t)+1
    ssa = [0]*ns
    ssb = [0]*ns
    sta = [0]*nt
    stb = [0]*nt
    for i,si in enumerate(s):
        if si == "A":
            da = 1
            db = 0
        else:
            da = 0
            db = 1
        ssa[i+1] = ssa[i]+da
        ssb[i+1] = ssb[i]+db
    for i,ti in enumerate(t):
        if ti == "A":
            da = 1
            db = 0
        else:
            da = 0
            db = 1
        sta[i+1] = sta[i]+da
        stb[i+1] = stb[i]+db

    q = int(ipt())
    for _ in range(q):
        a,b,c,d = map(int,ipt().split())
        da = ssa[b]-ssa[a-1]-sta[d]+sta[c-1]
        db = ssb[b]-ssb[a-1]-stb[d]+stb[c-1]
        if (da-db)%3 == 0:
            print("Yes")
        else:
            print("No")

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
S=input()
T=input()
N=int(input())
abcd = [tuple(map(int,input().split())) for _ in range(N)]

NS = len(S)
NT = len(T)
cs0 = [0]*(NS+1)
cs1 = [0]*(NS+1)
ct0 = [0]*(NT+1)
ct1 = [0]*(NT+1)
for i in range(NS):
    cs0[i+1] = cs0[i]
    cs1[i+1] = cs1[i]
    if S[i]=='A':
        cs0[i+1] += 1
    else:
        cs1[i+1] += 1
for i in range(NT):
    ct0[i+1] = ct0[i]
    ct1[i+1] = ct1[i]
    if T[i]=='A':
        ct0[i+1] += 1
    else:
        ct1[i+1] += 1

for a,b,c,d in abcd:
    anum = cs0[b] - cs0[a-1]
    bnum = cs1[b] - cs1[a-1]
    num = abs(anum-bnum)%3
    anum2 = ct0[d] - ct0[c-1]
    bnum2 = ct1[d] - ct1[c-1]
    num2 = abs(anum2-bnum2)%3
    if num+num2 in [0,3]:
        print('YES')
    else:
        print('NO')

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

accSA = [0] * (len(S) + 1)
accSB = [0] * (len(S) + 1)

for i, s in enumerate(S):
    accSA[i + 1] += accSA[i - 1]
    accSB[i + 1] += accSB[i - 1]
    if s == 'A':
        accSA[i + 1] += 1
    else:
        accSB[i + 1] += 1

accTA = [0] * (len(T) + 1)
accTB = [0] * (len(T) + 1)

for i, s in enumerate(T):
    accTA[i + 1] += accTA[i - 1]
    accTB[i + 1] += accTB[i - 1]
    if s == 'A':
        accTA[i + 1] += 1
    else:
        accTB[i + 1] += 1

Q = int(input())
ans = []
for _ in range(Q):
    a, b, c, d = map(int, input().split())

    sA = accSA[b] - accSA[a - 1]
    sB = accSB[b] - accSB[a - 1]
    tA = accTA[d] - accTA[c - 1]
    tB = accTB[d] - accTB[c - 1]

    sA = (sA + sB * 2) % 3
    tA = (tA + tB * 2) % 3

    ans.append('YES' if sA == tA else 'NO')
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

q = int(input())

s = [0]*len(S)
t = [0]*len(T)
for i, x in enumerate(S):
    if x == "A":
        s[i] += 1
for i, x in enumerate(T):
    if x == "A":
        t[i] += 1

ss = [0]*(len(S)+1)
for i, x in enumerate(s):
    ss[i+1] = s[i] + ss[i]
tt = [0]*(len(T) + 1)
for i, x in enumerate(t):
    tt[i+1] = t[i]+tt[i]


for i in range(q):
    a, b, c, d = map(int, input().split())

    k = (ss[b] - ss[a-1])
    l = (tt[d] - t[c-1])
    k += ((b - a + 1) - k)*2
    l += ((d - c + 1) - l)*2
    if abs(k-l) % 3 == 0:
        print("YES")
    else:
        print("NO")

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

S = input()
T = input()
Q = int(input())
ABCD = [list(map(int, input().split())) for _ in range(Q)]

SL = [1 if s == "A" else 2 for s in S]
TL = [1 if t == "A" else 2 for t in T]

AcumS = [0] + list(accumulate(SL))
AcumT = [0] + list(accumulate(TL))

for a, b, c, d in ABCD:
    s = AcumS[b] - AcumS[a - 1]
    t = AcumT[d] - AcumT[c - 1]
    if (s - t) % 3 == 0:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
q = int(input())
L = [[int(l) for l in input().split()] for _ in range(q)]

sumS = [0]*(len(S)+1)
sumT = [0]*(len(T)+1)

for i in range(len(S)):
    if S[i] == "A":
        sumS[i+1] += 1
    sumS[i+1] += sumS[i]

for i in range(len(T)):
    if T[i] == "A":
        sumT[i+1] += 1
    sumT[i+1] += sumT[i]

for i in range(q):
    a = (sumT[L[i][3]]-sumT[L[i][2]-1]) - (sumS[L[i][1]]-sumS[L[i][0]-1])
    b = (L[i][3]-L[i][2]+1) - (L[i][1]-L[i][0]+1) - a
    if (a-b)%3 == 0:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
def examC():
    N = I()
    d = defaultdict(int)
    for i in range(N):
        curD = defaultdict(int)
        S = SI()
        for s in S:
            curD[s]+=1
        if i==0:
            d = curD
            continue
        for s in alphabet:
            d[s] = min(d[s],curD[s])
    d = sorted(d.items())
    ans = ""
    for key,i in d:
        ans +=key*i
    print(ans)
    return

def examD():
    N, M = LI()
    X = LI(); Y = LI()
    distX = [0]*N; distY = [0]*M
    for i in range(N-1):
        distX[i+1] = X[i+1]-X[i]
    for i in range(M-1):
        distY[i+1] = Y[i+1]-Y[i]
    numX = [0]*N; numY = [0]*M
    for i in range(N):
        numX[i] = i*(N-i)
    for i in range(M):
        numY[i] = i*(M-i)
    LX = 0; LY = 0
    for i in range(N):
        LX += distX[i]*numX[i]
        LX %= mod
    for i in range(M):
        LY += distY[i]*numY[i]
        LY %= mod
#    print(numX,distX); print(numY,distY)
    ans = (LX*LY) % mod
    print(ans)
    return

def examE():
    S = SI(); T = SI()
    numaS = [0]*(len(S)+1)
    numaT = [0]*(len(T)+1)
    for i,s in enumerate(S):
        numaS[i+1] = numaS[i]
        if s=="A":
            numaS[i+1] +=1
    for i,s in enumerate(T):
        numaT[i+1] = numaT[i]
        if s=="A":
            numaT[i+1] +=1
#    print(numaS); print(numaT)
    Q = I()
    ans = ["YES"]*Q
    for i in range(Q):
        a,b,c,d = LI()
        curaS = numaS[b] - numaS[a-1]
        curbS = (b-a)-curaS+1
        curaT = numaT[d] - numaT[c-1]
        curbT = (d-c)-curaT+1
        print(curaS,curbS,curaT,curbT)
        if (curaS%3+(curaS+curbS)%3)%3 != (curaT%3+(curaT+curbT)%3)%3:
#            if (curbS % 3 + (curaS + curbS) % 3) % 3 != (curbT % 3 + (curaT + curbT) % 3) % 3:
            ans[i]="NO"
    for v in ans:
        print(v)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

Submission status: Wrong Answer

Solution code:
import sys 
input = sys.stdin.readline
yes = "YES"
no = "NO"
s=input()
t=input()
ls=[0]
lt=[0]
p=0
for c in s:
    if c == "A":p += 1
    else:p-= 1
    ls.append(p)
p=0
for c in t:
    if c == "A":p += 1
    else:p-= 1
    lt.append(p)

q=int(input())
for _ in range(q):
    a,b,c,d = map(int,input().split())
    if a==b:
        if c==d:print(yes)
        else:print(no)
    else:
        f1 = (ls[b]-ls[a-1])%3 
        f2 = (lt[d]-lt[c-1])%3
        if (ls[b]-ls[a-1])%3 == (lt[d]-lt[c-1])%3:print(yes)
        else:print(no)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
readline = sys.stdin.readline

S = [1 if s == 'A' else 2 for s in readline().strip()]
T = [1 if s == 'A' else 2 for s in readline().strip()]
AS = [0] + list(accumulate(S))
AT = [0] + list(accumulate(T))
Q = int(readline())
Ans = [None]*Q 

for qu in range(Q):
    a, b, c, d = map(int, readline().split())
    if (AS[b]-AS[a-1])%3 != (AT[d]-AT[c-1])%3:
        Ans[qu] = 'NO'    
    elif a == b and c != d:
        Ans[qu] = 'NO'
    else:
        Ans[qu] = 'YES'

print('\n'.join(map(str, Ans)))

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
q = int(input())

len_s = len(s)
len_t = len(t)

s_counter= [0]*(len_s+1)
s_temp = 0
for i in range(len_s):
	if s[i] == "A":
		s_temp += 1
	s_counter[i+1] = s_temp
	
t_counter= [0]*(len_t+1)
t_temp = 0
for i in range(len_t):
	if t[i] == "A":
		t_temp += 1
	t_counter[i+1] = t_temp

for _ in range(q):
	a, b, c, d = map(int, input().split())
	
	x = s_counter[b]-s_counter[a-1]
	y = t_counter[d]-t_counter[c-1]
	print(x,y)
	print(['NO', 'YES'][((x+b-a+1)-(y+d-c+1))%3==0])

Submission status: Wrong Answer

Solution code:
def main():
    S = list(str(input()))
    T = list(str(input()))
    q = int(input())
    S_cum = [0]
    T_cum = [0]
    for i in S:
        if i == "A":
            S_cum.append((S_cum[-1]+1)%3)
        else:
            S_cum.append((S_cum[-1]+2)%3)
    for i in T:
        if i == "A":
            T_cum.append((T_cum[-1]+1)%3)
        else:
            T_cum.append((T_cum[-1]+2)%3)
    for i in range(q):
        a,b,c,d = map(int,input().split())
        s_ = S_cum[b]-S_cum[a-1]
        t_ = T_cum[d]-T_cum[c-1]
        if s_%3 == t_%3:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
F = sys.stdin
S = F.readline().strip("\n")
T = F.readline().strip("\n")

def operate(i, j):
    if i == "": return j
    elif i == "A":
        if j == "": return "A"
        elif j == "A": return "B"
        else: return ""
    else:
        if j == "": return "B"
        elif j == "A": return ""
        else: return "B"

def initialize(L):
    d, length = 2, len(L)
    while d < length:
        d *= 2
    BT = [""] * (2 * d - 1)
    for i in range(length):
        K = d + i -1
        BT[d + i - 1] = L[i]
        while K > 0:
            K = (K - 1)//2
            BT[K] = operate(BT[2 * K + 1], BT[2 * K + 2])
    return BT

def Search(i, j, l, r, level, BT):
    if r < i or j < l: return ""
    elif i <= l <= r <= j: return BT[level]
    else:
        sl = Search(i, j, l, (l+r)//2, 2*level+1, BT)
        sr = Search(i, j, (l+r)//2 + 1, r, 2*level+2, BT)
        ans = operate(sl, sr)
        return ans


ST, TT = initialize(S), initialize(T)
maxS, maxT = len(ST)//2, len(TT)//2
Ans = ""
Q = int(F.readline().strip("\n"))
for _ in range(Q):
    a, b, c, d = map(int, F.readline().strip("\n").split(" "))
    if Search(a-1, b-1, 0, maxS, 0, ST) == Search(c-1, d-1, 0, maxT, 0, TT): Ans += "YES\n"
    else: Ans += "NO\n"
print(Ans)

Submission status: Wrong Answer

Solution code:
import math
inp=lambda:map(int,input().split())
s=input()
t=input()
q=int(input())
for _ in range(q):
	a,b,c,d=inp()
	if abs((s[a:b].count('A')-s[a:b].count('B')))==abs((t[a:b].count('A')-t[a:b].count('B')))%3:
		print('YES')
	else:
		print('NO')

Submission status: Wrong Answer

Solution code:
import math
inp=lambda:map(int,input().split())
s=input()
t=input()
q=int(input())
for _ in range(q):
	a,b,c,d=inp()
	if abs((s[a:b].count('A')-s[a:b].count('B')))==abs((t[a:b].count('A')-t[a:b].count('B'))):
		print('YES')
	else:
		print('NO')

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
N = len(S)
M = len(T)
Ss = [0]*(N+1)
Ts = [0]*(M+1)
for i in range(N):
  if S[i] == "A":
    temp = 1
  else:
    temp = -1
  Ss[i+1] = Ss[i] + temp
for i in range(M):
  if T[i] == "A":
    temp = 1
  else:
    temp = -1
  Ts[i+1] = Ts[i] + temp
Q = int(input())
for i in range(Q):
  a, b, c, d = (int(i) for i in input().split())
  if a == b:
    print("NO")
  else:
    if (Ss[b] - Ss[a-1] - Ts[d] + Ts[c-1])%3==0:
      print("YES")
    else:
      print("NO")

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
N = len(S)
M = len(T)
Ss = [0]*(N+1)
Ts = [0]*(M+1)
for i in range(N):
  if S[i] == "A":
    temp = 1
  else:
    temp = -1
  Ss[i+1] = Ss[i] + temp
for i in range(M):
  if T[i] == "A":
    temp = 1
  else:
    temp = -1
  Ts[i+1] = Ts[i] + temp
Q = int(input())
for i in range(Q):
  a, b, c, d = (int(i) for i in input().split())
  if a == b:
    print("NO")
    continue
  else:
    if (Ss[b] - Ss[a-1] - Ts[d] + Ts[c-1])%3==0:
      print("YES")
    else:
      print("NO")

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
q = int(input())

s = [0]
t = [0]
v = 0
for c in S:
	v = (v + (ord(c) - ord("A") + 1)) % 3
	s.append(v)
v = 0
for c in T:
	v = (v + (ord(c) - ord("A") + 1)) % 3
	t.append(v)
print(s)
print(t)
for i in range(q):
	a,b,c,d = map(int, input().split())
	x = (3 + s[b] - s[a-1]) % 3
	y = (3 + t[d] - t[c-1]) % 3
	if x == y:
		print("YES")
	else:
		print("NO")

Submission status: Wrong Answer

Solution code:
S = input()
T = input()
q = int(input())

s = [0]
t = [0]
v = 0
for c in S:
	v = (v + (ord(c) - ord("A") + 1)) % 3
	s.append(v)
v = 0
for c in T:
	v = (v + (ord(c) - ord("A") + 1)) % 3
	t.append(v)

for i in range(q):
	a,b,c,d = map(int, input().split())
	x = (3 + s[b] - s[a-1]) % 3
	y = (3 + t[d] - s[c-1]) % 3
	if x == y:
		print("YES")
	else:
		print("NO")

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def restore(s):
    while len(s) > 1:
        s = s.replace("AA", "B")
        s = s.replace("BB", "A")
        s = s.replace("AB", "")
        s = s.replace("BA", "")
    return s


S = input()
T = input()
q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    r_s = restore(S[a - 1 : b])
    r_t = restore(T[c - 1 : d])
    print("YES") if r_s == r_t else print("NO")

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def restore(s):
    s = s.replace("AAA", "")
    s = s.replace("BBB", "")
    while len(s) > 1:
        s = s.replace("AA", "B")
        s = s.replace("BB", "A")
        s = s.replace("AB", "")
        s = s.replace("BA", "")
    return s


S = input()
T = input()
q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    r_s = restore(S[a - 1 : b])
    r_t = restore(T[c - 1 : d])
    print("YES") if r_s == r_t else print("NO")

Submission status: Time Limit Exceeded

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


s,t=input(),input()
q=int(input())
abcd=[list(map(int,input().split())) for i in range(q)]


for i in range(q):
    a,b,c,d=abcd[i]
    ss,tt=s[a-1:b],t[c-1:d]
    scnt=ss.count("A")-ss.count("B")
    tcnt=tt.count("A")-tt.count("B")
    if abs(scnt-tcnt)%3==0:
        print("YES")
    else:
        print("NO")

Submission status: Time Limit Exceeded

Solution code:
from operator import add


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


S = input()
T = input()
treeS = SegTree(len(S), 0)
treeT = SegTree(len(T), 0)
treeS.set_list([1 if s=="A" else 0 for s in S])
treeT.set_list([1 if s=="A" else 0 for s in T])

q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    sa = treeS.get(a-1, b)
    sb = b-a+1-sa
    ta = treeT.get(c-1, d)
    tb = d-c+1-ta

    if (2*(sb-sa)+tb-ta)%3 or (sb-sa+2*(tb-ta))%3:
        print("NO")
    else:
        print("YES")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

s = input()
t = input()
q = int(input())
abcd = [list(map(int, input().split())) for _ in range(q)]

rmv = ["AAA", "BBB", "AB", "BA"]

dct = {"": 0, "A": 1, "B": 2, "AA": 2, "BB": 1}


class Hoge:
    def __init__(self, word):
        ln = len(word)
        self.n = 1
        while self.n < ln:
            self.n *= 2

        self.data = [""] * (2 * self.n - 1)
        for i, e in enumerate(word, self.n - 1):
            self.data[i] = e

        for i in range(self.n - 2, -1, -1):
            l = i * 2 + 1
            r = i * 2 + 2
            self.data[i] = self.data[l] + self.data[r]
            for e in rmv:
                for _ in range(2):
                    self.data[i] = self.data[i].replace(e, "")

    def make(self, begin, end, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if r <= begin or end <= l:
            return ""

        if begin <= l and r <= end:
            return self.data[i]

        wl = self.make(begin, end, i * 2 + 1, l, (l + r) // 2)
        wr = self.make(begin, end, i * 2 + 2, (l + r) // 2, r)
        ret = wl + wr
        for e in rmv:
            for _ in range(2):
                ret = ret.replace(e, "")
        return ret


ss = Hoge(s)
tt = Hoge(t)

for a, b, c, d in abcd:
    sss = ss.make(a - 1, b)
    ttt = tt.make(c - 1, d)
    if dct[sss] == dct[ttt]:
        print("YES")
    else:
        print("NO")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

s = input()
t = input()
q = int(input())
abcd = [list(map(int, input().split())) for _ in range(q)]

rmv = ["AAA", "BBB", "AB", "BA"]

dct = {"": 0, "A": 1, "B": 2, "AA": 2, "BB": 1}


def f(word):
    ln = len(word)
    n = 1
    while n < ln:
        n *= 2

    li = [""] * (2 * n - 1)
    for i, e in enumerate(word, n - 1):
        li[i] = e

    for i in range(n - 2, -1, -1):
        l = i * 2 + 1
        r = i * 2 + 2
        li[i] = li[l] + li[r]
        for e in rmv:
            for _ in range(2):
                li[i] = li[i].replace(e, "")

    return li, n


def make(data, begin, end, i, l, r):
    if r <= begin or end <= l:
        return ""

    if begin <= l and r <= end:
        return data[i]

    wl = make(data, begin, end, i * 2 + 1, l, (l + r) // 2)
    wr = make(data, begin, end, i * 2 + 2, (l + r) // 2, r)
    ret = wl + wr
    for e in rmv:
        for _ in range(2):
            ret = ret.replace(e, "")
    return ret


ss, sr = f(s)
tt, tr = f(t)

for a, b, c, d in abcd:
    sss = make(ss, a - 1, b, 0, 0, sr)
    ttt = make(tt, c - 1, d, 0, 0, tr)
    if dct[sss] == dct[ttt]:
        print("YES")
    else:
        print("NO")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

s = input()
t = input()
q = int(input())
abcd = [list(map(int, input().split())) for _ in range(q)]

rmv = ["AAA", "BBB", "AB", "BA"]

dct = {"": 0, "A": 1, "B": 2, "AA": 2, "BB": 1}


def f(word):
    ln = len(word)
    n = 1
    while n < ln:
        n *= 2

    li = [""] * (2 * n - 1)
    for i, e in enumerate(word, n - 1):
        li[i] = e

    for i in range(n - 2, -1, -1):
        l = i * 2 + 1
        r = i * 2 + 2
        li[i] = li[l] + li[r]
        for e in rmv:
            li[i] = li[i].replace(e, "")

    return li, n


def make(data, begin, end, i, l, r):
    if r <= begin or end <= l:
        return ""

    if begin <= l and r <= end:
        return data[i]

    wl = make(data, begin, end, i * 2 + 1, l, (l + r) // 2)
    wr = make(data, begin, end, i * 2 + 2, (l + r) // 2, r)
    ret = wl + wr
    for e in rmv:
        ret = ret.replace(e, "")
    return ret


ss, sr = f(s)
tt, tr = f(t)

for a, b, c, d in abcd:
    sss = make(ss, a - 1, b, 0, 0, sr)
    ttt = make(tt, c - 1, d, 0, 0, tr)
    if sss not in dct.keys() or ttt not in dct.keys():
        print("foo")
    elif dct[sss] == dct[ttt]:
        print("YES")
    else:
        print("NO")

Submission status: Time Limit Exceeded

Solution code:
S=input();T=input()
q=int(input())
for i in range(q):
    a,b,c,d=map(int,input().split())
    sc=S[a-1:b].count("A")
    sa=sc-(b-a+1-sc)
    tc=T[c-1:d].count("A")
    ta=tc-(d-c+1-tc)
    if sa%3==ta%3:
        print("YES")
    else:
        print("NO")

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
q = int(input())
abcd = [tuple(map(int,input().split())) for i in range(q)]

def to_one(word):


    word = word.replace('AAA', '')
    word = word.replace('BBB', '')

    word = word.replace('AB', '')
    word = word.replace('BA', '')

    word = word.replace('AA', 'B')
    word = word.replace('BB', 'A')

    word = word.replace('AAA', '')
    word = word.replace('BBB', '')

    word = word.replace('AB', '')
    word = word.replace('BA', '')

    if len(word)==0:
            return 'C'

    if len(word)==1:
        return word


for a,b,c,d in abcd:

    s_i = s[a-1:b]
    t_i = t[c-1:d]

    if to_one(s_i) == to_one(t_i):
        print('YES')
    else:
        print('NO')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

s = input()
t = input()
q = int(input())
abcd = [tuple(map(int,input().split())) for i in range(q)]

def to_one(word):
    if len(word)==0:
        return 'C'

    if len(word)==1:
        return word

    word = word.replace('AAA', '')
    word = word.replace('BBB', '')

    word = word.replace('AB', '')
    word = word.replace('BA', '')

    word = word.replace('AA', 'B')
    word = word.replace('BB', 'A')

    return to_one(word)


for a,b,c,d in abcd:

    s_i = s[a-1:b]
    t_i = t[c-1:d]

    if to_one(s_i) == to_one(t_i):
        print('YES')
    else:
        print('NO')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

s = input()
t = input()
q = int(input())
abcd = [tuple(map(int,input().split())) for i in range(q)]

def to_one(word):
    if len(word)==0:
        return 0

    if len(word)==1:
        return word

    if word[:2] == 'AB' or word[:2] == 'BA':
        return to_one(word[2:])

    if word[:3] == 'AAA':
        return to_one(word[3:])

    if word[:3] == 'BBB':
        return to_one(word[3:])

    if word[:2] == 'AA':
        return to_one('B'+word[2:])
    if word[:2] == 'BB':
        return to_one('A'+word[2:])


for a,b,c,d in abcd:

    s_i = s[a-1:b]
    t_i = t[c-1:d]

    if to_one(s_i) == to_one(t_i):
        print('YES')
    else:
        print('NO')

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
q = int(input())

for _ in range(q):
	a, b, c, d = map(int, input().split())
	
	x = s[a-1:b].count('A')
	y = t[c-1:d].count('A')
	
	print(['NO', 'YES'][((x+b-a+1)-(y+d-c+1))%3==0])

Submission status: Time Limit Exceeded

Solution code:
def checker(x,y):
	count_x_a = x.count('A')
	count_y_a = y.count('A')
	
	len_x = count_x_a*2 + (len(x)-count_x_a)
	len_y = count_y_a*2 + (len(y)-count_y_a)
	return (len_x-len_y)%3 == 0
	
s = input()
t = input()
q = int(input())

for _ in range(q):
	a, b, c, d = map(int, input().split())
	
	x = s[a-1:b]
	y = t[c-1:d]
	
	print(['NO', 'YES'][checker(x,y)])

Submission status: Time Limit Exceeded

Solution code:
def checker(x,y):
	new_x = ''
	for ch in list(x):
		if ch == 'A':
			new_x += 'BB'
		else:
			new_x += 'B'
	
	new_y = ''
	for ch in list(y):
		if ch == 'A':
			new_y += 'BB'
		else:
			new_y += 'B'
	
	len_x = len(new_x)
	len_y = len(new_y)
	
	return (len_x-len_y)%3 == 0
s = input()
t = input()
q = int(input())

for _ in range(q):
	a, b, c, d = map(int, input().split())
	
	x = s[a-1:b]
	y = t[c-1:d]
	
	print(['NO', 'YES'][checker(x,y)])

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    def __init__(self,N,f,ini):
        """
        f(val,ini)=ini
        """
        n=1
        while n<N: n<<=1
        self.n=n
        self.arr=[ini]*(2*n-1)
        self.f,self.ini=f,ini
    
    def update(self,i,val):
        i += self.n-1
        self.arr[i]=val
        while i>0:
            i=(i-1)//2
            self.arr[i]=self.f(self.arr[2*i+1],self.arr[2*i+2])

    def find(self,s,t):
        """
        [s,t)
        """
        return self.__find(s,t,0,0,self.n)

    def __find(self,s,t,k,l,r):
        if t<=l or s>=r: return self.ini
        if s<=l and t>=r: return self.arr[k]
        vl=self.__find(s,t,2*k+1,l,(l+r)//2)
        vr=self.__find(s,t,2*k+2,(l+r)//2,r)
        return self.f(vl,vr)

def f(c1, c2):
    cc = c1+c2
    if len(cc)==1: return cc
    if cc=="AA": return "B"
    if cc=="BB": return "A"
    return ""

S=input()
T=input()
Q=int(input())

sts = SegTree(len(S), f, "")
stt = SegTree(len(T), f, "")
for i,c in enumerate(S):
    sts.update(i,c)
for i,c in enumerate(T):
    stt.update(i,c)

for _ in range(Q):
    a,b,c,d = map(int,input().split())
    print("YES" if sts.find(a-1,b)==stt.find(c-1,d) else "NO")

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    cnts = cntt = 0
    for i in range(a-1, b):
        cnts += 1 if s[i] == 'A' else 2
    for i in range(c-1, d):
        cntt += 1 if t[i] == 'A' else 2
    print("YES" if cnts%3 == cntt%3 else "NO")

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
sl = [0]*(ls+1)
tl = [0]*(lt+1)
def g(x):
  if x == "A":
    return 1
  else:
    return 2
for i in range(ls):
  sl[i+1] = sl[i] + g(s[i])
for i in range(lt):
  tl[i+1] = tl[i] + g(t[i])
for _ in range(int(input())):
  a,b,c,d = map(int, input().split())
  if (sl[b]-tl[d]-sl[a-1]+tl[c-1])%3 == 0:
    print("YES")
  else:
    print("NO")

Submission status: Time Limit Exceeded

Solution code:
import sys
F = sys.stdin
S = list(map(int, list(F.readline().replace("A", "1").replace("B", "2").strip("\n"))))
T = list(map(int, list(F.readline().replace("A", "1").replace("B", "2").strip("\n"))))

sSum = [0] * (len(S)+1)
tSum = [0] * (len(T)+1)
for i in range(len(S)):
    sSum[i+1] = sSum[i] + S[i]
for i in range(len(T)):
    tSum[i+1] = tSum[i] + T[i]

Ans = ""
Q = int(F.readline().strip("\n"))
for _ in range(Q):
    a, b, c, d = map(int, F.readline().strip("\n").split(" "))
    if (sSum[b] - sSum[a-1]) % 3 == (tSum[d] - tSum[c-1]) % 3: Ans += "YES\n"
    else: Ans += "NO\n"
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
F = sys.stdin
S = list(map(int, list(F.readline().replace("A", "1").replace("B", "2").strip("\n"))))
T = list(map(int, list(F.readline().replace("A", "1").replace("B", "2").strip("\n"))))

def initialize(L):
    d, length = 2, len(L)
    while d < length:
        d *= 2
    BT = [0] * (2 * d - 1)
    for i in range(length):
        K = d + i -1
        BT[d + i - 1] = L[i]
        while K > 0:
            K = (K - 1)//2
            BT[K] = (BT[2 * K + 1] + BT[2 * K + 2]) % 3
    return BT

def Search(i, j, l, r, level, BT):
    if r < i or j < l: return 0
    elif i <= l <= r <= j: return BT[level]
    else:
        sl = Search(i, j, l, (l+r)//2, 2*level+1, BT)
        sr = Search(i, j, (l+r)//2 + 1, r, 2*level+2, BT)
        return (sl + sr) % 3


ST, TT = initialize(S), initialize(T)
maxS, maxT = len(ST)//2, len(TT)//2
Ans = ""
Q = int(F.readline().strip("\n"))
for _ in range(Q):
    a, b, c, d = map(int, F.readline().strip("\n").split(" "))
    if Search(a-1, b-1, 0, maxS, 0, ST) == Search(c-1, d-1, 0, maxT, 0, TT): Ans += "YES\n"
    else: Ans += "NO\n"
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
F = sys.stdin
S = F.readline().strip("\n")
T = F.readline().strip("\n")

def operate(i, j):
    group = {i, j}
    if group == {"A"}: return "B"
    elif group == {"B"}: return "A"
    elif group == {""}: return ""
    elif group == {"", "A"}: return "A"
    elif group == {"", "B"}: return "B"
    elif group == {"A", "B"}: return ""

def initialize(L):
    d, length = 2, len(L)
    while d < length:
        d *= 2
    BT = [""] * (2 * d - 1)
    for i in range(length):
        K = d + i -1
        BT[d + i - 1] = L[i]
        while K > 0:
            K = (K - 1)//2
            BT[K] = operate(BT[2 * K + 1], BT[2 * K + 2])
    return BT

def Search(i, j, l, r, level, BT):
    if r < i or j < l: return ""
    elif i <= l <= r <= j: return BT[level]
    else:
        sl = Search(i, j, l, (l+r)//2, 2*level+1, BT)
        sr = Search(i, j, (l+r)//2 + 1, r, 2*level+2, BT)
        ans = operate(sl, sr)
        return ans


ST, TT = initialize(S), initialize(T)
maxS, maxT = len(ST)//2, len(TT)//2
Ans = ""
Q = int(F.readline().strip("\n"))
for _ in range(Q):
    a, b, c, d = map(int, F.readline().strip("\n").split(" "))
    if Search(a-1, b-1, 0, maxS, 0, ST) == Search(c-1, d-1, 0, maxT, 0, TT): Ans += "YES\n"
    else: Ans += "NO\n"
print(Ans)