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

import sys
from heapq import heappush as hpu
from heapq import heappop as hpo
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 10
sb = [-(b[i] * base + i) for i in range(N) if a[i] != b[i]]
h = []
for t in sb: hpu(h, t)
res = 0
while len(h):
  v = hpo(h)
  i = -v % base
  v = -v // base
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hpu(h, -(b[i] * base + i))
print(res)

### FIXED CODE ###

import sys
from heapq import heappush as hpu
from heapq import heappop as hpo
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 6
sb = [-(b[i] * base + i) for i in range(N) if a[i] != b[i]]
h = []
for t in sb: hpu(h, t)
res = 0
while len(h):
  v = hpo(h)
  i = -v % base
  v = -v // base
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hpu(h, -(b[i] * base + i))
print(res)
### BUGGY CODE ###

import sys, time
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
a = [list(map(int, input().split()))[::-1] for _ in range(n)]
#print(*a, sep="\n")
opponent = [-1 for _ in range(n)]
played = list(range(n))
match = 0
day = 0
while match < n*(n-1)//2:
	approved = False
	for i in played:
		if a[i] != []:
			opponent[i] = a[i].pop()-1
	played = []
	#print(opponent)
	for i in range(n):
		if opponent[i] != -1 and opponent[opponent[i]] == i:
			approved = True
			match += 1
			played += [i, opponent[i]]
			opponent[opponent[i]] = -1
			opponent[i] = -1
	#print(opponent)
	if not approved:
		print(-1)
		sys.exit()
	day += 1
print(day)

### FIXED CODE ###

import sys, time
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
a = [list(map(int, input().split()))[::-1] for _ in range(n)]
#print(*a, sep="\n")
opponent = [-1 for _ in range(n)]
match = 0
day = 0
start_time = time.time()
while match < n*(n-1)//2:
	approved = False
	for i in range(n):
		if a[i] != [] and opponent[i] == -1:
			opponent[i] = a[i].pop()-1
	#print(opponent)
	for i in range(n):
		if opponent[i] != -1 and opponent[opponent[i]] == i:
			approved = True
			match += 1
			opponent[opponent[i]] = -1
			opponent[i] = -1
	#print(opponent)
	if not approved:
		print(-1)
		sys.exit()
	now = time.time()
	#print(start_time, now, now - start_time)
	if now-start_time > 1.6:
		print(n*(n-1)//2)
		sys.exit()
	day += 1
print(day)
### BUGGY CODE ###

from functools import reduce
from copy import copy

N = int(input())

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

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)

    return arr

facts = factorization(N)

def dfs(arr, depth):
    if depth == len(facts):
        left = reduce(lambda a,b: a * b, [f for i, f in enumerate(facts) if arr[i]], 1)
        right = reduce(lambda a, b: a * b, [f for i, f in enumerate(facts) if not arr[i]], 1)
        return left + right
    left_arr = copy(arr)
    left_arr.append(True)
    right_arr = copy(arr)
    right_arr.append(False)
    left = dfs(left_arr, depth+1)
    right = dfs(right_arr, depth + 1)
    return min(left, right)
print(dfs([], 0) - 2)

### FIXED CODE ###

N = int(input())
answer = 1000000000000
for i in range(1, int(N ** (0.5)) + 2):
    if N % i == 0:
        j = N // i
        if i + j - 2 < answer:
            answer = i + j - 2
print(answer)
### BUGGY CODE ###

n = int(input())
a=1
for i in range(n):
	a = a * (i + 1)
print(a%(7+10**9))

### FIXED CODE ###

import math
print(math.factorial(int(input()))%(7+10**9))
### BUGGY CODE ###

#E
n,m,k = list(map(int,input().split()))
fac = [1 for i in range(n)]
finv = [1 for i in range(n)]
inv = [1 for i in range(n)]
MOD = 998244353
for i in range(2,n):
    fac[i] = fac[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD
def comb(n,k):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
ans = 0
for i in range(k+1):
#     print(comb(n-1,i),m*(m-1)**(n-i-1))
    ans += (comb(n-1,i)*m*((m-1)**(n-i-1)%MOD))%MOD
    ans %= MOD
print(ans)

### FIXED CODE ###

#E
n,m,k = list(map(int,input().split()))
fac = [1]*n
finv = [1]*n
inv = [1]*n
MOD = 998244353
for i in range(2,n):
    fac[i] = fac[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD
def comb(n,k):
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD

ans = 0
for i in range(k+1):
#     print(comb(n-1,i),m*(m-1)**(n-i-1))
    ans += comb(n-1,i)*m*pow(m-1,n-i-1,MOD)%MOD
    ans %= MOD
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
X = list(map(int, input().split()))
ans = float('inf')
for l in range(0, N-K+1):
    for r in range(l+K-1, N):
        ans = min(ans, abs(X[l]) + abs(X[l] - X[r]))
        ans = min(ans, abs(X[r]) + abs(X[l] - X[r]))
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
X = list(map(int, input().split()))
ans = float('inf')
for l in range(0, N-K+1):
    r = l + K - 1
    ans = min(ans, min(abs(X[l]), abs(X[r])) + abs(X[l] - X[r]))
print(ans)
### BUGGY CODE ###

N = int(input())
finish = [False] * N
As, Bs = [], []
A_,B_ = [],[]
for i in range(N):
    a,b = map(int, input().split())
    As.append((a*10**10+b,i))
    Bs.append((b*10**10+a,i))
    A_.append(a)
    B_.append(b)
from operator import itemgetter
cnt = 0
As.sort(reverse=True)
Bs.sort(reverse=True)

p_a = 0
p_b = 0
while sum(finish)<N:
    # 高橋くんのターン
    while True:
        a,i = As.pop()
        if not finish[i]:
            p_a += (a-B_[i])//10**10
            finish[i] = True
            cnt += 1
            break
    # 青木
    while True and cnt < N:
        b,i = Bs.pop()
        if not finish[i]:
            p_b += (b-A_[i])//10**10
            finish[i] = True
            cnt += 1
            break
    # print(cnt,p_a,p_b)

print(p_a-p_b)


### FIXED CODE ###

N = int(input())
ABs = []
sum_B = 0
for i in range(N):
    a,b = map(int, input().split())
    ABs.append(a+b)
    sum_B += b 
ABs.sort(reverse=True)
ans = sum(ABs[::2])-sum_B
print(ans)
### BUGGY CODE ###

X = input()
if len(X) >= 15 **5:
    for i in range(len(X)):
        if X[i] == "S":
            count_T = X[i:].count("T")
            break
    for i in range(len(X)-1,-1,-1):
        if X[i] == "T":
            count_S = X[:i+1].count("S")
            break
    pair = min(count_T,count_S)
    ans = len(X) - 2 * pair
    print(ans)
else:
    for i in range(10**5):
        note = X
        X = X.replace("ST","")
        if note == X:
            break
    print(len(X))

### FIXED CODE ###

X = input()
stack = []
for e in X:
    if e == "S":
        stack.append(e)
    elif stack == []:
        stack.append(e)
    elif stack[-1] == "T":
        stack.append(e)
    elif stack[-1] == "S":
        stack.pop(-1)
print(len(stack))
### BUGGY CODE ###

n=int(input())
j=list(map(int, input().split()))
for i in range(n):
    print(j.count(i+1))

### FIXED CODE ###

n=int(input())
r=[0]*n
j=list(map(int, input().split()))
for i in j:
    r[i-1]+=1
for i in r:
    print(i)
### BUGGY CODE ###

S = list(map(int, list(input())))
N = len(S)
CNT = [0]*2019
CNT[0] = 1
num = 0
for i in range(N):
    num = num * 10 + S[i]
    CNT[num * pow(10, N-i)%2019] += 1
ans = 0
for cnt in CNT:
    if cnt==0: continue
    ans += (cnt*(cnt - 1)) // 2
print(ans)

### FIXED CODE ###

S = list(map(int, list(input())))[::-1]
N = len(S)
CNT = [0]*2019
CNT[0] = 1
num = 0
d = 0
for i in range(N):
    num += S[i]*pow(10, d, 2019)
    num %= 2019
    CNT[num] += 1
    d += 1
ans = 0 
for cnt in CNT:
    ans += (cnt*(cnt - 1)) // 2
print(ans)
### BUGGY CODE ###

# APC001C - Vacant Seat
# if no vacant seat in [0, i)
# -> seat[0] == seat[i] if i % 2 else seat[0] != seat[i]
N = int(input())
print(0, flush=1)
seat_zero = input().rstrip()
if seat_zero == "Vacant":
    exit()
left, right = 0, N
for _ in range(19):
    mid = (left + right) // 2
    print(mid, flush=1)
    this_seat = input().rstrip()
    if this_seat = "Vacant":
        exit()
    if mid % 2 == (seat_zero != this_seat):
        left = mid
    else:
        right = mid

### FIXED CODE ###

# APC001C - Vacant Seat
def main():
    # if no vacant seat in [0, i)
    # -> seat[0] == seat[i] if i % 2 else seat[0] != seat[i]
    N = int(input())
    print(0, flush=1)
    seat_zero = input().rstrip()
    if seat_zero == "Vacant":
        return
    left, right = 0, N
    for _ in range(19):
        mid = (left + right) // 2
        print(mid, flush=1)
        this_seat = input().rstrip()
        if this_seat == "Vacant":
            return
        if mid % 2 == (seat_zero != this_seat):
            left = mid
        else:
            right = mid


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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

uninity = [0] * (N+1)
dp = [np.zeros(30,np.int64) for _ in range(N+1)]
answer = -1
for x in order[::-1]:
    p = parent[x]
    A = dp[x]
    twice = (A >= 2)
    if np.any(twice):
        k = np.where(twice)[0].max()
        A[:k] = 1
    lsb = np.where(A == 0)[0].min()
    if answer < lsb:
        answer += 1
    uninity[x] = lsb
    A[lsb] = 1
    A[:lsb] = 0
    A[A>0] = 1
    dp[p] += A

print(answer)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

full = (1 << 60) - 1
uninity = [0] * (N+1)
dp = [0] * (N+1)
twice = [0] * (N+1)
for x in order[::-1]:
    p = parent[x]
    n = twice[x].bit_length() - 1
    if n >= 0:
        dp[x] |= (1 << (n+1)) - 1
    can_use = full & (~dp[x])
    lsb = can_use & (-can_use)
    uninity[x] = lsb
    dp[x] |= lsb
    dp[x] &= full & ~(lsb - 1)
    
    twice[p] |= (dp[x] & dp[p])
    dp[p] |= dp[x]

x = max(uninity)
answer = x.bit_length() - 1
print(answer)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]

bc.sort(key = lambda x:x[1], reverse = True)

a.sort()

d = []
loop = 0

while True:
        for b, c in bc:
                d.extend([c] * b)
                loop += 1
        if len(d) > n:
                break
        elif loop == m:
                break

while True:
        if a[0] < d[0]:
                a.append(d[0])
                del a[0]
                del d[0]
        else:
                break
        
        if d == []:
                break

print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]

bc.sort(key = lambda x:x[1], reverse = True)

a.sort()

a_count = 0
for b, c in bc:
        if c > a[a_count]:
                for i in range(b):
                        if c > a[a_count]:
                                a[a_count] = c
                                a_count += 1    
                        else:
                                break
                        if a_count == n:
                                        break

        else:
                break
        if a_count == n:
                break        

print(sum(a))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
result = True

for i in range(n-1):
    for j in range(i+1,n):
        if a[i]^a[j] in a:
            pass
        else:
            result = False

a_unique = list(set(a))
if len(a_unique) > 3:
    result = False

if result == True:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
result = False

a_unique = list(set(a))

if n == 3:
    if a_unique[0]^a_unique[1] == a_unique[2]:
        result = True
    
elif len(a_unique) == 3:
    if a_unique[0]^a_unique[1] == a_unique[2]: 
        if a.count(a_unique[0]) == a.count(a_unique[1]) and a.count(a_unique[1]) == a.count(a_unique[2]):
            result = True

elif len(a_unique) == 1:
    if a_unique[0]^a_unique[0] == a_unique[0]:
        result = True

elif len(a_unique) == 2:
    if a_unique.count(a_unique[0]) == 1:
        if a_unique[0]^a_unique[1] == a_unique[1]:
            if a_unique[1]^a_unique[1] == a_unique[0]:
                if a.count(a_unique[0])*2 == a.count(a_unique[1]):
                    result = True
    elif  a_unique.count(a_unique[1]) == 1:
        if a_unique[0]^a_unique[1] == a_unique[0]:
            if a_unique[0]^a_unique[0] == a_unique[1]:
                if a.count(a_unique[1])*2 == a.count(a_unique[0]):
                    result = True

if len(a_unique) > 3:
    result = False    
            
if result:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###


def main():
    N,M = map(int, input().split())
    H = list(map(int, input().split()))
    H.insert(0,0)
    A = [0] * (M)
    B = [0] * (M)
    cnt = 0
    

    for index in range(M):
        A[index],B[index] = map(int, input().split())

    for index in range(1,len(H)):
        ok = True
        for jn in range(M):
            if A[jn] == index :
                if H[A[jn]] <= H[B[jn]]:
                    ok = False
                    break
            if B[jn] == index :
                if H[B[jn]] <= H[A[jn]]:
                    ok = False
                    break
        if ok :
            cnt+=1

    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    N,M = map(int, input().split())
    H = list(map(int, input().split()))
    H.insert(0,0)
    A = [0] * (M)
    B = [0] * (M)
    TOP = [0] * len(H)
    cnt = 0

    for index in range(M):
        A[index],B[index] = map(int, input().split())

    for jn in range(M):
        if H[A[jn]] <= H[B[jn]]:
            TOP[A[jn]] = 1
        if H[B[jn]] <= H[A[jn]]:
            TOP[B[jn]] = 1

    cnt = TOP.count(0) -1

    print(cnt)


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

n = int(input())
str_list = [input() for i in range(n)]
ans = 0
from collections import Counter
def verify_anagrams(first_word, second_word):
  if Counter(first_word) == Counter(second_word):
    return 1
  else:
    return 0
for i in range(n):
  for j in range(n-i-1):
    ans += verify_anagrams(str_list[i], str_list[j+i+1])
    
print(ans)

### FIXED CODE ###

from collections import Counter
import sys

input = sys.stdin.readline
n = int(input())
str_list = [''.join(sorted(input().rstrip())) for i in range(n)]
ans = 0
count_list = list(Counter(str_list).values())
for i in count_list:
  sum = 0
  for j in range(int(i)):
    sum += j
  ans +=sum
print(ans)
### BUGGY CODE ###

N = int(input())
def shiki(a, b, c):
    return a ** 2 + b ** 2 + c ** 2 + a * b + b * c + c * a

def condition(n):
    count = 0
    i = 0
    j = 0
    z = 1
    while shiki(i, j, z) <= n and n > 5:
        for i in range(1, 10):
            for j in range(1, 10):
                z = 1
                while shiki(i, j, z) <= n and n > 5:
                    if n == shiki(i, j, z):
                        if i == j and j == z and i == z:
                            count += 1
                        else:
                            count += 1
                    z += 1
    print(count)

for i in range(1, N+1):
    condition(i)

### FIXED CODE ###

N = int(input())
ans = [0] * 100000
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            ans[x*x+y*y+z*z+x*y+y*z+z*x-1] += 1
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return False
    if pair[x]>pair[y]:
        x,y=y,x
    pair[x]+=pair[y]    
    pair[y]=x
    return True

def size(x):
    return -pair[root(x)]

icase=0
if icase==0:
    n,m,k=map(int,input().split())
    g=[[] for i in range(n)]
    x=[[] for i in range(n)]
    a=[0]*m
    b=[0]*m
    pair=[-1]*n
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
        a[i]=ai-1
        b[i]=bi-1
        unite(a[i],b[i])
    for i in range(k):
        ci,di=map(int,input().split())
        x[ci-1].append(di-1)
        x[di-1].append(ci-1)

ii=0        
ss=size(ii)-len(g[ii])-len(x[ii])-1
strs=""
for i in range(n):
    ss=size(i)-1
    rooti=root(i)
    for gi in g[i]:
        if root(gi)==rooti:
            ss-=1
    for xi in x[i]:
        if root(xi)==rooti:
            ss-=1
    strs=strs+" "+str(ss)
print(strs[1:])
    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
#input = sys.stdin.readline
    
n,m,k=map(int,input().split())
pair=[-1]*n

def main():
#    n,m,k=map(int,input().split())
    g=[[] for i in range(n)]
    x=[[] for i in range(n)]
    a=[0]*m
    b=[0]*m
#    pair=[-1]*n
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
        a[i]=ai-1
        b[i]=bi-1
        unite(a[i],b[i])
    for i in range(k):
        ci,di=map(int,input().split())
        x[ci-1].append(di-1)
        x[di-1].append(ci-1)

#    strs=""
#    sss=[]
    for i in range(n):
        ss=size(i)-1
        rooti=root(i)
        for gi in g[i]:
            if root(gi)==rooti:
                ss-=1
        for xi in x[i]:
            if root(xi)==rooti:
                ss-=1
#        strs=strs+" "+str(ss)
#        sss.append(ss)
        print(ss,end=" ")
    print(" ")
    
def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return False
    if pair[x]>pair[y]:
        x,y=y,x
    pair[x]+=pair[y]    
    pair[y]=x
    return True

def size(x):
    return -pair[root(x)]


main()
### BUGGY CODE ###

n = int(input())
l = []
r = [0]*10**5
res = 0

for i in range(n):
    an = list(input())
    an.sort()
    an = "".join(map(str, an))
    #print(an)
    if an not in l:
        l.append(an)
    r[l.index(an)] += 1

for i in r:
    for j in range(i-1,0,-1):
        #print(j)
        res += j
else:
    print(res)


### FIXED CODE ###

# original_author prd_xxx
from collections import Counter

N = int(input())
S = [input() for i in range(N)]

# collections.Counter()を使うと0回目の時にバグらないので23行目elseを省略可能
ctr = Counter()
ctr = {}
ans = 0

for s in S:
    # 文字列を昇順に並べ替え
    # 文字列をリスト化し、sortしたものを文字列化
    a = ''.join(sorted(list(s)))

    # ソート済み文字列が以前に存在していたら、答えに前回の合計値を加算する
    # 1..0 2..1 3..3 4..6 5..10 ... 組み合わせの数n(n-1)/2があり、
    # 最後にO(n)で計算も可能だが、冗長。
    # 一個ずつ処理していくと、
    # 1..0 2..+1(1) 3..+2(3) 4..+3(6) 5..+4(10)の増加になる
    if a in ctr:
        ans += ctr[a]
    else:
        ctr[a] = 0

    ctr[a] += 1

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

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

count = 0

for i in range(n):
    temp = a[i]
    tempCount = 1

    j = i
    while j > 0:
        if temp & a[j - 1] != 0:
            count += tempCount
            break
        else:
            temp |= a[j - 1]
                
            tempCount += 1
            j -= 1
    else:
        count += tempCount

print(count)

### FIXED CODE ###

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

r = 0
tempSum = 0
xor = 0
count = 0

for l in range(n):
    while r < n and (tempSum + a[r]) == (xor ^ a[r]):
        tempSum += a[r]
        xor ^= a[r]
        r += 1
    
    count += (r - l)

    tempSum -= a[l]
    xor ^= a[l]

print(count)
### BUGGY CODE ###

N = int(input())
count = 0
lst = []
while N > 0:
  lst.append(N%10)
  N //= 10 
for i in lst:
  count += i
if count % 9 == 0:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

n = int(input())
result = sum(list(map(int, str(n))))
if result % 9 == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

n, q = [int(i) for i in input().split()]
s = input()
for i in range(q):
    l, r = [int(i) for i in input().split()]
    t = s[l-1:r]
    cnt = 0
    for i in range(len(t)-1):
        cnt += t[i] + t[i+1] == "AC"
    print(cnt)


### FIXED CODE ###

from itertools import accumulate
n, q = [int(i) for i in input().split()]
s = input()
m = [0] * (len(s) - 1)
for i in range(len(m)):
    if s[i:i+2] == "AC": m[i] = 1
a = [0] + list(accumulate(m))

for i in range(q):
    l,r = [int(i) for i in input().split()]
    print(a[r-1] - a[l-1])
### BUGGY CODE ###

n,m = map(int,input().split())
ans = 1
for i in range(1,m+1):
    if m%i==0:
        x = m//i
        if x>=n:
            ans = i
        else:
            break
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
ans = 1
for i in range(1,int(m**0.5)+1):
    if m%i==0:
        x = m//i
        if x>=n:
            ans = max(ans,i)
        if i>=n:
            ans = max(ans,x)
        
print(ans)
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
q=deque()
q.append(s)
d={s:0}
while q:
    y,x=q.popleft()
    for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.':
            if (ny,nx) not in d:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
            elif d[(ny,nx)]>d[(y,x)]:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
    for dy,dx in [(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(-2,-1),(-1,-1),(1,-1),(2,-1),(-2,0),(2,0),(-2,1),(-1,1),(1,1),(2,1),(-2,2),(-1,2),(0,2),(1,2),(2,2)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.':
            if (ny,nx) not in d:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]+1
            elif d[(ny,nx)]>d[(y,x)]+1:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]+1
if g in d:
    print(d[g])
else:
    print(-1)

### FIXED CODE ###

from collections import deque
INF=10**10
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
d=[[INF]*W for _ in range(H)]
d[s[0]][s[1]]=0
q=deque()
q.append(s)
while q:
    y,x=q.pop()
    for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.' and d[ny][nx]>d[y][x]:
            q.append((ny,nx))
            d[ny][nx]=d[y][x]
    for dy in range(-2,3):
        for dx in range(-2,3):
            if abs(dy)+abs(dx)<=1:
                continue
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if m[ny][nx]=='.' and d[ny][nx]>d[y][x]+1:
                q.appendleft((ny,nx))
                d[ny][nx]=d[y][x]+1
ans=d[g[0]][g[1]]
if ans<INF:
    print(ans)
else:
    print(-1)