Harryxun/stf_run huggingface dataset:
import numpy as np
N,M = map(int,input().split())
A = np.array([list(input()) for i in range(N)])
B = np.array([list(input()) for i in range(M)])
for i in range(M):
    for j in range(M):
        check = A[i:i+M,j:j+M]
        if (check == B).all():
            print("Yes")
            exit()
print("No")


### FIXED CODE ###

import numpy as np
N,M = map(int,input().split())
A = np.array([list(input()) for i in range(N)])
B = np.array([list(input()) for i in range(M)])
for i in range(N):
    for j in range(N):
        check = A[i:i+M,j:j+M]
        if check.shape != (M,M):
            continue
        if (check==B).all():
            print("Yes")
            exit()
print("No")
def koubai(a,b):
    if b==0:
        return a
    return(koubai(b,a%b))
def kouyaku(a,b):
    return a*b/koubai(a,b)

N=int(input())
ans=1
T=[0]*N
for i in range(N):
    ans=kouyaku(ans,int(input()))
print(int(ans))


### FIXED CODE ###

def koubai(a,b):
    if b==0:
        return a
    return(koubai(b,a%b))
def kouyaku(a,b):
    return a*b//koubai(a,b)

N=int(input())
if N==1:
    print(int(input()))
    exit()
ans=1
for i in range(N):
    ans=kouyaku(ans,int(input()))
print(int(ans))
from collections import deque
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
CB = deque([])
for i in range(M):
    B, C = map(int, input().split())
    CB.append([C, B])
CB = sorted(CB, reverse=True)
flag = False
c = 0
I = 0
for i in CB:
    I += i[1]
    if flag:
        break
    while c < I:
        if A[c] < i[0]:
            A[c] = i[0]
            c += 1
        else:
            c = I
            flag = True

print(sum(A))

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
CB = deque([])
for i in range(M):
    B, C = map(int, input().split())
    CB.append([C, B])
CB = sorted(CB, reverse=True)
flag = False
c = 0
I = 0
for i in CB:
    I += i[1]
    if flag:
        break
    while c < I:
        if c >= N:
            break
        if A[c] < i[0]:
            A[c] = i[0]
            c += 1
        else:
            c = I
            flag = True
print(sum(A))
# -*- coding: utf-8 -*-
from math import ceil, sqrt, atan, degrees

def solve():
    a,b,x = map(int, input().split())
    if 1/2*a*a*b >= x:
        t = atan(2*x/a/b/b)
    else:
        t = atan(a*a*a/2/(a*a*b-x))

    return str(90-degrees(t))
        
if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
from math import ceil, sqrt, atan, degrees

def solve():
    a,b,x = map(int, input().split())
    if a*a*b == x:
        return '0'
    elif 1/2*a*a*b >= x:
        t = atan(2*x/a/b/b)
    else:
        t = atan(a*a*a/2/(a*a*b-x))

    return str(90-degrees(t))
        
if __name__ == '__main__':
    print(solve())
n=int(input())
abc=[list(map(int,input().split())) for i in range(3)]
sum=0
for _ in range(n):
  abc[1].append(abc[0][i])
  abc[1].sort()
  abc[2].sort()
  p=abc[1].index(abc[0][i])
  for k in range(p+1,n):
    abc[2].append(a[1][k])
    q=abc[2].index(abc[1][k])
    sum+=n-q-1
    abc[1].remove(abc[0][i])
    abc[2].remove(a[1][k])
print(sum)
    
    
    

### FIXED CODE ###

import bisect
n= int(input())
a = list(map(int,input().split()))
a.sort()
b = list(map(int,input().split()))
b.sort()
c = list(map(int,input().split()))
c.sort()

ans = 0
for y in b:
    x = bisect.bisect_left(a, y)#挿入点はどの同じ値よりも左
    z = bisect.bisect_right(c, y) #挿入点はどの同じ値より右
    ans += x * (len(c) - z)#b<a * b > cの組み合わせ
print(ans)
from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}

try:
    while True:
        v=raw_input().split()
        print(m[''.join(v)][1])
except EOFError:
    pass

### FIXED CODE ###

from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
	v=q.pop(0)
	coor=m[''.join(v)][0]
	x=coor%X
	y=coor//X
	depth=m[''.join(v)][1]
	nextstr=''.join(v)
	if 0<x:
		v[coor],v[coor-1]=v[coor-1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'R']
		v[coor],v[coor-1]=v[coor-1],v[coor]
	if x<X-1:
		v[coor],v[coor+1]=v[coor+1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'L']
		v[coor],v[coor+1]=v[coor+1],v[coor]
	if 0<y:
		v[coor],v[coor-X]=v[coor-X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'D']
		v[coor],v[coor-X]=v[coor-X],v[coor]
	if y<Y-1:
		v[coor],v[coor+X]=v[coor+X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'U']
		v[coor],v[coor+X]=v[coor+X],v[coor]

try:
	while True:
		v=raw_input().split()
		print(m[''.join(v)][1])
except EOFError:
	pass
string = input()
if x-r=>0&y-r=>0&x+r=<W&y+r=<H:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

string = input()
numbers = string.split()
W = int(numbers[0])
H = int(numbers[1])
x = int(numbers[2])
y = int(numbers[3])
r = int(numbers[4])
if x-r>=0 and y-r>=0 and x+r<=W and y+r<=H:
    print('Yes')
else:
    print('No')
x = int(import())
print(x+x*x+x*x*x)

### FIXED CODE ###

x = int(input())
print(x+x*x+x*x*x)
def f(n):
    if memo[n] > 0:
        return memo[n]
    else:
        return f(n - 1) + f(n - 2)


N, M, *A = map(int, open(0).read().split())
memo = [-1] * (N + 2)
memo[0] = 1
memo[1] = 1
A = list(A) + [N + 1]
MOD = 10 ** 9 + 7
ans = 1
prev = 0
for a in A:
    if a == prev:
        ans = 0
        break
    ans *= f(a - 1 - prev)
    ans %= MOD
    prev = a + 1
print(ans)


### FIXED CODE ###

import sys


sys.setrecursionlimit(10 ** 6)


def f(n):
    if memo[n] > 0:
        return memo[n]
    memo[n] = f(n - 1) + f(n - 2)
    return memo[n]


N, M, *A = map(int, open(0).read().split())
memo = [1, 1] + [-1] * N
A = list(A) + [N + 1]
MOD = 10 ** 9 + 7
ans = 1
prev = 0
for a in A:
    if a == prev:
        ans = 0
        break
    ans *= f(a - 1 - prev)
    ans %= MOD
    prev = a + 1
print(ans)
N, M = map(int, input().split())
m = 0
if M > 0:
  broken = int(input())
else:
  broken = 0
a1, a2, a3 = 1, 0, 0
for i in range(1, N+1):
  a3, a2 = a2, a1
  if i == broken:
    a1 = 0
    m += 1
    if m < M:
      broken = int(input())
  else:
    a1 = (a2 + a3) % 1000000007
print(a1)

### FIXED CODE ###

l = sorted([int(x) for x in input().split()])
print(l[0]+l[1])
def main():
    import sys
    N=int(sys.stdin.readline())
    r=0
    for i in range(1,N+1):
        r+=(i+N-N%i)*(N//i)//2
        print(i,r,(i+N-N%i)*(N//i)//2,N-N%i)

    
main()

### FIXED CODE ###

def main():
    import sys
    N=int(sys.stdin.readline())
    r=0
    for i in range(1,N+1):
        r+=(i+N-N%i)*(N//i)//2

    print(r)

    
main()
# 問題データを読み込む
def readQuestion(a,b):
    a,b=map(int,input().split())

# 解く
def solve(x):
    a,b=map(int,input().split())
    x=[]
    y=0
    high=0
    z=0
    u=0
    for i in range(1,1000):
        y+=i
        x.append(y)
    high = b-a
    z=high-1
    u=x[z]-b
    print(u)

# 全体
def main():
    x = readQuestion(a,b)
    answer = solve(x)
    print(answer)

# mainを呼び出す
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
def readQuestion():
    line = sys.stdin.readline()
    sline = line.rstrip()
    [rline,r1line]=sline.split(" ")
    a=int(rline)
    b=int(r1line)
    return a,b 

def solve(a,b):
    x=[]
    y=0
    high=0
    z=0
    u=0
    for i in range(1,1000):
        y+=i
        x.append(y)
    high = b-a
    z=high-1
    u=x[z]-b
    return u
# 全体
def main():
    x,y = readQuestion()
    answer = solve(x, y)
    print(answer)

# mainを呼び出す
if __name__ == '__main__':
    main()
N = int(input())
def factorize(n, already):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i ==0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])

    ret = []
    for a, b in arr:
        for i in range(1, b+1):
            ret.append(a*i)

    ret = set(ret) - set(already)
    return sorted(list(ret))[0]

already = []
z = 0
n = N
ans = 0
for _ in range(100000):
    z = factorize(n, already)
    if z > n or n == 1:
        break
    n = n // z
    already.append(z)
    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
def factorize(n):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i ==0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

if N == 1:
    print(0); exit()

f = factorize(N)
ans = 0
for p, i in f:
    j = 0
    while i > j:
        j += 1
        i -= j
        ans += 1
print(ans)
# -*- coding: utf-8 -*-
N,A,B =map(int,input(),split())
if (A * N) > B:
  print(B)
else:
  print(A*T)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N,A,B = map(int,input().split())
if A * N >= B:
  print(B)
else:
  print("{}".format(A*N))
n = int(input())
li = list(map(int,input().split()))

li.sort()

if li[0] > 0:
    print(sum(li)-2*li[0])
    for i in range(n-2):
        print(li[0],li[i+1])
        li[0] -= li[i+1]
    print(li[n-1],li[0])
elif li[n-1] < 0:
    print(abs(sum(li))+2*li[n-1])
    for i in range(n-1):
        print(li[n-1],li[i])
        li[n-1] -= li[i]
else:
    for i in range(n):
        if li[i] > 0:
            a = i-1
            break
    print(abs(sum(li[:a+1])) + sum(li[a+1:]))
    for i in range(n-a-2):
        print(li[0],li[a+1+i])
        li[0] -= li[a+1+i]
    for i in range(a+1):
        print(li[n-1],li[i])
        li[n-1] -= li[i]


### FIXED CODE ###

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

li.sort()

if li[0] >= 0:
    print(sum(li)-2*li[0])
    for i in range(n-2):
        print(li[0],li[i+1])
        li[0] -= li[i+1]
    print(li[n-1],li[0])
elif li[n-1] <= 0:
    print(abs(sum(li))+2*li[n-1])
    for i in range(n-1):
        print(li[n-1],li[i])
        li[n-1] -= li[i]
else:
    for i in range(n):
        if li[i] > 0:
            a = i-1
            break
    print(abs(sum(li[:a+1])) + sum(li[a+1:]))
    for i in range(n-a-2):
        print(li[0],li[a+1+i])
        li[0] -= li[a+1+i]
    for i in range(a+1):
        print(li[n-1],li[i])
        li[n-1] -= li[i]
S = str(input())
if S == Sunny:
    print('Cloudy')
elif S == Cloudy:
    print('Rainy')
else:
    print('Sunny')

### FIXED CODE ###

S = str(input())
if S == 'Sunny':
    print('Cloudy')
elif S == 'Cloudy':
    print('Rainy')
else:
    print('Sunny')
k,s=map(int,input().split())
ans=0
z=[i for i in range(k+1)]
for x in range(k+1):
    for y in range(k+1):
        a=s-x-y
        if a<=k and z[bisect.bisect_left(z,a)]==a:
            ans+=1
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if 0<=z<=k:
            ans+=1
print(ans)
N,X = map(int,input().split())

PforL = [1]
HforL = [1]
for i in range(1,51):
    PforL.append(PforL[i-1]*2+1)
    HforL.append(HforL[i-1]*2+3)

def recursive(n,x):
    if x<=n:
        return 0
    if x<=HforL[n-1]+1:
        return recursive(n-1,x-1)
    else:
        return PforL[n-1]+1+recursive(n-1,x-HforL[n-1]-2)

print(recursive(N,X))


### FIXED CODE ###

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

PforL = [1]
HforL = [1]
for i in range(1,51):
    PforL.append(PforL[i-1]*2+1)
    HforL.append(HforL[i-1]*2+3)

ans = 0
while 0<X:
    if(X<((HforL[N]-3)/2)+1):
        X -= 1
        N -= 1
        continue
    if(X==((HforL[N]-3)/2+1)):
        ans+=PforL[N-1]
        break
    if(X==((HforL[N]-3)/2+2)):
        ans+=PforL[N-1]+1
        break
    if(X<HforL[N]-1):
        ans += PforL[N-1]+1
        X -= 2+HforL[N-1]
        N -= 1
        continue
    if(X<=HforL[N]):
        ans += PforL[N]
        break
print(ans)
def resolve():

    n, m,x = map(int, input().split())
    c=[]
    a=[]
    ans=10**13
    nedan=0
    rikai=[0]*m
    for i in range(n):
        A = list(map(int, input().split()))
        c.append(A[0])
        a.append(A[1:])
        for j in range(m):
            rikai[j]+=a[i][j]
    if min(rikai)>=x:
        for Bin in range(2**n):
            N = [str(x) for x in list(str(bin(Bin+2**13)))]
            N.pop(0)
            N.pop(0)
            for hon in range(n):
                if N[hon + 1] == 1:
                    for aru in range(m):
                        rikai[aru]+=a[hon][aru]
                    nedan+=c[hon]
            if min(rikai)>=x:
                ans=min(ans,nedan)
            rikai=[]
            nedan=0
        print(ans)

    else:
        print(-1)
resolve()

### FIXED CODE ###

def resolve():

    n, m,x = map(int, input().split())
    c=[]
    a=[]
    ans=10**13
    nedan=0
    rikai=[0]*m
    for i in range(n):
        A = list(map(int, input().split()))
        c.append(A[0])
        a.append(A[1:])
        for j in range(m):
            rikai[j]+=a[i][j]

    if min(rikai)>=x:
        for Bin in range(1,2**n):
            rikai = [0] * m
            nedan = 0
            for hon in range(n):
                if (Bin>>hon) & 1:
                    for aru in range(m):
                        rikai[aru]+=a[hon][aru]
                    nedan+=c[hon]
            if min(rikai)>=x:
                ans=min(ans,nedan)
        print(ans)

    else:
        print(-1)
resolve()
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
for x in range(h):
    for y in range(w):
        if(s[x][y] == '#'):
            up = s[max(0, x-1)][y]
            down = s[min(h-1, x+1)][y]
            right = s[x][max(0, y-1)]
            left = s[x][max(w-1,  y+1)]
            if(up == '.' and down == '.' and right == '.' and left == '.'):
                print("No")
                exit()
print("Yes")


### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for i in range(h)]
up = down = right = left = '.'
for x in range(h):
    for y in range(w):
        if(list(s[x])[y] == '#'):
            if(y != w-1):
                right = list(s[x])[y+1]
            if(x != h-1):
                down = list(s[x+1])[y]
            if(x != 0):
                up = list(s[x-1])[y]
            if(y != 0):
                left = list(s[x])[y-1]
            if(up != '#' and down != '#' and right != '#' and left != '#'):
                print("No")
                exit()
            up = down = right = left = '.'
print("Yes")
import sys

def main():
    N, M = list(map(int, input().split()))
    
    inputs = [input().split() for i in range(M)]
    has_been_solved = set()

    penalty = {}
    correct = 0

    for i in inputs:
        
        num = int(i[0])
        if num in has_been_solved:
            continue

        if i[1] == 'AC':
            correct += 1
            has_been_solved.add(num)
        else:
            if num not in penalty:
                penalty[num] = 1
            else:
                penalty[num] += 1
    print(correct, sum([penalty[p] for p in  already]))         
        

if __name__ == "__main__":
    main()


### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*n
w=[0]*n
ac=0
wc=0
for _ in range(m):
    p,s=input().split()
    p=int(p)-1
    if a[p]==0:
        if s=='AC':
            a[p]=1
            ac+=1
            wc+=w[p]
        else:
            w[p]+=1
print(ac,wc)
X = int(input())
Y = int(input())

Z = X + (Y/2)

print(Z)

### FIXED CODE ###

x,y = map(int,input().split())

ans = x+y/2

print(int(ans))
S = input()

disp = []
for s in S:
    if s == "B":
        if len(s) > 0:
            disp.pop()
        continue
    disp.append(s)
print("".join(disp))

### FIXED CODE ###

S = input()

disp = []
for s in S:
    if s == "B":
        if len(disp) > 0:
            disp.pop()
        continue
    disp.append(s)
print("".join(disp))
age = int(input())
price = int(input())
if age >= 13:
    print(price)
elif 6 <= age <= 12:
    print(price // 2)
else:
    print(0)

### FIXED CODE ###

a, b = [int(x) for x in input().split()]

cost = 0
if a >= 13:
    cost = b
elif a >= 6:
    cost = b / 2
else:
    cost = 0

print(int(cost))
a=int(input())
b=list(map(int,input().split()))
c=0
for i in range(a):
  if b[i]>b[i+1]:
    b[i+1]=b[i+1]+1
    c=c+1
print(c)

### FIXED CODE ###

a=int(input())
b=list(map(int,input().split()))
c=0
for i in range(a-1):
  if b[i]>b[i+1]:
    c=c+b[i]-b[i+1]
    b[i+1]=b[i]
print(c)
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力

import copy

n, m = map(int, input().split())
ary = [int(s) for s in input().split()]

ary.sort()

ary2 = copy.copy(ary)
ary2.pop(0)
ary2.append(0)

sa = []

for i in range(0, m - 1):
    sa.append(ary2[i] - ary[i])

#print(sa)

for i in range(0, n -1):
    sa.remove(max(sa))

#print(sa)

print(sum(sa))

### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力

import copy

n, m = map(int, input().split())
ary = [int(s) for s in input().split()]

if n < m :
    ary.sort()
    sa = []
    
    for i in range(0, m - 1):
        sa.append(ary[i + 1] - ary[i])
    
    #print(sa)
    
    sa.sort()
    
    for i in range(0, n - 1):
        sa.pop(-1)
    
    print(sum(sa))
else :
    print(0)
x=int(input())
if (x>=30):
  print(‘Yes’)
else:
  print(‘No’)

### FIXED CODE ###

T=int(input())
if (T>=30):
    print("Yes")
else:
    print("No")
N = list(map(int,input().split()))

row = ""

if N[1] == 0:
    print(0)
else:
    remain = N[0] - N[1] - N[2]
    row += "b"*N[1]+"a"*N[2]+"b"*remain
    print(row.count("b"))        

### FIXED CODE ###

N, A, B = map(int, input().split())
ans = N // (A + B) * A
rem = N % (A + B)
ans += min(rem, A)
print(ans)
import math


def lcm(a, b):
    return a * b // math.gcd(a, b)


def f(n, A):
    return sum([n % x for x in A])


def main():
    N = int(input())
    A = list(map(int, input().split()))
    retval = 1
    for a in A:
        retval = lcm(a, retval)
    print(f(retval - 1, A))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    print(sum([x-1 for x in A]))


if __name__ == "__main__":
    main()
print(sys.stdin)

### FIXED CODE ###

if len(set(input().split())) == 2:
  print("Yes")
else:
  print("No")
n=int(input())
g={(i,j):set() for i in range(n+1) for j in range(n+1) if i<j}
visit={(i,j):0 for i in range(n+1) for j in range(n+1) if i<j}
d={(i,j):0 for i in range(n+1) for j in range(n+1) if i<j}

inf=10**10

for i in range(1,n+1):
    last=(0,1)
    for j in list(map(int,input().split())):
        current=(min(i,j),max(i,j))
        g[last].add(current)
        last=current

def dfs(u):
    if visit[u]==2:
        return d[u]
        
    if len(g[u])==0:
        return 0
    
    ans=0
    visit[u]=1
    for v in g[u]:
        if visit[v]==1:
            print(-1)
            exit(0)
        
        ans=max(ans,1+dfs(v))
    
    visit[u]=2
    d[u]=ans
    return d[u]

print(dfs((0,1)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n=int(input())
g=[set() for _ in range(n*(n-1)//2+1)]
visit=[0]*(n*(n-1)//2+1)
d=[0]*(n*(n-1)//2+1)

for i in range(1,n+1):
    last=0
    for j in list(map(int,input().split())):
        mi,ma=(min(i-1,j-1),max(i-1,j-1))
        current=ma*(ma-1)//2+mi+1
        g[last].add(current)
        last=current

def dfs(u):
    if visit[u]==2:
        return d[u]
    
    ans=0
    visit[u]=1
    for v in g[u]:
        if visit[v]==1:
            print(-1)
            exit(0)
        
        d[u]=max(d[u],1+dfs(v))
    
    visit[u]=2
    return d[u]

print(dfs(0))
import math
A,B,K=map(int,input().split())
C=math.gcd(A,B)
count=0
for x in range(C,-1,-1):
    if C%x==0:
        count+=1
        if count==K:
            print(x)
            break



### FIXED CODE ###

import fractions
A,B,K=map(int,input().split())
C=fractions.gcd(A,B)
cnt=0
for x in range(C,0,-1):
    if C%x==0:
        cnt+=1
        if cnt==K:
            print(x)
            break
s=input()
k=int(input())
a=[]
for i in range(k):
  for j in range(len(s)-i):a.append(s[j:j+i+1])
a.sort()
for i in range(1,len(a)):
  if a[-i]==a[-i-1]:del a[-i]
print(a[k-1])

### FIXED CODE ###

s=input()
k=int(input())
a={s}
for i in range(k):
  for j in range(len(s)-i):a.add(s[j:j+i+1])
print(sorted(list(a))[k-1])
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [0, 0] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.append((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(v if (v := cost[d[0]][d[1]]) < float('inf') else -1)


### FIXED CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.appendleft((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)
N,Q=map(int,input().split())
S=input()
Sum=['']
for i in range(N):
    g=0 if i==0 else 1
    Sum.append(Sum[i]+S[i])
for i in range(Q):
    l,r=map(int,input().split())
    print(Sum[-1][l-1:r].count('AC'))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
Sum=[0,0]
for i in range(1,N):
    if S[i-1]=='A'and S[i]=='C':
        Sum.append(Sum[-1]+1)
    else:
        Sum.append(Sum[-1])
for i in range(Q):
    l,r=map(int,input().split())
    print(Sum[r]-Sum[l])