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: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    x = S()
    s = 0
    ans = len(x)
    for i in x:
        if i == "S":
            s += 1
        else:
            if s > 0:
                s -= 1
                ans -= 2
    print(ans)
    return

#B
def B():
    n = I()
    a = LI()
    f = [0 for i in range(n+1)]
    for i in range(n):
        f[a[i]] = i
    l = [i for i in range(n+1)]
    r = [i for i in range(n+1)]
    ans = 0
    for i in range(1,n+1)[::-1]:
        j = f[i]
        ans += (j-l[j]+1)*(r[j]-j+1)*i
        l[r[j]+1] = l[j]
        r[l[j]-1] = r[j]
    print(ans)
    return

#C
def C():
    n,x = LI()
    if x == 1 or x == 2*n-1:
        print("No")
        quit()
    else:
        ans = [i+1 for i in range(2*n-1)]
        k = x-n
        if k < 0:
            ans = ans[2*n-1+k:]+ans[:2*n-1+k]
        if k > 0:
            ans = ans[k:]+ans[:k]
        print("Yes")
        for i in ans:
            print(i)
    return

#D
def D():
    s = S()
    t = S()
    n = len(s)
    m = len(t)
    fs = [1 if s[i] == "A" else 2 for i in range(n)]
    ft = [1 if t[i] == "A" else 2 for i in range(m)]
    for i in range(n-1):
        fs[i+1] += fs[i]
        fs[i+1] %= mod
    for i in range(m-1):
        ft[i+1] += ft[i]
        ft[i+1] %= mod
    fs.insert(0,0)
    ft.insert(0,0)
    q = I()
    for i in range(q):
        a,b,c,d = LI()
        a -= 1
        c -= 1
        if (fs[b]-fs[a])%3 == (ft[d]-ft[c])%3:
            print("YES")
        else:
            print("NO")
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

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

q = int(input())

SA = [0]
SB = [0]
TA = [0]
TB = [0]

sa=0
sb=0
ta=0
tb=0

for i in range(len(S)):
    if S[i]=="A":
        sa+=1
    elif S[i]=="B":
        sb+=1
    SA.append(sa)
    SB.append(sb)
    

for i in range(len(T)):
    if T[i]=="A":
        ta+=1
    elif T[i]=="B":
        tb+=1
    TA.append(ta)
    TB.append(tb)

for i in range(q):
    a,b,c,d = list(map(int,input().split()))
    sa_num=SA[b]-SA[a-1]
    sb_num=SB[b]-SB[a-1]
    ta_num=TA[d]-TA[c-1]
    tb_num=TB[d]-TB[c-1]
    if (sa_num+2*sb_num)%3==(ta_num+2*tb_num)%3:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)
sl = [0]*(ls+1)
tl = [0]*(lt+1)
for i in range(ls):
  if s[i] == "A":
    sl[i+1] = sl[i] + 1
  else:
    sl[i+1] = sl[i] + 2
for i in range(lt):
  if t[i] == "A":
    tl[i+1] = tl[i] + 1
  else:
    tl[i+1] = tl[i] + 2
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: Accepted

Solution code:
import sys
F = sys.stdin
S = F.readline().replace("A", "1").replace("B", "2").strip("\n")
T = 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] + int(S[i])
for i in range(len(T)):
    tSum[i+1] = tSum[i] + int(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: Accepted

Solution code:
import sys
input = sys.stdin.readline
s = list(input())
t = list(input())

snum = [(0,0)] #snum[j]-snum[i-1]:i-j文字目に含まれる(A,B)の数
for i in range(len(s)):
    if s[i] == 'A':
        snum.append((snum[-1][0]+1,snum[-1][1]))
    else:
        snum.append((snum[-1][0],snum[-1][1]+1))

tnum = [(0,0)]
for i in range(len(t)):
    if t[i] == 'A':
        tnum.append((tnum[-1][0]+1,tnum[-1][1]))
    else:
        tnum.append((tnum[-1][0],tnum[-1][1]+1))

q = int(input())
for i in range(q):
    a,b,c,d = map(int,input().split())
    sa = snum[b][0]-snum[a-1][0]
    sb = snum[b][1]-snum[a-1][1]
    ta = tnum[d][0]-tnum[c-1][0]
    tb = tnum[d][1]-tnum[c-1][1]
    
    #全てbにする
    b1 = sb+sa*2
    b2 = tb+ta*2
    if abs(b2-b1)%3==0:
        print('YES')
        continue
    
    
    print('NO')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
s, t, q = list(input()), list(input()), int(input())
ssum, tsum = [0], [0]
for i in range(len(s)):
    if s[i]=="A": ssum.append(ssum[-1]+1)
    else: ssum.append(ssum[-1]+2)
for i in range(len(t)):
    if t[i]=="A": tsum.append(tsum[-1]+1)
    else: tsum.append(tsum[-1]+2)
for i in range(q):
    a,b,c,d = map(int,input().split())
    sa = (ssum[b]-ssum[a-1])-(tsum[d]-tsum[c-1])
    if abs(sa)%3==0:print("YES")
    else: print("NO")

Submission status: Accepted

Solution code:
s, t, q = list(input()), list(input()), int(input())
ssum, tsum = [0], [0]
for i in range(len(s)):
    if s[i]=="A": ssum.append(ssum[-1]+1)
    else: ssum.append(ssum[-1]+2)
for i in range(len(t)):
    if t[i]=="A": tsum.append(tsum[-1]+1)
    else: tsum.append(tsum[-1]+2)
for i in range(q):
    a,b,c,d = map(int,input().split())
    sa = (ssum[b]-ssum[a-1])-(tsum[d]-tsum[c-1])
    if abs(sa)%3==0:print("YES")
    else: print("NO")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
s = list(input())
t = list(input())

snum = [(0,0)] #snum[j]-snum[i-1]:i-j文字目に含まれる(A,B)の数
for i in range(len(s)):
    if s[i] == 'A':
        snum.append((snum[-1][0]+1,snum[-1][1]))
    else:
        snum.append((snum[-1][0],snum[-1][1]+1))

tnum = [(0,0)]
for i in range(len(t)):
    if t[i] == 'A':
        tnum.append((tnum[-1][0]+1,tnum[-1][1]))
    else:
        tnum.append((tnum[-1][0],tnum[-1][1]+1))

q = int(input())
for i in range(q):
    a,b,c,d = map(int,input().split())
    sa = snum[b][0]-snum[a-1][0]
    sb = snum[b][1]-snum[a-1][1]
    ta = tnum[d][0]-tnum[c-1][0]
    tb = tnum[d][1]-tnum[c-1][1]
    
    #全てbにする
    b1 = sb+sa*2
    b2 = tb+ta*2
    if abs(b2-b1)%3==0:
        print('YES')
        continue
    
    #全てaにする
    a1 = sa+sb*2
    a2 = ta+tb*2
    if abs(a2-a1)%3==0:
        print('YES')
        continue
    
    print('NO')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
s = list(input())
t = list(input())

snum = [(0,0)] #snum[j]-snum[i-1]:i-j文字目に含まれる(A,B)の数
for i in range(len(s)):
    if s[i] == 'A':
        snum.append((snum[-1][0]+1,snum[-1][1]))
    else:
        snum.append((snum[-1][0],snum[-1][1]+1))

tnum = [(0,0)]
for i in range(len(t)):
    if t[i] == 'A':
        tnum.append((tnum[-1][0]+1,tnum[-1][1]))
    else:
        tnum.append((tnum[-1][0],tnum[-1][1]+1))

q = int(input())
for i in range(q):
    a,b,c,d = map(int,input().split())
    sa = snum[b][0]-snum[a-1][0]
    sb = snum[b][1]-snum[a-1][1]
    ta = tnum[d][0]-tnum[c-1][0]
    tb = tnum[d][1]-tnum[c-1][1]
    
    #全てbにする
    b1 = sb+sa*2
    b1 += max(tb-b1,0)//3*3+3
    a1 = (b1-tb)*2
    if abs(a1-ta)%3==0:
        print('YES')
        continue
    
    #全てaにする
    a2 = sa+sb*2
    a2 += max(ta-a2,0)//3*3+3
    b2 = (a2-ta)*2
    if abs(b2-tb)%3==0:
        print('YES')
        continue
    
    print('NO')

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = ns()
t = ns()
q = ni()

sa = [0]
sb = [0]
ta = [0]
tb = [0]

for si in s:
    if si == "A":
        sa.append(sa[-1] + 1)
        sb.append(sb[-1])
        
    else:
        sa.append(sa[-1])
        sb.append(sb[-1] + 1)
        
for ti in t:
    if ti == "A":
        ta.append(ta[-1] + 1)
        tb.append(tb[-1])
        
    else:
        ta.append(ta[-1])
        tb.append(tb[-1] + 1)
        
for _ in range(q):
    a,b,c,d = li()
    
    sanum = sa[b] - sa[a-1]
    sbnum = sb[b] - sb[a-1]
    
    tanum = ta[d] - ta[c-1]
    tbnum = tb[d] - tb[c-1]
    
    sanum += 2*sbnum
    tanum += 2*tbnum
    
    if sanum%3 == tanum%3:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

astr = input()
bstr = input()
n = getN()
queries = []
for i in range(n):
    queries.append(getlist())
s1 = 1 if astr[0] == "A" else 2
t1 = 1 if bstr[0] == "A" else 2
s_acc = [0]
t_acc = [0]
tmp = 0
for s in astr:
    if s == "A":
        s_acc.append(s_acc[-1] + 1)
    else:
        s_acc.append(s_acc[-1] + 2)

for s in bstr:
    if s == "A":
        t_acc.append(t_acc[-1] + 1)
    else:
        t_acc.append(t_acc[-1] + 2)


for q in queries:
    x,y,z,w = q

    if (s_acc[y] - s_acc[x-1]) % 3 == (t_acc[w] - t_acc[z-1])%3:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

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 (Ss[b] - Ss[a-1] - Ts[d] + Ts[c-1])%3==0:
    print("YES")
  else:
    print("NO")

Submission status: Accepted

Solution code:
S=input()
T=input()
q=int(input())
table=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    a,b,c,d=a-1,b-1,c-1,d-1
    table.append((a,b,c,d))
N=len(S)
M=len(T)
A=[[0]*(N+1) for i in range(2)]
B=[[0]*(N+1) for i in range(2)]
for i in range(1,N+1):
    if S[i-1]=='A':
        A[0][i]+=A[0][i-1]+1
        A[1][i]+=A[1][i-1]
    else:
        A[0][i]+=A[0][i-1]
        A[1][i]+=A[1][i-1]+1
for i in range(1,M+1):
    if T[i-1]=='A':
        B[0][i]+=B[0][i-1]+1
        B[1][i]+=B[1][i-1]
    else:
        B[0][i]+=B[0][i-1]
        B[1][i]+=B[1][i-1]+1
#print(A)
#print(B)
for i in range(q):
    a,b,c,d = table[i]
    #print(S[a:b+1])
    #print(T[c:d+1])
    x=A[0][b+1]-A[0][a]
    y=A[1][b+1]-A[1][a]
    z=B[0][d+1]-B[0][c]
    w=B[1][d+1]-B[1][c]
    #print(x,y,z,w)
    if (x+2*y)%3==(z+2*w)%3:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
s = input()
t = input()
q = int(input())
xa = [0]*len(s)+[0]
xb = [0]*len(s)+[0]
ya = [0]*len(t)+[0]
yb = [0]*len(t)+[0]
for i in range(len(s)):
  if s[i] == "A":
    xa[i+1] = xa[i] + 1
    xb[i+1] = xb[i]
  else:
    xa[i+1] = xa[i] 
    xb[i+1] = xb[i] + 1
for i in range(len(t)):
  if t[i] == "A":
    ya[i+1] = ya[i] + 1
    yb[i+1] = yb[i]
  else:
    ya[i+1] = ya[i] 
    yb[i+1] = yb[i] + 1
for i in range(q):
  a,b,c,d = map(int,input().split())
  sa = (xa[b] -xa[a-1]) %3
  sb = (xb[b] -xb[a-1]) %3
  ta = (ya[d] -ya[c-1]) %3
  tb = (yb[d] -yb[c-1]) %3
  if [(sa-1)%3,(sb+2)%3] == [ta,tb] or [(sa+2)%3,(sb-1)%3] == [ta,tb] or [sa,sb] == [ta,tb] or [(sa-2)%3,(sb+4)%3] == [ta,tb] or [(sa+4)%3,(sb-2)%3] == [ta,tb]:
    print("YES")
  else:
    print("NO")

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

S=input()
T=input()
s=[0 for i in range(len(S))]
for i in range(len(s)):
 if S[i]=="B":
    s[i]=2
 else:
    s[i]=1

t=[0 for i in range(len(T))]
for i in range(len(t)):
 if T[i]=="B":
    t[i]=2
 else:
    t[i]=1
for i in range(len(s)-1):
   s[i+1]+=s[i]
for i in range(len(t)-1):
   t[i+1]+=t[i]
q=i1()
s=[0]+s
t=[0]+t
for i in range(q):
 [a,b,c,d]=i2()
 if (s[b]-s[a-1])%3==(t[d]-t[c-1])%3:
    print("YES")
 else:
    print("NO")

Submission status: Accepted

Solution code:
s=input()
t=input()
S,T=[0],[0]
for i in range(len(s)):
  if s[i]=="A":
    S.append((S[-1]+1)%3)
  elif s[i]=="B":
    S.append((S[-1]+2)%3)
for i in range(len(t)):
  if t[i]=="A":
    T.append((T[-1]+1)%3)
  elif t[i]=="B":
    T.append((T[-1]+2)%3)
    
Q=int(input())
for q in range(Q):
  a,b,c,d=map(int,input().split())
  if (S[b]-S[a-1])%3==(T[d]-T[c-1])%3:
    print("YES")
  else:
    print("NO")

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

S = input()
T = input()
typeS = [0 for _ in range(1+len(S))]
typeT = [0 for _ in range(1+len(T))]
typeS[0] = typeT[0] = 0 
for i in range(len(S)):
    ctr = 2
    if S[i] == 'A':
        ctr = 1
    typeS[i+1] = (typeS[i] + ctr)%3
for i in range(len(T)):
    ctr = 2
    if T[i] == 'A':
        ctr = 1
    typeT[i+1] = (typeT[i] + ctr)%3
Q = int(input())
for _ in range(Q):
    a, b, c, d = inpl()
    if (typeS[b] - typeS[a-1])%3 == (typeT[d] -typeT[c-1])%3:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
s = input()
t = input()
q = int(input())
sl,tl = len(s),len(t)
sa,sb,ta,tb = [0]*(sl+1),[0]*(sl+1),[0]*(tl+1),[0]*(tl+1)
for i in range(sl):
	if s[i]=="A": sa[i+1],sb[i+1] = sa[i]+1,sb[i]
	else: sa[i+1],sb[i+1] = sa[i],sb[i]+1
for i in range(tl):
	if t[i]=="A": ta[i+1],tb[i+1] = ta[i]+1,tb[i]
	else: ta[i+1],tb[i+1] = ta[i],tb[i]+1
for _ in range(q):
	a,b,c,d = (int(i) for i in input().split())
	if (sa[b]-sa[a-1]-sb[b]+sb[a-1]-ta[d]+ta[c-1]+tb[d]-tb[c-1])%3: print("NO")
	else: print("YES")

Submission status: Accepted

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

ms = [0]
for s in S:
    if s == 'A':
        ms.append(ms[-1] + 1)
    else:
        ms.append(ms[-1] - 1)

mt = [0]
for t in T:
    if t == 'A':
        mt.append(mt[-1] + 1)
    else:
        mt.append(mt[-1] - 1)

q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    if (ms[b] - ms[a - 1]) % 3 == (mt[d] - mt[c - 1]) % 3:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
S = input()
T = input()
def sign(s):
    if len(s)==1:
        return s
    elif s=="AA":
        return "B"
    elif s in ["AB", "BA"]:
        return ""
    elif s=="BB":
        return "A"

def diff(a, b):
    if b=="":
        return a
    elif b==a:
        return ""
    elif a=="":
        if b=="A":
            return "B"
        elif b=="B":
            return "A"
    else:
        return b

a = ""
Sn = [""]
for s in S:
    a = sign(a+s)
    Sn.append(a)
a = ""
Tn = [""]
for t in T:
    a = sign(a+t)
    Tn.append(a)

q = int(input())
for i in range(q):
    a, b, c, d = map(int, input().split())
    if diff(Sn[b], Sn[a-1]) == diff(Tn[d], Tn[c-1]):
        print("YES")
    else:
        print("NO")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S, T, ABCD):

    S_ = [0]
    for c in S:
        S_.append((1 if c == 'A' else 2) + S_[-1])
    T_ = [0]
    for c in T:
        T_.append((1 if c == 'A' else 2) + T_[-1])

    for a, b, c, d in ABCD:
        s = (S_[b]-S_[a-1]) % 3
        t = (T_[d]-T_[c-1]) % 3
        if s == t:
            print('YES')
        else:
            print('NO')


def main():
    S = read_str()
    T = read_str()
    q = read_int()
    ABCD = [read_int_n() for _ in range(q)]
    slv(S, T, ABCD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
T = input()
S_a, S_b = [0], [0]
T_a, T_b = [0], [0]

for s in S:
    if s == "A":
        S_a.append(S_a[-1] + 1)
        S_b.append(S_b[-1])
    if s == "B":
        S_a.append(S_a[-1])
        S_b.append(S_b[-1] + 1)

for t in T:
    if t == "A":
        T_a.append(T_a[-1] + 1)
        T_b.append(T_b[-1])
    if t == "B":
        T_a.append(T_a[-1])
        T_b.append(T_b[-1] + 1)


def calc(na, nb):
    if na > nb:
        diff = na- nb
        if diff % 3 == 0:
            return ""
        elif (diff % 3) % 2 == 0:
            return "B"
        else:
            return "A"
    else:
        diff = nb - na
        if diff % 3 == 0:
            return ""
        elif (diff % 3) % 2 == 0:
            return "A"
        else:
            return "B"


Q = int(input())
for q in range(Q):
    a, b, c, d = map(int, input().split())
    sa = S_a[b] - S_a[a - 1]
    sb = S_b[b] - S_b[a - 1]
    ta = T_a[d] - T_a[c - 1]
    tb = T_b[d] - T_b[c - 1]

    SQ = calc(sa, sb)
    TQ = calc(ta, tb)

    print("YES" if SQ == TQ else "NO")

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

S = input()
T = input()
q = int(input())

tmp = 0
S_SUM = [0]
for s in S:
	if s == 'A':
		tmp += 2
	else:
		tmp += 1
	S_SUM.append(tmp)

T_SUM = [0]
tmp = 0
for t in T:
	if t == 'A':
		tmp += 2
	else:
		tmp += 1
	T_SUM.append(tmp)

for i in range(q):
	a,b,c,d = inpl()
	sa = (S_SUM[b]-S_SUM[a-1]) - (T_SUM[d]-T_SUM[c-1])
	if sa%3 == 0:
		print('YES')
	else:
		print('NO')

Submission status: Accepted

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

sa_pre = [s[i] == "A" for i in range(len(s))]
ta_pre = [t[i] == "A" for i in range(len(t))]

sa = [0, sa_pre[0]]
ta = [0, ta_pre[0]]

for i in range(1, len(s)):
	sa.append(sa[-1] + sa_pre[i])

for i in range(1, len(t)):
	ta.append(ta[-1] + ta_pre[i])

def check(a, b, c, d):
	xa = sa[b] - sa[a - 1]
	ya = ta[d] - ta[c - 1]
	if (2 * xa - (b - a + 1)) % 3 == (2 * ya - (d - c + 1)) % 3:
		print("YES")
		return
	else:
		print("NO")
		return

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

Submission status: Accepted

Solution code:
S=input()
T=input()
N=len(S)
M=len(T)
U=[0 for i in range(N+1)]
V=[0 for i in range(M+1)]
for i in range(N):
    if S[i]=="A":
        U[i+1]=(U[i]+1)%3
    else:
        U[i+1]=(U[i]-1)%3
for i in range(M):
    if T[i]=="A":
        V[i+1]=(V[i]+1)%3
    else:
        V[i+1]=(V[i]-1)%3
q=int(input())
O=["" for i in range(q)]
for inp in range(q):
    a,b,c,d=map(int,input().split())
    if (U[b]-U[a-1]-V[d]+V[c-1])%3==0:
        O[inp]="YES"
    else:
        O[inp]="NO"
for i in O:
    print(i)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

def enc(s):
  return [(1 if c == 'A' else 2) for c in s]

S = enc(input())
T = enc(input())

psumS = [0] + list(accumulate(S))
psumT = [0] + list(accumulate(T))

q = read()
for _ in range(q):
  a, b, c, d = reads()
  ms = psumS[b] - psumS[a-1]
  mt = psumT[d] - psumT[c-1]
  ans = (ms - mt) % 3 == 0
  print("YES" if ans else "NO")

Submission status: Accepted

Solution code:
S,T=[0],[0]
for c in input():S+=[S[-1]+1+(c=='B')]
for c in input():T+=[T[-1]+1+(c=='B')]
for _ in[0]*int(input()):
    a,b,c,d=map(int,input().split())
    print('NO'if(T[d]-T[c-1]-S[b]+S[a-1])%3 else'YES')

Submission status: Accepted

Solution code:
S,T=[0],[0]
for k,c in enumerate(input()):S+=[S[-1]+1+(c=='B')]
for k,c in enumerate(input()):T+=[T[-1]+1+(c=='B')]
for _ in[0]*int(input()):
    a,b,c,d=map(int,input().split())
    print('NO'if(T[d]-T[c-1]-S[b]+S[a-1])%3 else'YES')

Submission status: Accepted

Solution code:
S,T=[0],[0]
for k,c in enumerate(input()):S+=[S[-1]+1+(c=='B')]
for k,c in enumerate(input()):T+=[T[-1]+1+(c=='B')]
for _ in[0]*int(input()):
    a,b,c,d=map(int,input().split())
    print(['YES','NO'][(T[d]-T[c-1]-S[b]+S[a-1])%3>0])

Submission status: Accepted

Solution code:
S,T=[0],[0]
for k,c in enumerate(input()):S+=[S[-1]+(c=='A')]
for k,c in enumerate(input()):T+=[T[-1]+(c=='A')]
for _ in[0]*int(input()):
    a,b,c,d=map(int,input().split())
    print(['YES','NO'][(2*(b-a-d+c)+T[d]-T[c-1]-S[b]+S[a-1])%3>0])

Submission status: Accepted

Solution code:
S = input()
T = input()
Q = int(input())
qs = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(Q)]

smem = [0]
for c in S:
    if c == 'A':
        smem.append(smem[-1] + 1)
    else:
        smem.append(smem[-1] - 1)

tmem = [0]
for c in T:
    if c == 'A':
        tmem.append(tmem[-1] + 1)
    else:
        tmem.append(tmem[-1] - 1)

anss = []
for s1,s2,t1,t2 in qs:
    a = smem[s2+1] - smem[s1]
    b = tmem[t2+1] - tmem[t1]
    if a%3 == b%3:
        anss.append('YES')
    else:
        anss.append('NO')
print(*anss, sep='\n')

Submission status: Accepted

Solution code:
S = input()
T = input()
def count(S):
    L = len(S)
    cA = [0]*(L+1)
    cB = [0]*(L+1)
    for i in range(L):
        cA[i+1] = cA[i] + (S[i] == 'A')
        cB[i+1] = cB[i] + (S[i] == 'B')
    return cA, cB

sA, sB = count(S)
tA, tB = count(T)
q = int(input())
ans = []
for i in range(q):
    a, b, c, d = map(int, input().split())
    dA = (sA[b] - sA[a-1]) - (tA[d] - tA[c-1])
    dB = (sB[b] - sB[a-1]) - (tB[d] - tB[c-1])
    if (2*dA + dB) % 3 == 0 and (dA + 2*dB) % 3 == 0:
        ans.append('YES')
    else:
        ans.append('NO')
print(*ans, sep='\n')

Submission status: Accepted

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

cumsa = [0]
cumsb = [0]
for c in S:
    cumsa.append(cumsa[-1] + int(c == 'A'))
    cumsb.append(cumsb[-1] + int(c == 'B'))
cumta = [0]
cumtb = [0]
for c in T:
    cumta.append(cumta[-1] + int(c == 'A'))
    cumtb.append(cumtb[-1] + int(c == 'B'))

Q = int(input())
ans = []
for i in range(Q):
    a,b,c,d = map(int,input().split())
    sa = cumsa[b] - cumsa[a-1]
    sb = cumsb[b] - cumsb[a-1]
    ta = cumta[d] - cumta[c-1]
    tb = cumtb[d] - cumtb[c-1]
    ans.append('YES' if (sa-sb)%3 == (ta-tb)%3 else 'NO')

print('\n'.join(ans))

Submission status: Accepted

Solution code:
ds = [0]
tmp = 0
for c in input():
  tmp += [-1, 1][c == 'A']
  ds.append(tmp)

dt = [0]
tmp = 0
for c in input():
  tmp += [-1, 1][c == 'A']
  dt.append(tmp)

q = int(input())
for i in range(q):
  a, b, c, d = map(int, input().split())
  if abs((ds[b] - ds[a-1]) - (dt[d] - dt[c-1])) % 3 == 0:
    print('YES')
  else:
    print('NO')

Submission status: Accepted

Solution code:
Ss = input()
Ts = input()
q = int(input())
querys = [tuple(map(lambda x: int(x) - 1, input().split())) for i in range(q)]

def countA(Cs):
    numAs = [0] * (len(Cs) + 1)

    for i, C in enumerate(Cs, 1):
        if C == 'A':
            numAs[i] = numAs[i - 1] + 1
        else:
            numAs[i] = numAs[i - 1]

    return numAs


numASs = countA(Ss)
numATs = countA(Ts)
        
for a, b, c, d in querys:
    lenS = b - a + 1
    numAS = numASs[b + 1] - numASs[a]
    lenT = d - c + 1
    numAT = numATs[d + 1] - numATs[c]

    if ((numAS - (lenS - numAS)) - (numAT - (lenT - numAT))) % 3 == 0:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


def main():
    S = input()
    T = input()

    s_sum, t_sum = [0] * (len(S) + 1), [0] * (len(T) + 1)
    for i in range(len(S)):
        s_sum[i + 1] = s_sum[i] + (1 if S[i] == "A" else 2)

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
T = input()
q = int(input())
A = [list(map(int, input().split())) for _ in range(q)]

count_s = [{"A": 0, "B":0} for i in range(len(S))]
count_t = [{"A": 0, "B":0} for i in range(len(T))]

for i in range(len(S)):
  if(S[i] == "A"):
    count_s[i]["A"] += 1
    if(i == len(S) -1):
      break
    count_s[i+1] = count_s[i].copy()
  else:
    count_s[i]["B"] += 1
    if(i == len(S) -1):
      break
    count_s[i+1] = count_s[i].copy()


for i in range(len(T)):
  if(T[i] == "A"):
    count_t[i]["A"] += 1
    if(i == len(T) -1):
      break
    count_t[i+1] = count_t[i].copy()
  else:
    count_t[i]["B"] += 1
    if(i == len(T) -1):
      break
    count_t[i+1] = count_t[i].copy()


for i in range(q):
  if(S[A[i][0] - 1] == "A"):
    count_S = {"A": count_s[A[i][1] - 1]["A"] - count_s[A[i][0] - 1]["A"] + 1, "B": count_s[A[i][1] - 1]["B"] - count_s[A[i][0] -1]["B"]}
  else:
    count_S = {"A": count_s[A[i][1] - 1]["A"] - count_s[A[i][0] - 1]["A"], "B": count_s[A[i][1] - 1]["B"] - count_s[A[i][0] -1]["B"] + 1}
  if(T[A[i][2] - 1] == "A"):
    count_T = {"A": count_t[A[i][3] - 1]["A"] - count_t[A[i][2] - 1]["A"] + 1, "B": count_t[A[i][3] - 1]["B"] - count_t[A[i][2] - 1]["B"]}
  else:
    count_T = {"A": count_t[A[i][3] - 1]["A"] - count_t[A[i][2] - 1]["A"], "B": count_t[A[i][3] - 1]["B"] - count_t[A[i][2] - 1]["B"] + 1}

  if(count_S["A"] - count_T["A"] > 0):
    tmp = count_S["A"] - count_T["A"] - (count_S["B"] - count_T["B"])
    if(tmp % 3 == 0):
      print("YES")
    else:
      print("NO")

  else:
    tmp = count_T["A"] - count_S["A"] - (count_T["B"] - count_S["B"])
    if(tmp % 3 == 0):
      print("YES")
    else:
      print("NO")

Submission status: Accepted

Solution code:
#coding:utf-8


if __name__ == "__main__":
    S = raw_input()
    T = raw_input()
    q = int(raw_input())

    S_sum = [0] * (len(S) + 1)
    T_sum = [0] * (len(T) + 1)

    for i, char in enumerate(S):
        if char == "A":
            S_sum[i+1] = S_sum[i] + 1
        elif char == "B":
            S_sum[i+1] = S_sum[i] + 2

    for i, char in enumerate(T):
        if char == "A":
            T_sum[i+1] = T_sum[i] + 1
        elif char == "B":
            T_sum[i+1] = T_sum[i] + 2

    for query in range(q):
        a, b, c, d = map(int, raw_input().split(" "))

        S_mod = (S_sum[b] - S_sum[a-1]) % 3
        T_mod = (T_sum[d] - T_sum[c-1]) % 3

        if S_mod == T_mod:
            print "YES"
        else:
            print "NO"

Submission status: Accepted

Solution code:
import numpy as np

ss = [0] + np.fromiter(map(lambda c: 1 if c == 'A' else 2, input()), dtype=int).cumsum().tolist()
ts = [0] + np.fromiter(map(lambda c: 1 if c == 'A' else 2, input()), dtype=int).cumsum().tolist()
q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    print('YES' if (ss[b] - ss[a - 1]) % 3 == (ts[d] - ts[c - 1]) % 3 else 'NO')

Submission status: Accepted

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] - t[c-1]) % 3
	if x == y:
		print("YES")
	else:
		print("NO")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from random import *

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

def calc(s):
    res = [0 for ch in s]
    prev = 0
    for i in range(0,len(s)):
        if s[i] == 'A':
            res[i] = (prev - 1) % 3
        else:
            if s[i] == 'B':
                res[i] = (prev + 1) % 3
        prev = res[i]
    return res

def sum(l,r,s):
    l = l - 1
    r = r - 1
    if l > 0:
        res =  s[r] - s[l - 1]
    else:
        res =  s[r]
    return (res + 30000) % 3

s = input()
t = input()
ss = calc(s)
st = calc(t)
q = readln()[0]
for i in range(0,q):
    a,b,c,d = readln()
    x = sum(a,b,ss)
    y = sum(c,d,st)
    if x == y :
        print('YES')
    else:
        print('NO')