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

from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))
maps2 = list(maps2)

for i in range(1, H + 1):
    for l in range(1, W + 1):
        maps = copy.deepcopy(maps2)
        if maps2[i][l] != "#":
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth
                maps[y][x] = "$"

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
print(MAX)


### FIXED CODE ###

import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            maps[i][l] = "a"
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    maps[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    maps[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    maps[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    maps[y][x - 1] = "a"
print(MAX)
### BUGGY CODE ###

n=int(input())
l=[list(str(input())) for i in range(n)]
cnt=0
nums=[x for x in range(n)]
for m in l:
  m.sort()
for i in nums[:n-1]:
  for j in l[i+1:]:
    if(l[i]==j):
      cnt+=1
print(cnt)

### FIXED CODE ###

from collections import Counter
n=int(input())
l=["".join(sorted(list(str(input())))) for i in range(n)]
cnt=Counter(l)
ans=0
for i in set(l):
  n=cnt[i]
  ans+=n*(n-1)//2
print(ans)
### BUGGY CODE ###

N=int(input())
listA=list(map(int,input().split()))
ans=0
for i in range(N-1):
  if listA[i]<N-i:
    for k in range(i+1,N):
      if abs(k-i)==listA[i]+listA[k]:
        ans+=1
print(ans)        

### FIXED CODE ###

N=int(input())
listA=list(map(int,input().split()))
ans=0
L=[]
R=[]
L1=[0]*N
R1=[0]*N
for i in range(N):
  L+=[i+listA[i]]
  R+=[i-listA[i]]
  try:
    L1[i+1+listA[i]]+=1
  except:
    pass
  try:
    if i-listA[i]>0:
      R1[i+1-listA[i]]+=1
  except:
    pass
for i in range(N):
  ans+=L1[i]*R1[i]
print(ans)
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    maze.append(input())
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            ne = deque([[i,j]])
            dist = [[0]*w for k in range(h)]
            checked = [[0]*w for k in range(h)]
            while len(ne) != 0:
                cur = ne.popleft()
                checked[cur[0]][cur[1]] = 1
                for l in range(4):
                    t = cur[0]+dy_dx[l][0]
                    u = cur[1]+dy_dx[l][1]
                    if (0 <= t <= h-1) and (0 <= u <= w-1):
                        if checked[t][u] == 0:
                            if maze[t][u] == '.':
                                dist[t][u] = dist[cur[0]][cur[1]]+1
                                ne.append([t,u])
                                ans = max(ans,dist[t][u])
print(ans)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    maze.append(input())
flag = True
check = '.'*w
for i in range(h):
    if maze[i] != check:
        flag = False
        break
if flag:
    print(h+w-2)
else:
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                ne = deque([[i,j]])
                dist = [[0]*w for k in range(h)]
                checked = [[0]*w for k in range(h)]
                while len(ne) != 0:
                    cur = ne.popleft()
                    checked[cur[0]][cur[1]] = 1
                    for l in range(4):
                        t = cur[0]+dy_dx[l][0]
                        u = cur[1]+dy_dx[l][1]
                        if (0 <= t <= h-1) and (0 <= u <= w-1):
                            if checked[t][u] == 0:
                                if maze[t][u] == '.':
                                    dist[t][u] = dist[cur[0]][cur[1]]+1
                                    ne.append([t,u])
                                    ans = max(ans,dist[t][u])
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

    dec_a = [0] * (N)
    for x in range(1, N):
        if S[x] == 'C' and S[x-1] == 'A':
            S[x-1] = 'a'
        dec_a[x] = S[:x+1].count('a')


    for i in range(Q):
        L, R = map(int, input().split())
        print(dec_a[R-1] - dec_a[L-1])

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    cnt_ac = 0
    arr_ac = [0] * (N)
    for x in range(0, N-1):
        if S[x:x+2] == 'AC':
            cnt_ac += 1
        arr_ac[x+1] = cnt_ac

    for i in range(Q):
        L, R = map(int, input().split())
        print(arr_ac[R-1] - arr_ac[L-1])


main()
### BUGGY CODE ###

(N, K, Q) = map(int, list(input().split()))

A = list(map(int,[input() for i in range(Q)]))
for y in range(1, N+1):
    if K - Q + A.count(y) > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

(N, K, Q) = map(int, list(input().split()))

points = []
for x in range(N):
    points.append(K-Q)

for y in range(Q):
    ansed = int(input()) - 1
    points[ansed] += 1

for point in points:
    if point > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n,m=map(int,input().split())
h=[int(w) for w in input().split()]
x=[[0]*(n) for j in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    x[a-1][b-1]=1
    x[b-1][a-1]=1
ans=0
for i in range(n):
    if sum(x[i])==0:
        #print(i)
        ans+=1
    else:
        t=0
        for j in range(len(x[i])):
            if x[i][j]==1:
                t=max(t,h[j])
        if h[i]>t:
            ans+=1
            #print(i,j)
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
h=[int(w) for w in input().split()]
x=[0]*(n)
for i in range(m):
    a,b=map(int,input().split())
    
    x[a-1]=max(h[b-1],x[a-1])
    x[b-1]=max(h[a-1],x[b-1])
        
ans=0
for i in range(n):
    if (h[i]>x[i]) or x[i]==0:
        ans+=1
print(ans)
### BUGGY CODE ###

from collections import Counter
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+1000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n,m=map(int, input().split())
mb=[]
while m>1:
    for i in range(2,m+1):
        if m%i==0:
            mb.append(i)
            m//=i
            break

mb2=Counter(mb)
    
mblist=list()
for i in mb2:
    a = cmb(mb2[i]+n-1,mb2[i],mod)
    mblist.append(a)
ans=1
for i in mblist:
    ans=(ans*i)%mod
print(ans)

### FIXED CODE ###

from collections import Counter
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+1000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n,m=map(int, input().split())
mb=[]
while m>1:
    for i in range(2,int(m**0.5)+1):
        if m%i==0:
            mb.append(i)
            m//=i
            break
    else:
        mb.append(m)
        m//=m
mb2=Counter(mb)
    
mblist=list()
for i in mb2:
    a = cmb(mb2[i]+n-1,mb2[i],mod)
    mblist.append(a)
ans=1
for i in mblist:
    ans=(ans*i)%mod
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

n=int(input())
a=list(map(float,input().split()))
dp={}

def foo(i,h,t,p):
	if i==n-1:
		if h>t:
			return p
		else:
			return 0
	return foo(i+1,h+1,t,p*a[i+1])+foo(i+1,h,t+1,p*(1-a[i+1]))

print(foo(-1,0,0,1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

n=int(input())
a=list(map(float,input().split()))
dp=[[0.0 for _ in range(n+1)] for _ in range(n+1)]
dp[1][1]=a[0]
dp[1][0]=1-a[0]
 
for i in range(2, n+1):
    for j in range(i+1):
        dp[i][j]=a[i - 1] * dp[i - 1][j - 1]+(1 - a[i - 1])*dp[i - 1][j]
 
print(sum(dp[n][n // 2 + 1:]))
### BUGGY CODE ###

class SegmentTree:
    def __init__(self,orig,func,unit):
        _len= len(orig)
        self.func = func
        self.size = 1 << (_len-1).bit_length()
        self.tree = [unit] * self.size + orig + [unit] *(self.size-_len)
        self.unit = unit
        
        for i in range(self.size -1,0,-1):
            self.tree[i] = func(self.tree[i*2], self.tree[i*2+1])
            
    def update(self, i, v):
        i+=self.size
        self.tree[i] = v
        while i:
            i//=2
            self.tree[i]=self.func(self.tree[i*2],self.tree[i*2+1])
    
    def find(self,l,r):
        l+=self.size
        r+=self.size
        ret=self.unit
        while l<r:
            if l&1:
                ret = self.func(ret,self.tree[l])
                l+=1
            if r&1:
                r-=1
                ret=self.func(ret,self.tree[r])
            l//=2
            r//=2
        return ret
import sys
input=sys.stdin.readline
input()
def lam(x,y):
  return x|y
seg = SegmentTree([set(x) for x in input()[:-1]],lam, set())
ans = []
for _ in range(int(input())):
  f, x, y = input().split()
  if f == "1":
    seg.update(int(x) - 1, set(y))
  else:
    ans.append(len(seg.find(int(x) - 1, int(y))))
print(*ans)

### FIXED CODE ###

class SegmentTree:
    def __init__(self,orig,func,unit):
        _len= len(orig)
        self.func = func
        self.size = 1 << (_len-1).bit_length()
        self.tree = [unit] * self.size + orig + [unit] *(self.size-_len)
        self.unit = unit
        
        for i in range(self.size -1,0,-1):
            self.tree[i] = func(self.tree[i*2], self.tree[i*2+1])
            
    def update(self, i, v):
        i+=self.size
        self.tree[i] = v
        while i:
            i//=2
            self.tree[i]=self.func(self.tree[i*2],self.tree[i*2+1])
    
    def find(self,l,r):
        l+=self.size
        r+=self.size
        ret=self.unit
        while l<r:
            if l&1:
                ret = self.func(ret,self.tree[l])
                l+=1
            if r&1:
                r-=1
                ret=self.func(ret,self.tree[r])
            l//=2
            r//=2
        return ret
      
import sys
input = sys.stdin.readline
from operator import or_

input()
seg = SegmentTree([1 << ord(x) - 97 for x in input()[:-1]], or_, 0)
ans = []
for _ in range(int(input())):
  f, x, y = input().split()
  if f == "1":
    seg.update(int(x) - 1, 1 << ord(y) - 97)
  else:
    ans.append(bin(seg.find(int(x) - 1, int(y))).count("1"))
print(*ans)
### BUGGY CODE ###

from collections import defaultdict


n = int(input())
A = list(map(int, input().split()))


def divisor(n):
    div_list = []
    limit = int(n**0.5) + 1
    for div in range(1, limit):
        if n % div == 0:
            div2 = n // div
            div_list.append(div)
            if div != div2:
                div_list.append(div2)
    
    return div_list


        
A_dict = defaultdict(int)
for a in A:
    A_dict[a] += 1

    
ans = n
for a in A:
    divs = divisor(a)
    for div in divs:
        if div == a:
            
            if A_dict[div] >= 2:
                ans -= 1
                break
        else:
            if A_dict[div] >= 1:
                ans -= 1
                break
            

print(ans)

### FIXED CODE ###

import numpy as np
from collections import Counter


n = int(input())
A = list(map(int, input().split()))
A.sort()
is_divisible = np.zeros(10**6+1, dtype=np.int64)


def update(num):
    nums = np.arange(num, 10**6+1, num)
    is_divisible[nums] = True

counter = Counter(A)
ans = 0
for a, count in counter.items():
    if count == 1 and not is_divisible[a]:
        ans += 1
        
    update(a)

print(ans)
### BUGGY CODE ###

N,Q=map(int,input().split())

S=input()

cnt=[0 for _ in range(len(S))]

prev=""

for i in range(len(S)):
	if prev + S[i] == "AC":
		cnt[i]+=1
	prev = S[i]

for q in range(Q):
 	L,R=map(int,input().split())
 	ans = 0
 	# 本当は、L-1からだが、
 	# "AC"のCの部分をカウントしているので、
 	# 最初の文字がその"C"だったら集計してはいけない
 	for i in range(L,R):
 		ans += cnt[i]
 	print(ans)



### FIXED CODE ###

N,Q=map(int,input().split())

S=input()

# 最初からNまでに何個ACがあったか
cnt=[0 for _ in range(N)]

prev=""

for i in range(N):
	if S[i]=="C":
		if prev=="A":
			cnt[i]+=1
	if i!=0:
		cnt[i]+=cnt[i-1]
	prev = S[i]

for q in range(Q):
 	L,R=map(int,input().split())
 	ans = cnt[R-1]-cnt[L-1]
 	print(ans)
### BUGGY CODE ###

a = int(input())
b = [list(map(int, input().split()))for _ in range(a)]
c = []
for i in range(len(b)):
    c.append(b[i].copy())
    if len(c) != 1:
        while True:
            if c[i][0] < c[i-1][0] or c[i][1] < c[i-1][1]:
                c[i][0] = c[i][0] + b[i][0]
                c[i][1] = c[i][1] + b[i][1]
            else:
                break
print(c[len(c)-1][0] + c[len(c)-1][1])


### FIXED CODE ###

a = int(input())
b = [list(map(int, input().split()))for _ in range(a)]
c = []
for i in range(len(b)):
    c.append(b[i].copy())
    if len(c) != 1:
        while True:
            if c[i][0] < c[i-1][0] or c[i][1] < c[i-1][1]:
                c[i][0] = b[i][0] * max((c[i-1][0] + b[i][0] - 1) // b[i][0], (c[i-1][1] + b[i][1] - 1) // b[i][1])
                c[i][1] = b[i][1] * max((c[i-1][0] + b[i][0] - 1) // b[i][0], (c[i-1][1] + b[i][1] - 1) // b[i][1])
            else:
                break
print(c[len(c)-1][0] + c[len(c)-1][1])
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    wv = [None] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp_i[j] = dp_im[j]
            elif dp_im[j - w] + v > dp_im[j]:
                dp_i[j] = dp_im[j - w] + v
            else:
                dp_i[j] = dp_im[j]

    ans = dp[-1][-1]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    wv = [None] * N
    for i in range(N):
        wv[i] = tuple(map(int, input().split()))

    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i, (w, v) in enumerate(wv, start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        for j in range(1, W + 1):
            if j < w:
                dp_i[j] = dp_im[j]
            else:
                a = dp_im[j - w] + v
                b = dp_im[j]
                if a > b:
                    dp_i[j] = a
                else:
                    dp_i[j] = b

    ans = dp[-1][-1]
    print(ans)


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

A, B, Q = map(int, input().split())
s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]
x = [int(input()) for i in range(Q)]

def search(a):
  cur = a
  sx, tx = [], [] #xiとsi、tiの差のリスト
  for si in s:
    sx.append(abs(si - a))
  for ti in t:
    tx.append(abs(ti - a))
  stmin = [[sx.index(min(sx)),min(sx)], [tx.index(min(tx)),min(tx)]]
  ans = min(stmin[0][1], stmin[1][1])
  
#  if stmin[0][1] <= stmin[1][1]: #sのほうが近いとき
  cur1 = s[stmin[0][0]]
  tcur = []
  for ti in t:
    tcur.append(abs(ti - cur1))
  ans1 = stmin[0][1] + min(tcur)
    
#  if stmin[0][1] > stmin[1][1]: #tのほうが近いとき
  cur2 = t[stmin[1][0]]
  scur = []
  for si in s:
    scur.append(abs(si - cur2))
  ans2 = stmin[1][1] + min(scur)
  
  print(min(ans1, ans2))
  
for xi in x:
  search(xi)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
  x = int(input())
  b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
  res = INF
  for S in [s[b - 1], s[b]]:
    for T in [t[d - 1], t[d]]:
      d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
      res = min(res, d1, d2)
  print(res)
### BUGGY CODE ###

N = int(input())
Ps = list(map(float, input().split()))

probs = [[None for _ in range(N+1)] for _ in range(N)]

probs[0][1] = Ps[0]
probs[0][0] = 1 - Ps[0]
for i in range(2, N+1):
  probs[0][i] = 0

for i in range(1, N):
  for k in range(0, N+1):
    if k == 0:
      probs[i][k] = probs[i-1][k]*(1-Ps[i])
    else:
      probs[i][k] = probs[i-1][k-1]*Ps[i] + probs[i-1][k]*(1-Ps[i])

# print(probs)

sum_all = sum(probs[N-1])
sum_ok = 0

start = int(N/2) + 1
for i in range(start, N+1):
  sum_ok += probs[N-1][i]

print(sum_ok / sum_all)

### FIXED CODE ###

# input
N = int(input())
Ps = list(map(float, input().split()))

# probs[i][k] : コインiまでを投げて表がk枚出る確率
probs = [[0 for _ in range(N+1)] for _ in range(N)]

probs[0][1] = Ps[0]
probs[0][0] = 1 - Ps[0]
# for i in range(2, N+1):
#   probs[0][i] = 0

for i in range(1, N):
  for k in range(0, N+1):
    if k == 0:
      probs[i][k] = probs[i-1][k]*(1-Ps[i])
    else:
      probs[i][k] = probs[i-1][k-1]*Ps[i] + probs[i-1][k]*(1-Ps[i])

# print(probs)

sum_all = sum(probs[N-1])
sum_ok = 0

start = int(N/2) + 1
for i in range(start, N+1):
  sum_ok += probs[N-1][i]

print(sum_ok / sum_all)
### BUGGY CODE ###

def main():
  n=int(input())
  a=list(map(int,input().split()))
  tf=[1]*n
  n=n-1
#r=[]
#print(n)
#print(a)
  notdiv=True
  firstyn=0
  for i in range(n,-1,-1):
  #print(i)
  #notdiv=True
    if tf[i] ==0:
      continue
    for j in range(i):
    #print(a[j])
      if tf[j] ==0:
        continue
      if a[i]%a[j] == 0:
        tf[i]=0
      #break
      if a[j]%a[i] == 0:
        tf[j]=0
      #break
#print(tf)
  print(sum(tf))
main()

### FIXED CODE ###

def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]+1
  tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    if tf[a_i] ==False:
      for j in range(a_i,maxa,a_i):
        tf[j]=True
      if a_i < a[i+1]:
        #print(a_i)
        r+=1
  if tf[-1] ==False:
    r+=1
  print(r)
main()
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = []
tmp = 1
#最初のK番目まで
for i in range(k):
  tmp *= a[i]
ans.append(tmp)
for j in range(k,n):
  tmp *= a[j]
  tmp //= a[j-k]
  ans.append(tmp)
for t in range(n-k):
  if ans[t+1] > ans[t]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = []
for i in range(k,n):
  ans.append(a[i] - a[i-k])
for j in ans:
  if j > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import numpy as np
from collections import Counter

s = list(input())

l = len(s)
ans = 0

dp = np.zeros((3, l))

for i in range(l):
    dp[0][i] = int(s[i])
    dp[1][i] = (int(s[i]) * (10**(l-i-1))) % 2019

dp[2][l-1] = dp[0][l-1]

for i in range(l-2, -1, -1):
    dp[2][i] = (dp[1][i] + dp[2][i+1]) % 2019

c = Counter(dp[2])
for i, j in c.items():
    if i == 0:
        ans += int(j*(j+1)/2)
    elif j >= 2:
        ans += int(j*(j-1)/2)

print(ans)

### FIXED CODE ###

s = input()[::-1]
l = len(s)
MOD = 2019
ans = 0
mods = [0] * 2019
mods[0] = 1
num = 0
cnt = 0
d = 1
for i in s:
    num += int(i) * d
    num %= MOD
    mods[num] += 1
    d *= 10
    d %= MOD

for j in mods:
    ans += int(j*(j-1)/2)

print(ans)
### BUGGY CODE ###

from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
f = lambda x: "\n".join(" ".join(map(str, x[i])) for i in range(3))
def MAIN():
    MAP = [list(map(int, input().split())) for _ in range(N)]
    start = divmod(sum(MAP, []).index(0), N)
    goal = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
    ans = 0
    dp = deque([[start[0], start[1], 0, MAP]])
    LOG = [MAP]
    while dp:
        y, x, cnt, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                CM = deepcopy(M)
                CM[y][x], CM[ny][nx] = CM[ny][nx], CM[y][x]
                if not CM in LOG:
                    dp.append([ny, nx, cnt, CM])
                    LOG.append(CM)
MAIN()



### FIXED CODE ###

from collections import deque
N = 3
m = {8: {7, 5}, 7: {8, 6, 4}, 6: {7, 3}, 5: {8, 4, 2}, 4: {7, 5, 3, 1}, 3: {6, 4, 0}, 2: {5, 1}, 1: {4, 2, 0},
     0: {3, 1}}
goal = 123456780
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def solve():
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    zero = 8 - MAP.find("0")
    start = int(MAP)
    if start == goal:
        return 0
    dp = deque([(0, start, zero, 1), (0, goal, 0, 0)])
    TABLE = {start: (1, 0), goal: (0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            dp.append((cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()
### BUGGY 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]) 

### FIXED 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(['NO', 'YES'][((x+b-a+1)-(y+d-c+1))%3==0])
### BUGGY CODE ###

n = int(input())
p = [int(i) for i in input().split()]

m = []
for i in range(1,n+1):
    m.append(sorted(p[:i])[0])
    
ans = 0
for i in range(n):
    if m[i] == p[i]:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
ppp = list(map(int, input().split()))
curr = 10 ** 6
ans = 0
for p in ppp:
    if p < curr:
        ans += 1
        curr = p
print(ans)