Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

class SegTreeMin:
    def __init__(self, n, inf=10 ** 15):
        self.n = n
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [inf] * (n2 << 1)
        self.inf = inf
        
    def update(self, i, x):
        i += self.n2
        self.tree[i] = x
        while i > 1:
            x = min(x, self.tree[i ^ 1])
            self.tree[i >> 1] = x
            i >>= 1
            
    def get_min(self, a, b):
        result = self.inf
        q = [(1, 0, self.n2)]
        while q:
            k, l, r = q.pop()
            if a <= l and r <= b:
                result = min(result, self.tree[k])
                continue
                
            m = (l + r) // 2
            k <<= 1
            if a < m and l < b:
                q.append((k, l, m))
            if a < r and l < m:
                q.append((k + 1, m, r))
                
        return result

INF = 10 ** 15
seg_tree = SegTreeMin(N, INF)
seg_tree.update(0, 0)
X.sort()
for l, r, c in X:
    l -= 1
    r -= 1
    tmp = seg_tree.get_min(l, r)
    seg_tree.update(r, min(tmp + c, seg_tree.get_min(r, r + 1)))
ans = seg_tree.get_min(N - 1, N)
print(ans if ans != INF else -1)


### FIXED CODE ###

from heapq import heappop, heappush
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

edges = [[] for _ in range(N)]
for u, v, c in X:
    edges[u - 1].append((v - 1, c))
    
for i in range(N - 1):
    edges[i + 1].append((i, 0))

INF = float("inf")
d = [INF] * N
d[0] = 0

pq = []
heappush(pq, (0, 0))

while len(pq) > 0:
    cost, u = heappop(pq)
    for v, c in edges[u]:            
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            
print(d[-1] if d[-1] != INF else -1)
### BUGGY CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_C&lang=jp
#??????
if __name__ == "__main__":
    n_line = int(input())
    l = []
    for i in range(n_line):
        input_line = input().split()
        if input_line[0] == "insert":
            l.append(input_line[1])
        else:
            if input_line[1] in l:
                print("yes")
            else:
                print("no")

### FIXED CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_C&lang=jp
#??????
if __name__ == "__main__":
    n_line = int(input())
    input_list = [tuple(input().split()) for i in range(n_line)]
    l = set([])
    for c, s in input_list:
        if c == "insert":
            l.add(s)
        else:
            if s in l:
                print("yes")
            else:
                print("no")
### BUGGY CODE ###

n,m=map(int,input().split())
dp = [[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
  w,v=map(int,input().split())
  for j in range(m+1):
    if j < w:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-w]+v,dp[i-1][j])
print(dp[n][m])

### FIXED CODE ###

n,m=map(int,input().split())
dp = [[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
  w,v=map(int,input().split())
  for j in range(m+1):
    if j < w:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j-w]+v,dp[i-1][j])
print(dp[n][m])
### BUGGY CODE ###

import sys
k = int(input())
if k %2 == 0:
    print(-1)
    sys.exit()

num = 0

if k == 999983:
    print(999982)
    sys.exit()

for i in range(k):
    num += 7*(10**i)
    if num %k == 0:
        print(i+1)
        sys.exit()
print(-1)

### FIXED CODE ###

import sys
k = int(input())

num = 0
for i in range(k + 1):
    num = (num*10+7)%k
    if num == 0:
        print(i + 1)
        sys.exit()
print(-1)
### BUGGY CODE ###

from collections import Counter
N = int(input())
S =[]
for i in range(N):
    S.append(str(input()))

B =[]
for i in S:
    S1 =list(Counter(i).items())
    S1 =sorted(S1, reverse = False)
    B.append(S1)
#print(B)

cnt = 0
for i in range(N-1):
    for j in range(i+1,N):
        if B[i] == B[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

from collections import Counter

N = int(input())
S = [list((map(str,input().split()))) for _ in range(N)]

A = []
for i in S:
    ew_str = ''.join(sorted(i[-1]))
    A.append(ew_str)

cnt = Counter(A)
cnt = list(cnt.values())
#print(cou)

ans = 0
for i in cnt:
    ans +=i*(i-1)//2
print(ans)
### BUGGY CODE ###

from math import gcd
N = int(input())
a = list(map(int, input().split()))
ans = a[0]
flag = True

for i in range(N):
  if i != 0:
    ans = gcd(ans,a[i])
  for j in range(i+1,N):
    if gcd(a[i],a[j]) != 1:
      flag = False
  
if flag:
  print("pairwise coprime")
  exit()     
elif flag == False and ans == 1:
  print("setwise coprime")
elif ans != 1:
  print("not coprime")

### FIXED CODE ###

from math import gcd
N = int(input())
A = list(map(int,input().split()))

g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    exit()

MAXA = 10**6
B = [0] * (MAXA+1)
for a in A:
    if a==1: continue
    if B[a]:
        print('setwise coprime')
        exit()
    B[a] = 1

for n in range(2,MAXA+1):
    c = 0
    for m in range(n,MAXA+1,n):
        c += B[m]
        if c > 1:
            print('setwise coprime')
            exit()

print('pairwise coprime')
### BUGGY CODE ###

from collections import Counter, defaultdict
N = int(input())
S = list(input())
Q = int(input())

l = 2**((N-1).bit_length())
data = [Counter([]) for i in range(2*l)]
for i in range(N):
    data[l+i][S[i]] = 1
for i in range(l-1,0,-1):
    data[i] = data[2*i] + data[2*i+1]

for cnt in range(Q):
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        if S[b-1] == c:
            continue
        oldc = S[b-1]
        S[b-1] = c
        n = l + b - 1
        while n > 0:
            data[n][oldc] -= 1
            data[n][c] += 1
            n = n // 2
    else:
        c = int(c)
        i = b + l -1
        j = c + l
        temp = Counter()
        while j-i > 0:
            if i & 1:
                temp += data[i]
                i += 1
            if j & 1:
                temp += data[j-1]
                j -= 1
            i //= 2
            j //= 2
        print(len(temp))



### FIXED CODE ###

N = int(input())
S = list(input())
Q = int(input())

l = 2**((N-1).bit_length())
#data = [Counter([]) for i in range(2*l)]
data = [0] * (2*l)

str2bin = lambda x : 1 << (ord(x) - ord('a'))
    
for i in range(N):
    data[l+i] = str2bin(S[i])
for i in range(l-1,0,-1):
    data[i] = data[2*i] | data[2*i+1]

for cnt in range(Q):
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        n = l + b - 1
        data[n] = str2bin(c)
        n //= 2
        while n > 0:
            data[n] = data[2*n] | data[2*n+1]
            n = n // 2
    else:
        c = int(c)
        i = b + l -1
        j = c + l
        res = 0
        while j-i > 0:
            if i & 1:
                res |= data[i]
                i += 1
            if j & 1:
                res |= data[j-1]
                j -= 1
            i //= 2
            j //= 2
        print(bin(res).count('1'))
### BUGGY CODE ###

def main():
    N, Q = input().split()
    S = input()
    list = []

    for i in range(int(Q)):
        list.append(int(x) for x in input().split())

    for i in range(int(Q)):
        a, b = list[i]
        sss = S[a - 1:   b]
        count = sss.count("AC")
        print(count)

    return 0


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()

    list = [0] * (N + 1)

    for i in range(N):
        list[i + 1] = list[i] + (1 if S[i:i + 2] == "AC" else 0)

    for i in range(Q):
        a, b = map(int, input().split())
        output = list[b - 1] - list[a - 1]
        print(output)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(K: int):
    if K % 2 == 0:
        print(-1)
    else:
        num = 7
        cnt = 1
        while True:
            if num % K == 0:
                print(cnt)
                return
            else:
                num *= 10
                num += 7
                num %= K
                cnt += 1
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(K: int):
    if K % 2 == 0:
        print(-1)
    else:
        num = 7
        cnt = 1
        stop = 10 ** 7
        while cnt < stop:
            if num % K == 0:
                print(cnt)
                return
            else:
                num *= 10
                num += 7
                num %= K
                cnt += 1
        print(-1)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections

def solve(N: int, A: "List[int]"):
    counter = sorted(list(collections.Counter(A).values()),reverse=True)
    for i in range(1,N+1):
        if len(counter)<i:
            print(0)
            continue
        c_index = 0
        n = N
        k = i 
        while counter[c_index]*k > n and c_index<len(counter)-1:
            n-=counter[c_index]
            c_index+=1
            k-=1
        print(n//k)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections

def solve(N: int, A: "List[int]"):
    counter = sorted(list(collections.Counter(A).values()),reverse=True)
    c_index = 0
    k=0
    for i in range(1,N+1):
        k+=1
        if len(counter)<i:
            print(0)
            continue
        while counter[c_index]*k > N and c_index<len(counter)-1:
            N-=counter[c_index]
            c_index+=1
            k-=1
        print(N//k)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

#ABC065

n = int(input())
a = [int(input()) for _ in range(n)]
b = []
count = 0
i = 1
for _ in range(n):
    if i in b:
        
        count = 0
        break
    if i == 2:
        break
    b.append(i)
    i = a[i-1]
    count += 1
    
        
if count != 0:
    print(count)
else:
    print(-1)

### FIXED CODE ###

#ABC065

n = int(input())
a = [int(input()) for _ in range(n)]
b = []

i = 1
for _ in range(n):
    
    b.append(i)
    i = a[i-1]
    
    
        
if 2 in b:
    print(b.index(2))
else:
    print(-1)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    S = list(input())

    ans = 10 * 6
    for i in range(N):
        tmp = S[:i].count('W')
        if i + 1< N:
            tmp += S[i+1:].count('E')
        ans = min(ans, tmp)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    S = list(input())

    ans = 10 ** 6
    sum_count = S.count('E')
    for s in S:
        aft = 0
        if s == 'W':
            aft = 1
        else:
            sum_count -= 1
        ans = min(ans, sum_count)
        sum_count += aft
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=str(input())
ans=0
nn=len(n)
for i in range(0,nn-3):
  for j in range(i+3,nn+1):
    now=n[i:j]
    now=int(now)
    if now%2019==0:
      ans+=1
print(ans)

### FIXED CODE ###

s=str(input())
n=len(s)
ans=0
l=[0 for i in range(2019)]
now=l[int(s[n-1])]
r=1
for i in range(1,n+1):
  now=(now+int(s[-i])*r)%2019
  l[now]+=1
  r=r*10
  r=r%2019
ans+=l[0]
for i in l:
  ans+=int(i*(i-1)//2)
print(ans)
#print(l)
### BUGGY CODE ###

n=int(input())
if n<4:
  print(2,5,63)
  exit()
a,b=[],[]
i=j=k=0
while i<n:
  if not b or a and a[-1]>b[-1]:
    b+=3*-~k,
    k+=1
    i+=1
  else:
    t=2*-~j
    if t%3:
      a+=t,
      i+=1
    j+=1
c=sum(a+b)
if c%6:
  if c%2:
    b[-1]+=3
    c+=3
  while c%6:
    a[-1]+=2
    c+=2
    if a[-1]%3<1:
      a[-1]+=2
      c+=2
print(*a+b)

### FIXED CODE ###

n=int(input())
if n<4:
  print(2,5,63)
  exit()
a,b=[],[]
i=j=k=0
while i<n:
  if not b or a and a[-1]>b[-1]:
    b+=3*-~k,
    k+=1
    i+=1
  else:
    t=2*-~j
    if t%3:
      a+=t,
      i+=1
    j+=1
c=sum(a+b)
if c%6:
  if c%2:
    b[-1]+=3
    c+=3
  while c%6:
    a[-1]+=2
    c+=2
    if a[-1]%3<1and a[-1]==b[-1]:
      a[-1]+=2
      c+=2
print(*a+b)
### BUGGY CODE ###

N = int(input())
import heapq as h
A = list(map(int, input().split()))


def reverse(x):
    return -x


# use 0 based index
sum_red, sum_blue = [], []

# sum_redを制作
head = A[:N]
h.heapify(head)
sum_red.append(sum(head))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))


# sum_blueを制作
# 最大値をpopしてほしいがそれができないのですべて負にすることで擬似的に最大値をpopする
tail = list(map(reverse, A[-N:]))
h.heapify(tail)
sum_blue.append(-sum(tail))
for k in range(2*N-1, N-1, -1):
    h.heappushpop(tail, -A[k])
    sum_blue.append(sum(list(map(reverse, tail))))

# 逆順に突っ込んでるので反転
sum_blue = sum_blue[::-1]

import numpy as np
diff = np.array(sum_red) - np.array(sum_blue)
print(max(diff))


### FIXED CODE ###

N = int(input())
import heapq as h
A = list(map(int, input().split()))


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
# keypoint: いちいちsumすると線形時間かかるのでsum_hoge[-1]でアクセスする
for k in range(N, 2*N):
    num_sub = h.heappushpop(head, A[k])
    sum_red.append(sum_red[-1]-num_sub+A[k])
    num_sub = -h.heappushpop(tail, -A[-k-1])
    sum_blue.append(sum_blue[-1]-num_sub+A[-k-1])


print(max([r-b for r, b in zip(sum_red, sum_blue[::-1])]))
### BUGGY CODE ###

H,W = map(int,input().split())
g = [list(input()) for i in range(H)]

c = [[0 for w in range(W)] for h in range(H)]

hs = [0 for i in range(W)]

for h in range(H):
    ws = 0

    for w in range(W):
        if g[h][w] == '#':

            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1

            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1

    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1

h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]

#print(c)

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,c[h][w])

print(ans)
'''
横方向と縦方向に分けてプログラムを作成してまとめた
横方向
for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1

縦方向
hs = [0 for i in range(W)]
for h in range(H):
    for w in range(W):
        if g[h][w] == '#':
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]
'''


### FIXED CODE ###

H,W = map(int,input().split())
g = [list(input()) for i in range(H)]

c = [[0 for w in range(W)] for h in range(H)]

hs = [0 for i in range(W)]

for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]

#print(c)

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,c[h][w])

print(ans)
'''
横方向と縦方向に分けてプログラムを作成してまとめた
横方向
for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1

縦方向
hs = [0 for i in range(W)]
for h in range(H):
    for w in range(W):
        if g[h][w] == '#':
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]
'''
### BUGGY CODE ###

def main():
  from fractions import Fraction
  from collections import defaultdict
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      dd_ba[Fraction(-b, a)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  flag_dd = defaultdict(bool, {})

  iterator = list(dd_ba.items())
  for key,value in iterator:
    if flag_dd[key]:
      continue
    x = Fraction(key.denominator, -(key.numerator))
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    flag_dd[x] = True

  ans += zero_zero_count - 1
  print(ans%MOD) 

if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from math import gcd
  from collections import defaultdict
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      if a * b < 0:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(b//g, a//g)] += 1
      else:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(-b//g, a//g)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  dd_flag = defaultdict(bool, {})

  for key,value in tuple(dd_ba.items()):
    if dd_flag[key]:
      continue
    
    key_0 = key[0]
    key_1 = key[1]
    if key_0<0:
      x = (key_1, -key_0)
    else:
      x = (-key_1, key_0)
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    dd_flag[x] = True

  ans += zero_zero_count - 1
  print(ans%MOD) 

if __name__=='__main__':
  main()
### BUGGY CODE ###

n, m = map(int, input().split())
lst = [[] for _ in range(n + 1)]
py = []
for i in range(m):
    p, y = map(int, input().split())
    py.append([p, y])
    lst[p].append(y)

for i in range(n+1):
    lst[i] = sorted(lst[i])

for i, j in py:
    print(str(i).zfill(6) + str(lst[i].index(j)+1).zfill(6))

### FIXED CODE ###

n, m = map(int, input().split())
lst = [[] for _ in range(n + 1)]
py = [tuple(map(int, input().split())) for i in range(m)]

for i, (p, y) in enumerate(py):
    lst[p].append((y, i))

ans = [None] * m

for p, l in enumerate(lst):
    l.sort()
    for j, (y, i) in enumerate(l):
        ans[i] = str(p).zfill(6) + str(j + 1).zfill(6)

print(*ans, sep=('\n'))
### BUGGY CODE ###

N, M= map(int, input().split())
B=[]
for i in range(N):
    B.append([None]*2)
    l=input().split()
    B[i][0]=int(l[1])
    B[i][1]=int(l[0])
B.sort(reverse=True)
h=[0]*(M+1)
a=0
d=M+1
for i in range(N):
    if d>B[i][1]:
      for j in range(B[i][1],d):
        if h[j]==0:
            h[j]=1
            a+=B[i][0]
            break
      else:
        d=B[i][1]
print(a)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
l=[[] for i in range(10**5)]
for i in range(N):
    a,b=map(int,input().split())
    l[a-1].append(b)
h=[]
import heapq
a=0
for i in range(M):
    for j in l[i]:
        heapq.heappush(h,-j)
    if h:
        a-=heapq.heappop(h)
print(a)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
ans = 0
for i in range(N):
    flag = 0
    for j in range(N):
        if i!=j and A[i]%A[j] == 0:
            #print("i=%d,j=%d,A[j]=%d"%(i,j,A[j]))
            flag +=1
            break
    if flag == 0:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
D = set() #重複
S = set() #初出
for i in range(N):
    if A[i] in S:
        D.add(A[i])
    else:
        S.add(A[i])
#print(D,S)
M = max(S)
#print(M)
X = [1 for i in range(M+1)] #i番目が数字iに対応、条件を満たせば1、満たさなければ0にする。
#print(X)
for a in S:
    if a in D:
        X[a]=0 #aが重複していれば、aは条件を満たす数字ではない。
    for i in range(2*a,M+1,a):
        X[i]=0 #aはおｋ、2a以上のaの倍数は条件を満たさない。
        
ans = 0
for i in range(N):
    if X[A[i]]==1: #数字A(i)に対応するX[i]の箇所を参照して、条件を満たしていれば+1する
        ans += 1
print(ans)
### BUGGY CODE ###

A,B = map(int,input().split())
ans = 0

jouzan = 0
if B >= 10**11:
    jouzan = 11
elif B >= 10**10:
    jouzan = 10
elif B >= 10**9:
    jouzan = 9
elif B >= 10**8:
    jouzan = 8
elif B >= 10**7:
    jouzan = 7
elif B >= 10**6:
    jouzan = 6
elif B >= 10**5:
    jouzan = 5
elif B >= 10**4:
    jouzan = 4

for i in range(A,B+1):
    if i == 10**2 and jouzan != 0:
        ans = ans ^ 10**jouzan
        i = 10**jouzan + 1
    if i == 10**3 and jouzan != 0:
        ans = ans ^ 10**jouzan
        i = 10**jouzan + 1
    if i == 10**4 and jouzan != 0:
        ans = ans ^ 10**jouzan
        i = 10**jouzan + 1
    if i == 10**5 and jouzan != 0:
        ans = ans ^ 10**jouzan
        i = 10**jouzan + 1
    if i == 10**6 and jouzan != 0:
        ans = ans ^ 10**jouzan
        i = 10**jouzan + 1
    if i == 10**7 and jouzan != 0:
        ans = ans ^ 10**jouzan
        i = 10**jouzan + 1
    if i == 10**8 and jouzan != 0:
        ans = ans ^ 10**jouzan
        i = 10**jouzan + 1
    if i == 10**9 and jouzan != 0:
        ans = ans ^ 10**jouzan
        i = 10**jouzan + 1
    if i == 10**10 and jouzan != 0:
        ans = ans ^ 10**jouzan
        i = 10**jouzan + 1
    
    ans = ans ^ i
    
print(ans)

### FIXED CODE ###

A,B = map(int,input().split())
ans = 0

def calc(a):
    cnt = (a + 1) / 2
    ans = int(cnt  % 2)
    if a % 2 == 0:
        ans ^= a
        
    return ans
    
print(calc(B)^calc(A-1))
### BUGGY 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])

### FIXED 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)