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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
S = input()
T = input()


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
Q = int(input())
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    if Search(a-1, b-1, 0, maxS, 0, ST) == Search(c-1, d-1, 0, maxT, 0, TT): print("YES")
    else: print("NO")

Submission status: Time Limit Exceeded

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

    def norm(s):
        s_ = []
        for c in s:
            if len(s_) == 0:
                s_.append(c)
            elif s_[-1] == c:
                s_.pop()
                s_.append('A' if c != 'A' else 'B')
            else:
                s_.pop()
        return ''.join(s_)

    for a, b, c, d in ABCD:
        s = S[a-1:b]
        t = T[c-1:d]
        if norm(s) == norm(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: Time Limit Exceeded

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

def check(x, y):
	xa = len(list(filter(lambda i: i == "A", x)))
	ya = len(list(filter(lambda i: i == "A", y)))
	if (2 * xa - len(x)) % 3 == (2 * ya - len(y)) % 3:
		print("YES")
	else:
		print("NO")

for _ in range(q):
	a, b, c, d = map(int, input().split())
	check(s[a - 1 : b], t[c - 1 : d])

Submission status: Time Limit Exceeded

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

def check(x, y):
	xa = len(list(filter(lambda i: i == "A", x)))
	ya = len(list(filter(lambda i: i == "A", y)))
	if (2 * xa - len(x)) % 3 == (2 * ya - len(y)) % 3:
		print("YES")
	else:
		print("NO")

for _ in range(q):
	a, b, c, d = map(int, input().split())
	check(s[a - 1 : b], t[c - 1 : d])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def check(x, y):
	xa = len(list(filter(lambda i: i == "A", x)))
	ya = len(list(filter(lambda i: i == "A", y)))
	if (2 * xa - len(x)) % 3 == (2 * ya - len(y)) % 3:
		print("YES")
	else:
		print("NO")

for _ in range(q):
	a, b, c, d = map(int, input().split())
	check(s[a - 1 : b], t[c - 1 : d])

Submission status: Time Limit Exceeded

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

def check(x, y):
	xa = x.count("A")
	ya = y.count("A")
	if (2 * xa - len(x)) % 3 == (2 * ya - len(y)) % 3:
		print("YES")
	else:
		print("NO")

for _ in range(q):
	a, b, c, d = map(int, input().split())
	check(s[a - 1 : b], t[c - 1 : d])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
S = input()
T = input()
q = int(input())
for i in range(q):
  a, b, c, d = map(int, input().split())
  c1 = Counter(list(S[a-1:b]))
  c2 = Counter(list(T[c-1:d]))
  if abs((c1['A'] - c1['B']) - (c2['A'] - c2['B'])) % 3 == 0:
    print('YES')
  else:
    print('NO')

Submission status: Time Limit Exceeded

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

for a, b, c, d in querys:
    lenS = b - a + 1
    numAS = S[a:b + 1].count('A')
    lenT = d - c + 1
    numAT = T[c:d + 1].count('A')

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

Submission status: Time Limit Exceeded

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

for i in range(q):
  count_s = {"A": 0, "B": 0}
  count_t = {"A": 0, "B": 0}
  for j in range(A[i][0]-1, A[i][1]):
    if(S[j] == "B"):
      count_s["B"] += 1
    else:
      count_s["A"] += 1
  for k in range(A[i][2]-1, A[i][3]):
    if(T[k] == "B"):
      count_t["B"] += 1
    else:
      count_t["A"] += 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: 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())
	s = S[a-1:b]
	t = T[c-1:d]
	x = (s.count("A") + 2 * s.count("B")) % 3
	y = (t.count("A") + 2 * t.count("B")) % 3
	if x == y:
		print("YES")
	else:
		print("NO")

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

s = input()
t = input()
q = int(input())

for i in range(q):
    a, b, c, d = map(int, input().split())
    s_check = s[(a - 1):(b)]
    t_check = t[(c - 1):(d)]
    s_counts = Counter(s_check)
    t_counts = Counter(t_check)
    s_score = (s_counts['A'] * 1 + s_counts['B'] * 2) % 3
    t_score = (t_counts['A'] * 1 + t_counts['B'] * 2) % 3
    print('YES' if s_score == t_score else 'NO')

Submission status: Time Limit Exceeded

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

def shorten(s):
    if s[0] != s[1]:
        return s[2:]
    elif s[1] != s[2]:
        return s[0] + s[3:]
    return s[3:]

def check(s):
    sc = [s]
    while len(s) >= 3:
        if s in visited:
            s = visited[s]
            break
        s = shorten(s)
        sc.append(s)

    if len(s) == 2:
        if s == 'AA':
            s = 'B'
        elif s == 'BB':
            s = 'A'
        else:
            s = ''

    for sci in sc:
        visited[sci] = s

    return s

visited = {}
for a,b,c,d in q:
    si = check(s[a-1:b])
    ti = check(t[c-1:d])

    if si == ti:
        print 'YES'
    else:
        print 'NO'

Submission status: Time Limit Exceeded

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

# S=list("BBAAABA")
# T=list("BBBA")

q = int(input())

l = []
for i in range(q):
	l.append(list(map(int,input().split(" "))))


i = 1
while i < len(S):
	i <<= 1
sta = [0 for i in range(i*2)]

i = 1
while i < len(S):
	i <<= 1
stb = [0 for i in range(i*2)]

i = 1
while i < len(T):
	i <<= 1
tta = [0 for i in range(i*2)]

i = 1
while i < len(T):
	i <<= 1
ttb = [0 for i in range(i*2)]

for i in range(len(S)):
	if S[i] == "A":
		sta[i+len(sta)//2] = 1
	else:
		stb[i+len(stb)//2] = 1

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

def make(l):
	def do(i):
		if i >= len(l)//2:
			return(l[i])
		else:
			l[i] = do(i*2)+do(i*2+1)
			return(l[i])

	do(1)

def get(li,a,b):   #[a,b]を調べる
		def foo(k,a,b,l,r): #[a,b)を調べる
			if b <= l or r <= a:
				return(0)
			elif a <= l and r <= b:
				return(li[k])
			else:
				return(
					foo(2*k,a,b,l,(r+l)//2)+foo(2*k+1,a,b,(r+l)//2,r)
					)

		return(foo(1,a,b+1,0,len(li)//2))

make(sta)
make(stb)
make(tta)
make(ttb)

for a,b,c,d in l:
	sa = get(sta,a-1,b-1)
	sb = get(stb,a-1,b-1)
	ta = get(tta,c-1,d-1)
	tb = get(ttb,c-1,d-1)


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

Submission status: Time Limit Exceeded

Solution code:
def check(s, t, a, b, c, d):
    ssum = 0
    tsum = 0
    for i in range(a - 1, b):
        if s[i] == 'A':
            ssum += 1
        else:
            ssum += 2 
    for i in range(c - 1, d):
        if t[i] == 'A':
            tsum += 1
        else:
            tsum += 2 
    return (ssum - tsum) % 3 == 0

s = input()
t = input()
q = int(input())
a = [[int(i) for i in input().split()] for j in range(q)]

for i in range(q):
    if check(s, t, a[i][0], a[i][1], a[i][2], a[i][3]):
        print('YES')
    else:
        print('NO')

Submission status: Time Limit Exceeded

Solution code:
s = raw_input()
t = raw_input()
q = int(raw_input())
a = []
b = []
c = []
d = []

for i in range(q):
    at, bt, ct, dt = map(int, raw_input().split())
    a.append(at)
    b.append(bt)
    c.append(ct)
    d.append(dt)

for i in range(q):
    st = s[a[i]-1:b[i]]
    tt = t[c[i]-1:d[i]]
    if len(st) == 0:
        print 'NO'
    else:
        if ((len(st) - 2 * st.count('A')) - (len(tt) - 2 * tt.count('A'))) % 3 == 0:
            print 'YES'
        else:
            print 'NO'

Submission status: Time Limit Exceeded

Solution code:
import collections

NONE_RES,A_RES,B_RES = 0,1,2
buf = [[NONE_RES,B_RES,A_RES],[A_RES,NONE_RES,B_RES],[B_RES,A_RES,NONE_RES]]

def check(s1,s2):
    s1,s2 = collections.Counter(s1),collections.Counter(s2)
    A1 = s1['A'] if 'A' in s1 else 0
    A2 = s2['A'] if 'A' in s2 else 0
    B1 = s1['B'] if 'B' in s1 else 0
    B2 = s2['B'] if 'B' in s2 else 0
    type1 = buf[A1%3][B1%3]
    type2 = buf[A2%3][B2%3]
    return type1==type2

S = input()
T = input()
n = int(input())
for _ in range(n):
    a,b,c,d = map(int,input().split(' '))
    if check(S[a-1:b],T[c-1:d]):
        print('YES')
    else:
        print('NO')

Submission status: Time Limit Exceeded

Solution code:
def cnt(str):
    rtn = 1
    for i in range(1, len(str)):
        if str[i] == str[0]:
            rtn += 1
        else:
            break
    return rtn

S = input()
T = input()
q = int(input())
ans = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    si = S[a - 1: b]
    ti = T[c - 1: d]
    ls = len(si)
    for c in list(si):
        if c == ti[0]:
            ls += 1
    while 0 < len(ti):
        ls *= 2
        lt = cnt(ti)
        ti = ti[lt:]
        while ls <= lt:
            ls *= 4
        ls -= lt
    if ls % 3 == 0:
        ans.append('YES')
    else:
        ans.append('NO')

for yn in ans:
    print(yn)

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys

S = input()
T = input()

ns = len(S)
nt = len(T)
SA = [0] * (ns + 1)
SB = [0] * (ns + 1)
TA = [0] * (nt + 1)
TB = [0] * (nt + 1)
for i, s in enumerate(S, 1):
    if s == "A":
        SA[i] = 1
    else:
        SB[i] = 1
for i, t in enumerate(T, 1):
    if t == "A":
        TA[i] = 1
    else:
        TB[i] = 1
SA = list(accumulate(SA))
SB = list(accumulate(SB))
TA = list(accumulate(TA))
TB = list(accumulate(TB))


q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    sa = SA[b] - SA[a - 1]
    sb = SB[b] - SB[a - 1]
    ta = TA[d] - TA[c - 1]
    tb = TB[d] - TB[c - 1]
    # ぜんぶBにしちゃう
    sb += 2 * sa
    tb += 2 * ta
    if abs(sb - tb) % 3 == 0:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate


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


def acc(li, n):
    res = [0] * (n + 1)
    for i in range(n):
        if li[i] == "A":
            res[i + 1] = 1
        elif li[i] == "B":
            res[i + 1] = 2
    return list(accumulate(res))


def restore(x, y, li):
    return (li[y] - li[x - 1]) % 3


S = input()
T = input()
N = len(S)
M = len(T)

acc_S = acc(S, N)
acc_T = acc(T, M)

q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    v_S = restore(a, b, acc_S)
    v_T = restore(c, d, acc_T)
    print("YES") if v_S == v_T else print("NO")

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
readlines = sys.stdin.readlines
input = sys.stdin.readline
S = tuple(accumulate(map(lambda x: 1 if x == 'A' else 2, input().rstrip())))
T = tuple(accumulate(map(lambda x: 1 if x == 'A' else 2, input().rstrip())))
input()
for line in readlines():
    a, b, c, d = map(lambda x: int(x)-1, line.split())
    s = S[b]-S[a-1] if a else S[b]
    t = T[d]-T[c-1] if c else T[d]
    print('YES' if s % 3 == t % 3 else 'NO')

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

S = input()
T = input()
Q = getN()
que = [getList() for i in range(Q)]
# 各queryにつきO(1)で答える
# →リストをO(n)で作り答える
# AとBについてそれぞれ対応させると?
# 各要素について合成できる？
# 1:[A, BB], 2:[AA, B], 3[AAA, BBB]
# 1のものを2つ足したら2のものになる
# 1のものと2のものを足したら3になり消える
# 前からA: += 1, B: += 2を累積していく
imos_s = [0]
for i in range(len(S)):
    if S[i] == 'A':
        imos_s.append(imos_s[i] + 1)
    else:
        imos_s.append(imos_s[i] + 2)
imos_t = [0]
for i in range(len(T)):
    if T[i] == 'A':
        imos_t.append(imos_t[i] + 1)
    else:
        imos_t.append(imos_t[i] + 2)

for i in range(Q):
    a, b, c, d = que[i]
    opt_1 = (imos_s[b] - imos_s[a - 1]) % 3
    opt_2 = (imos_t[d] - imos_t[c - 1]) % 3
    if opt_1 == opt_2:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
sl=[0]
for i in s:
    sl.append(sl[-1])
    if i=="A":sl[-1]+=1
    else:sl[-1]+=2
    sl[-1]%=3
tl=[0]
for i in t:
    tl.append(tl[-1])
    if i=="A":tl[-1]+=1
    else:tl[-1]+=2
    tl[-1]%=3
q=int(input())
for _ in range(q):
    a,b,c,d=map(int,input().split())
    a-=1
    c-=1
    ss=sl[b]-sl[a]
    tt=tl[d]-tl[c]
    if ss%3==tt%3:print("YES")
    else:print("NO")

Submission status: Accepted

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)]

scnt=[(0,0)]*(len(s)+1)
tcnt=[(0,0)]*(len(t)+1)
for i in range(len(s)):
    a,b=scnt[i]
    if s[i]=="A":
        a+=1
    else:
        b+=1
    scnt[i+1]=(a,b)
for i in range(len(t)):
    a,b=tcnt[i]
    if t[i]=="A":
        a+=1
    else:
        b+=1
    tcnt[i+1]=(a,b)
# print(scnt)
# print(tcnt)

for i in range(q):
    a,b,c,d=abcd[i]
    sa,sb=scnt[b],scnt[a-1]
    sa,sb=sa[0]-sb[0],sa[1]-sb[1]
    ta,tb=tcnt[d],tcnt[c-1]
    ta,tb=ta[0]-tb[0],ta[1]-tb[1]
    # print(sa,sb,ta,tb)

    if abs((sa-sb)-(ta-tb))%3==0:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
S = input()
T = input()
q = int(input())
abcd= [list(map(int,input().split())) for i in range(q)]

# Segment Tree
class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self, i=None):
        if i is None:
            return self.data[self.l:self.l + self.N]
        else:
            return self.data[self.l+i]

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = self.default 
        while j-i > 0:
            if i & 1:
                s = self.op(s,self.data[i])
                i += 1
            if j & 1:
                s = self.op(s,self.data[j-1])
                j -= 1
            i, j = i//2, j//2
        return s

convert = lambda x : 1 if x == 'A' else 2
nS = list(map(convert,S))
nT = list(map(convert,T))
segS = SegmentTree(nS,lambda x,y:x+y, 0)
segT = SegmentTree(nT,lambda x,y:x+y, 0)

# A -> BB -> AAAA -> A
# B -> AA -> BBBB -> B
# (S) -> AAAAA......
for a,b,c,d in abcd:
    rs = segS.get(a-1,b)
    rt = segT.get(c-1,d)
    if (rs-rt) % 3 == 0:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
fc=lambda x:1 if x=='A' else 2
s=list(map(fc,list(input())))
t=list(map(fc,list(input())))
q=int(input())
abcd=[list(map(int,input().split())) for _ in range(q)]
cs=[0]
tmp=0
for x in s:
  tmp+=x
  cs.append(tmp)
ct=[0]
tmp=0
for x in t:
  tmp+=x
  ct.append(tmp)
for a,b,c,d in abcd:
  if (cs[b]-cs[a-1])%3==(ct[d]-ct[c-1])%3:
    print('YES')
  else:
    print('NO')

Submission status: Accepted

Solution code:
# AB -> BBAA -> BAAAA -> BA
# Thus, this problem has commutative property.
# So, if we let A and B satisfy x^2 + x + 1 == 0,
# then A^2 == B, B^2 == A, and A^3 == B^3 == 1.
# So this makes an invariant.

from itertools import accumulate

S = input()
T = input()
q = int(input())
abcds = [tuple(map(int, input().split())) for _ in range(q)]

S_csum = list(map(lambda x: x%3, [0] + list(accumulate(map(lambda c: 1 if c == 'A' else -1, S)))))
T_csum = list(map(lambda x: x%3, [0] + list(accumulate(map(lambda c: 1 if c == 'A' else -1, T)))))

for a, b, c, d in abcds:
    if (S_csum[b] - S_csum[a-1]) % 3 == (T_csum[d] - T_csum[c-1]) % 3:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

Solution code:
# AB -> BBAA -> BAAAA -> BA
# Thus, this problem has commutative property.
# So, if we let A and B satisfy x^2 + x + 1 == 0,
# then A^2 == B, B^2 == A, and A^3 == B^3 == 1.
# So this makes an invariant.

from itertools import accumulate

S = input()
T = input()
q = int(input())
abcds = [tuple(map(int, input().split())) for _ in range(q)]

S_csum = list(map(lambda x: x%3, accumulate(map(lambda c: 1 if c == 'A' else -1, S), initial=0)))
T_csum = list(map(lambda x: x%3, accumulate(map(lambda c: 1 if c == 'A' else -1, T), initial=0)))

for a, b, c, d in abcds:
    if (S_csum[b] - S_csum[a-1]) % 3 == (T_csum[d] - T_csum[c-1]) % 3:
        print("YES")
    else:
        print("NO")

Submission status: Accepted

Solution code:
s=input()
t=input()
sm=0
ss=[]
for i in s:
  sm+=(i=="A")*2-1
  ss.append(sm)
ss.append(0)
sm=0
ts=[]
for i in t:
  sm+=(i=="A")*2-1
  ts.append(sm)
ts.append(0)
q=int(input())
for i in range(q):
  inp=list(map(int,input().split()))
  if (ss[inp[1]-1]-ss[inp[0]-2])%3==(ts[inp[3]-1]-ts[inp[2]-2])%3:
    print("YES")
  else:
    print("NO")

Submission status: Accepted

Solution code:
s = list(input())
t = list(input())
ls, lt = len(s), len(t)
sa, sb = [0] * (ls + 1), [0] * (ls + 1)
ta, tb = [0] * (lt + 1), [0] * (lt + 1)
for i in range(1, ls + 1):
    if s[i - 1] == "A":
        sa[i] = sa[i - 1] + 1
        sb[i] = sb[i - 1]
    else:
        sa[i] = sa[i - 1]
        sb[i] = sb[i - 1] + 1
for i in range(1, lt + 1):
    if t[i - 1] == "A":
        ta[i] = ta[i - 1] + 1
        tb[i] = tb[i - 1]
    else:
        ta[i] = ta[i - 1]
        tb[i] = tb[i - 1] + 1

q = int(input())
for _ in range(q):
    ans = 0
    a, b, c, d = map(int, input().split())
    a1, b1 = sa[b] - sa[a - 1], sb[b] - sb[a - 1]
    a2, b2 = ta[d] - ta[c - 1], tb[d] - tb[c - 1]
    x, y = a1 - b1, a2 - b2
    if x * y < 0:
        x = -2 * x
    if abs(x - y) % 3 == 0:
        ans = 1
    print("YES" if ans == 1 else "NO")

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

s = readline().strip()
t = readline().strip()
q = int(readline())
abcd = list(map(int,read().split()))

cumsum_s = [0] * (len(s)+1)
cumsum_t = [0] * (len(t)+1)
for cs,st in zip([cumsum_s,cumsum_t],[s,t]):
    for i,ch in enumerate(st,1):
        cs[i] = cs[i-1] + (1 if ch=='A' else 2)

ans = []
it = iter(abcd)
for a,b,c,d in zip(it,it,it,it):
    num1 = cumsum_s[b] - cumsum_s[a-1]
    num2 = cumsum_t[d] - cumsum_t[c-1]
    if((num1-num2)%3 == 0):
        ans.append('YES')
    else:
        ans.append('NO')

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    s = input()
    t = input()
    a = [0]*(len(s)+1)
    b = [0]*(len(t)+1)
    for i, c in enumerate(s):
        if c == "A":
            a[i+1] = 1
        else:
            a[i+1] = 2
        a[i+1] += a[i]
    for i, c in enumerate(t):
        if c == "A":
            b[i+1] = 1
        else:
            b[i+1] = 2
        b[i+1] += b[i]
    q = int(input())
    ans = [None]*q
    for i in range(q):
        a1, a2, b1, b2 = map(int, input().split())
        x, y = a[a2] - a[a1-1], b[b2] - b[b1-1]
        if abs(x-y) % 3 == 0:
            ans[i] = "YES"
        else:
            ans[i] = "NO"
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

s = ins()
t = ins()
sacc = [0]
for c in s:
    sacc.append(((1 if c=='A' else 2)+sacc[-1])%3)
tacc = [0]
for c in t:
    tacc.append(((1 if c=='A' else 2)+tacc[-1])%3)
#ddprint(sacc)
#ddprint(tacc)
q = inn()
for i in range(q):
    a,b,c,d = inm()
    #ddprint('{} {} {} {}'.format(sacc[b],sacc[a-1],tacc[d],tacc[c-1]))
    print('YES' if (sacc[b]-sacc[a-1])%3==(tacc[d]-tacc[c-1])%3 else 'NO')

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,m = map(int,readline().split())
s = input()
t = input()

vs = [0]
for i in s:
    if i =="A": vs.append(vs[-1]+1)
    else: vs.append(vs[-1]-1)

vt = [0]
for i in t:
    if i =="A": vt.append(vt[-1]+1)
    else: vt.append(vt[-1]-1)

#print(vs)
#print(vt)

q = int(input())
for _ in range(q):
    a,b,c,d = map(int,readline().split())
    rs = vs[b] - vs[a-1]
    rs %= 3

    rt = vt[d] - vt[c-1]
    rt %= 3

    if rs==rt: print("YES")
    else: print("NO")

Submission status: Accepted

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

cum_s = [(0, 0)]
cum_t = [(0, 0)]

for i in range(len(S)):
    p, q = cum_s[-1]
    if S[i] == 'A':
        cum_s.append((p + 1, q))
    else:
        cum_s.append((p, q + 1))

for i in range(len(T)):
    p, q = cum_t[-1]
    if T[i] == 'A':
        cum_t.append((p + 1, q))
    else:
        cum_t.append((p, q + 1))

Q = int(input())

for _ in range(Q):
    a, b, c, d = map(int, input().split())
    sp = cum_s[b][0] - cum_s[a - 1][0]
    sq = cum_s[b][1] - cum_s[a - 1][1]
    tp = cum_t[d][0] - cum_t[c - 1][0]
    tq = cum_t[d][1] - cum_t[c - 1][1]
    sp += sq * 2
    tp += tq * 2
    if sp % 3 == tp % 3:
        print('YES')
    else:
        print('NO')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    S = input()
    T = input()
    Scnt = [0] * (len(S) + 1)
    for i in range(len(S)):
        if S[i] == 'A':
            Scnt[i + 1] = Scnt[i] + 1
        else:
            Scnt[i + 1] = Scnt[i] + 2
    
    Tcnt = [0] * (len(T) + 1)
    for i in range(len(T)):
        if T[i] == 'A':
            Tcnt[i + 1] = Tcnt[i] + 1
        else:
            Tcnt[i + 1] = Tcnt[i] + 2
    
    Q = int(input())
    for _ in range(Q):
        a,b,c,d = map(int,input().split())
        a -= 1
        c -= 1
        if (Scnt[b] - Scnt[a] - Tcnt[d] + Tcnt[c])%3 == 0:
            print('YES')
        else:
            print('NO')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S=[input() for i in range(2)]
q=int(input())
ABCD=[list(map(int,input().split())) for i in range(q)]
p=[[0] for i in range(2)]
for i in range(2):
    for j,s in enumerate(S[i]):
        if s=='A':
            p[i].append(p[i][-1]+1)
        else:
            p[i].append(p[i][-1]+2)
for a,b,c,d in ABCD:
    print(['NO','YES'][(p[0][b]-p[0][a-1])%3==(p[1][d]-p[1][c-1])%3])

Submission status: Accepted

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()