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

import collections
from collections import OrderedDict

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

#出現回数のカウント
c = OrderedDict(collections.Counter(S))
ln = len(c.values())

#多い順に並べ替えた辞書をつくる
d = OrderedDict(sorted(c.items(), key = lambda x : x[1], reverse=True))
dval = list(d.values())
dkey = list(d.keys())

#回数が多い単語を抜き出したリストの制作
word = list()
word.append(dkey[0])
i=1
if ln>1:
    while dval[i-1]==dval[i]:
        word.append(dkey[i])
        i+=1
        if i==ln:
            break

#辞書順に並べ替える
dic = sorted(word)

#表示
for i in range(len(dic)):
    print(dic[i])

### FIXED CODE ###

import collections
from collections import OrderedDict

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

#出現回数のカウント
c = OrderedDict(collections.Counter(S))
ln = len(c.values())

#多い順に並べ替えた辞書をつくる
d = OrderedDict(sorted(c.items(), key = lambda x : x[1], reverse=True))
dval = list(d.values())
dkey = list(d.keys())

#回数が多い単語を抜き出したリストの制作
word = list()
word.append(dkey[0])
i=1
if ln>1:
    while dval[i-1]==dval[i]:
        word.append(dkey[i])
        i+=1
        if i==ln:
            break

#辞書順に並べ替える
dic = sorted(word)

#表示
for i in range(len(dic)):
    print(dic[i])
### BUGGY CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
*F, = map(int, input().split())
A, F = sorted(A), sorted(F, reverse=True)

def cond(x):
    k = 0
    for a, f in zip(A, F): k += max(a - (x // f), 0)
    return True if k <= K else False 

MIN = -1
MAX = 10**12 + 1
left, right = MIN, MAX # search range
while right - left > 1:
    mid = (left + right) // 2
    if cond(mid): right = mid
    else: left = mid
print(right)

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
*F, = map(int, input().split())
A, F = sorted(A), sorted(F, reverse=True)

def cond(x):
    k = 0
    for a, f in zip(A, F): k += max(a - (x // f), 0)
    return True if k <= K else False 

MIN = -1
MAX = 10**12 + 1
left, right = MIN, MAX # search range
while right - left > 1:
    mid = (left + right) // 2
    if cond(mid): right = mid
    else: left = mid
print(right)
### BUGGY CODE ###

from queue import deque
import heapq

def countposdoc(string):
    return string.count('D') + string.count('PD')

T = input()

queue = deque([T])


res = []
heapq.heapify(res)

while queue:
    string = queue.pop()

    if '?' not in string:
        heapq.heappush(res, (countposdoc(string), string))
    else:
        queue.append(string.replace('?', 'P', 1))
        queue.append(string.replace('?', 'D', 1))
print(heapq.nlargest(1, res)[0][1])

### FIXED CODE ###

T = input()

print(T.replace('?', 'D'))
### BUGGY CODE ###


import numpy as np
import math

k =int(input())
memo = [[[0]*k for _ in range(k)]  for _ in range(k)]
ans = 0

for i in range(k):
    for j in range(k):
        for l in range(k):
            ans += math.gcd(math.gcd(i+1,j+1),l+1)


print(ans)






### FIXED CODE ###

import math

k =int(input())
ans = 0
temp_list =[]


for i in range(k):
    for j in range(k):
        temp_list.append(math.gcd(i+1,j+1))

temp_set= list(set(temp_list))

memo = [0]*len(temp_set)

for i in temp_list:
    for j in range(len(temp_set)):
        if i == temp_set[j]:
            memo[j] += 1
            break

for i in range(k):
    for j in range(len(temp_set)):
        ans += memo[j] * math.gcd(temp_set[j],i+1)

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

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline
import numpy as np

def main():
    numbers=[]
    n = int(input())
    numbers=np.array(list(map(int,input().split())))
    left=[]
    right=[]
    left=np.cumsum(numbers[:1])
    right=np.cumsum(numbers[1:])
    for i in range(2,n):
        if abs(right[-1]-left[-1]) > abs(np.cumsum(numbers[i:])[-1] -np.cumsum(numbers[:i])[-1]):
            left=np.cumsum(numbers[:i])
            right=np.cumsum(numbers[i:])
    print(abs(right[-1]-left[-1]))

if __name__=="__main__":
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline
import numpy as np

def main():
    N=[]
    n = int(input())
    N=np.array(list(map(int,input().split())))
    Ncum=N.cumsum()
    L=Ncum[:-1]
    R=Ncum[-1]-L
    ans=np.abs(L-R).min()
    print(ans)

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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n=int(input())
ans=0
for i in range(1,n+1):
  ans=ans+i*len(make_divisors(i))
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
  ans=ans+((n//i)*((n//i)+1)*i)//2
print(ans)
### BUGGY CODE ###

L=[i for i in range(2,10**5)]
X=int(input())
while X > L[0]:
  a=L[0]
  for l in L:
    if not l%a:
      L.remove(l)
print(L[0])

### FIXED CODE ###

def is_prime(x):
  if x <= 1: return false
  i=2
  while i*i <= x:
    if not x%i: return False
    i+=1
  return True
 
X=int(input())
while not is_prime(X):
  X+=1
print(X)
### BUGGY CODE ###

#Stone Monument
a,b = map(int, input().split())
M = []
ans = []
for i in range(1,1000,1):
	n = 1/2*i*(i+1)
	M.append(n)
for i in range(0,999,1):
	n = int(i*(i+1)/2)
	for j in range(0,n,1):
		if (a + j == M[i]) and (b + j == M[i+1]):
			print(j)
			exit()


### FIXED CODE ###

#Stone Monument
a,b = map(int, input().split())
M = []
for i in range(1,1000,1):
	n = 1/2*i*(i+1)
	M.append(n)
n = b-a-1
print(int(M[n-1]-a))
### BUGGY CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
ac = collections.Counter(a)
q = int(input())
ans = []
for i in range(q):
    b, c = map(int, input().split())
    tmp = ac[b]
    del ac[b]
    ac[c]+= tmp
    ans.append(sum(num*size for num, size in ac.items()))

[print(total) for total in ans]


### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
a_sum = sum(a)
ac = collections.Counter(a)
q = int(input())
ans = []
for i in range(q):
    b, c = map(int, input().split())
    b_num = ac[b]
    before = b * b_num
    after = c * (b_num)
    a_sum = a_sum - before + after
    ans.append(a_sum)

    tmp = ac[b]
    del ac[b]
    ac[c]+= tmp

[print(total) for total in ans]
### BUGGY CODE ###

def gcd(a, b):
  if(b % a == 0):
    return a
  else:
    ans = 1
    i = 2
    while a!= 1:
      if(a % i == 0):
        while a % i == 0:
          a/= i
        while b % i == 0:
          b/= i
          ans*= i
        i+= 1
    return ans
          

def ggcd(lista):
  if(len(lista) == 1):
    return lista[0]
  else:
    l = lista[0]
    for i in range(1, len(lista)):
      l = gcd(l, lista[i])
    return l

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
d = []
gcds = []
x.sort()

for i in range(N):
  d.append(x[i+ 1]- x[i])
  
gcds.append(d[0])

for i in range(N- 1):
  if(d[i+ 1] != d[i]):
    gcds.append(gcd(d[i+ 1], d[i]))

print(ggcd(gcds))

### FIXED CODE ###

def gcd(a, b):
  if(a == b):
    return a
  elif(a % b == 0):
    return b
  elif(b % a == 0):
    return a
  elif(a == 1 or b == 1):
    return 1
  elif(a > b):
    return gcd(a- a// b* b, b)
  elif(a < b):
    return gcd(a, b- b// a* a)

def ggcd(lista):
  if(len(lista) == 1):
    return lista.pop()
  else:
    l = lista.pop()
    for i in range(1, len(lista)):
      l = gcd(l, lista.pop())
    return l

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
d = []
gcds = set()
x.sort()

for i in range(N):
  d.append(x[i+ 1]- x[i])

gcds.add(d[0])

for i in range(N- 1):
  if(d[i+ 1] != d[i]):
    gcds.add(d[i+ 1])

print(ggcd(gcds))
### BUGGY CODE ###

from heapq import heappush, heappop
K = int(input())
INF = float("inf")
d = [INF] * K
G = [[] for i in range(K)]
for i in range(K):
    G[i].append(((i + 1) % K, 1))
    G[i].append(((10 * i) % K, 0))

d[1] = 0
que = [(1, 0)]
while que:
    v, cost = heappop(que)
    if d[v] < cost:
        continue

    for w, c in G[v]:
        if d[w] > d[v] + c:
            d[w] = d[v] + c
            heappush(que, (w, d[w]))

print(d[0] + 1)


### FIXED CODE ###

from heapq import heappush, heappop
K = int(input())
INF = float("inf")
d = [INF] * K
G = [[] for i in range(K)]
for i in range(K):
    G[i].append(((i + 1) % K, 1))
    G[i].append(((10 * i) % K, 0))

d[1] = 0
que = [(1, 0)]
while que:
    v, cost = heappop(que)
    if d[v] < cost:
        continue

    for w, c in G[v]:
        if d[w] > d[v] + c:
            d[w] = d[v] + c
            heappush(que, (w, d[w]))

print(d[0] + 1)
### BUGGY CODE ###

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

ans = 0
mod = 10**9 + 7

for i in range(N):
    num = 0
    for j in range(i+1, N):
        num += A[j]
    ans += A[i] * num

print(ans % mod)

### FIXED CODE ###

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

ans = 0
mod = 10 ** 9 + 7
num = sum(A)

for a in A:
    num -= a
    ans += a * num

print(ans % mod)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[-1] * W for i in range(H)]

que = deque([])

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            continue
        reached[i][j] = 0
        que.append([i, j])

while que:
    py, px = que.popleft()
    dy = (0, 1, 0, -1)
    dx = (1, 0, -1, 0)
    for y, x in zip(dy, dx):
        ny = py + y
        nx = px + x
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if reached[ny][nx] == -1:        
            que.append([ny, nx])
            reached[ny][nx] = reached[py][px] + 1

MAX = 0
for i in range(H):
    MAX = max(max(reached[i]), MAX)

print(MAX)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[-1] * W for i in range(H)]

que = deque([])

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            continue
        reached[i][j] = 0
        que.append([i, j])

while que:
    py, px = que.popleft()
    dy = (0, 1, 0, -1)
    dx = (1, 0, -1, 0)
    for y, x in zip(dy, dx):
        ny = py + y
        nx = px + x
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if reached[ny][nx] == -1:        
            que.append([ny, nx])
            reached[ny][nx] = reached[py][px] + 1

MAX = 0
for i in range(H):
    MAX = max(max(reached[i]), MAX)

print(MAX)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().strip().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q

for i in range(Q):
    B[i],C[i] = map(int,input().split())

for i in range(Q):
    A = list(map(lambda x: C[i] if x == B[i] else x, A))
    print(sum(A))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().strip().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q
from collections import Counter
K=Counter(A)
ans = 0

for i in range(Q):
    B[i],C[i] = map(int,input().split())


for i in K:
    ans += i * K[i]

for i in range(Q):
    ans -= B[i] * K[B[i]]
    ans += C[i] * K[B[i]]
    K[C[i]] += K[B[i]]
    K[B[i]] = 0
    print(ans)
### BUGGY CODE ###

import itertools
s = input()
K = int(input())
table = []
for i, j in itertools.combinations(range(len(s) + 1), 2):
    if not s[i:j] in table:
        table = sorted(table + [s[i:j]])[0:5]
print(table[K - 1])

### FIXED CODE ###

import itertools
s = input()
K = int(input())
dp = []

def substr(x):
    table = {}
    for i, j in itertools.combinations(range(len(x) + 1), 2):
        table[x[i:j]] = 1
    return sorted(table.keys())[:5]

dp = []

if len(s) < 6:
    dp = substr(s)
else:
    dp = substr(s[-5:])
    for i in range(-6, -len(s) -1, -1):
        for j in range(1, 6):
            if not s[i : i + j] in dp:
                dp = sorted(dp + [s[i : i + j]])[:5]
print(dp[K - 1])
### BUGGY CODE ###

N = int(input())
S = str(input())

ans = 0
for i in range(1000):
    n = "{:03}".format(i)
    index = 0
    c = 0
    for k in n:
        for j in range(index, len(S)):
            if S[j] == k:
                index = j+1
                c+=1
                break
    if c == 3:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = str(input())

ans = 0
for i in range(1000):
    n = "{:03}".format(i)
    index = 0
    c = 0
    for k in n:
        for j in range(index, N):
            if S[j] == k:
                index = j+1
                c+=1
                break
    if c == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def update_distance(d, num, N):
    minn = num
    maxx = num
    # 要素数の小さい方に向けて
    while True:
        if minn > 0:
            minn -= 1
        else:
            break
        if d[minn] > d[minn+1] + 1:
            d[minn] = d[minn+1] + 1
        else:
            break
    # 要素数の大きいほうに向けて
    while True:
        if maxx < (N - 1):
            maxx += 1
        else:
            break
        if d[maxx] > d[maxx-1] + 1:
            d[maxx] = d[maxx-1] + 1
        else:
            break

(N, X, Y) = (int(i) for i in input().split())
X = X-1
Y = Y-1

# まずは経路情報をd[N][N]の二次元配列に格納
# (i, j)がつながっていれば1, つながってなければ2*10^3

d = []
for i in range(N):
    dd = []
    for j in range(N):
        dd.append(abs(i - j))
    d.append(dd)

# XとYがつながることで最短経路を修正していく
for i in range(N):
    dd = d[i]
    dd[X] = min(dd[X], dd[Y] + 1)
    dd[Y] = min(dd[Y], dd[X] + 1)
    update_distance(dd, X, N)
    update_distance(dd, Y, N)

# dの全リストを連結してあとは0~N-1までカウントする
d_list = []
for i in range(N - 1):
    d_list += d[i][i+1:]

#print(d_list)

for i in range(1, N):
    count = d_list.count(i)
    print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import Counter

def update_distance(d, num, N):
    minn = num
    maxx = num
    # 要素数の小さい方に向けて
    while True:
        if minn > 0:
            minn -= 1
        else:
            break
        if d[minn] > d[minn+1] + 1:
            d[minn] = d[minn+1] + 1
        else:
            break
    # 要素数の大きいほうに向けて
    while True:
        if maxx < (N - 1):
            maxx += 1
        else:
            break
        if d[maxx] > d[maxx-1] + 1:
            d[maxx] = d[maxx-1] + 1
        else:
            break

(N, X, Y) = (int(i) for i in input().split())
X = X-1
Y = Y-1

# まずは経路情報をd[N][N]の二次元配列に格納
# (i, j)がつながっていれば1, つながってなければ2*10^3

d = []
for i in range(N):
    dd = []
    for j in range(N):
        dd.append(abs(i - j))
    d.append(dd)

# XとYがつながることで最短経路を修正していく
for i in range(N):
    dd = d[i]
    dd[X] = min(dd[X], dd[Y] + 1)
    dd[Y] = min(dd[Y], dd[X] + 1)
    update_distance(dd, X, N)
    update_distance(dd, Y, N)

# dの全リストを連結してあとは0~N-1までカウントする
d_list = []
for i in range(N - 1):
    d_list += d[i][i+1:]

#print(d_list)
c = Counter(d_list)

for i in range(1, N):
    if i in c:
        print(c[i])
    else:
        print(0)
### BUGGY CODE ###

s=input()[::-1]
n=len(s)
p=2019
S=[0 for i in range(n+1)]
ans=[0]*p

x10=1
for j, i in enumerate(s):
  S[j+1]=(S[j]+(x10*int(i)))%p
  x10*=10
  ans[S[j+1]]+=1

cnt=ans[0]
for a in ans:
  cnt+=(a*(a-1))//2
  
print(cnt)


### FIXED CODE ###

s=input()[::-1]
p=2019
ans=[0]*p

x10, S=1, 0
for i in s:
  S+=x10*int(i)
  S%=p
  x10*=10
  x10%=p
  ans[S]+=1

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

n,m=map(int,input().split())
lrd=[list(map(int,input().split())) for _ in range(m)]
g=[[] for _ in range(n)]
for l,r,d in lrd:
  g[l-1].append([d,r-1])
  g[r-1].append([-d,l-1])

from collections import deque
no_seen=set(range(n))
inf=float('inf')
dst=[inf]*n
while no_seen:
  todo=deque([[0,no_seen.pop()]])
  #print(todo)
  while todo:
    d,t=todo.popleft()
    no_seen.discard(t)
    dst[t]=d
    l=g[t]
    for di,ti in l:
      if dst[ti]!=inf and dst[ti]!=d+di:
        print('No')
        exit()
      elif dst[ti]!=inf and dst[ti]==d+di:
        pass
      else:
        todo.append([d+di,ti])

print('Yes')

### FIXED CODE ###

n,m=map(int,input().split())
lrd=[list(map(int,input().split())) for _ in range(m)]
g=[[] for _ in range(n)]
for l,r,d in lrd:
  g[l-1].append([d,r-1])
  g[r-1].append([-d,l-1])

no_seen=set(range(n))
inf=float('inf')
dst=[inf]*n
while no_seen:
  todo=[[0,no_seen.pop()]]
  #print(todo)
  while todo:
    d,t=todo.pop()
    no_seen.discard(t)
    l=g[t]
    for di,ti in l:
      if dst[ti]!=inf and dst[ti]!=d+di:
        print('No')
        exit()
      elif dst[ti]!=inf and dst[ti]==d+di:
        pass
      else:
        todo.append([d+di,ti])
        dst[ti]=d+di

print('Yes')
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
def modpow(a,n,mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

def modinv(a,mod):
    return modpow(a,mod - 2,mod)


one = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] > A[j]:
            one+=1
two = 0
AA = A+A
for i in range(N*2):
    for j in range(i+1,N*2):
        if AA[i] > AA[j]:
            two+=1
two -= one*2
MOD = 10**9+7

print((one*K%MOD + two*(((K-1)*(K)//2)))%MOD)




### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
def modpow(a,n,mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

def modinv(a,mod):
    return modpow(a,mod - 2,mod)


one = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] > A[j]:
            one+=1
two = 0
AA = A+A
for i in range(N*2):
    for j in range(i+1,N*2):
        if AA[i] > AA[j]:
            two+=1
two -= one*2
MOD = 10**9+7

print((one*K%MOD + two*(((K-1)*(K)//2)))%MOD)
### BUGGY CODE ###

import bisect

N = int(input())
L = [int(input()) for _ in range(N)]
Q = [L[0]]

for l in L[1:]:
    #print("Q=>", Q)
    Q = sorted(Q)
    r = bisect.bisect_left(Q, l)
    if r == 0:
        Q.append(l)
        Q = sorted(Q)
    else:
        Q[r-1] = l
print(len(Q))


### FIXED CODE ###

from collections import deque
import bisect

N = int(input())
L = [int(input()) for _ in range(N)]
Q = deque()
Q.append(L[0])

for l in L[1:]:
    r = bisect.bisect_left(Q, l)
    if r == 0:
        Q.appendleft(l)
    else:
        Q[r-1] = l
print(len(Q))
### BUGGY CODE ###

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

ans = [0] * N

X -= 1
Y -= 1
for i in range(N):
    for j in range(i+1, N):
        distance = abs(i-j)
        # X Y i j
        if Y <= i:
            pass
        # i j X Y
        elif j <= X:
            pass
        # X i Y j
        elif X <= i < Y <= j:
            dis = (i-X) + 1 + (j-Y)
            distance = min(distance, dis)
        # i X j Y
        elif i <= X < j <= Y:
            dis = (X-i) + 1 + (Y-j)
            distance = min(distance, dis)
        # i X Y j
        elif i <= X < Y <= j:
            dis = (X-i) + 1 + (j-Y)
            distance = min(distance, dis)
        # X i j Y
        elif X <= i < j <= Y:
            dis = (i-X) + 1 + (Y-j)
            distance = min(distance, dis)

        ans[distance] += 1

for k in range(1, N):
    print(ans[k])


### FIXED CODE ###

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

ans = [0] * N

X -= 1
Y -= 1
for i in range(N):
    for j in range(i+1, N):
        distance = min(abs(i-j), abs(i-X) + 1 + abs(j-Y))
        ans[distance] += 1

for k in range(1, N):
    print(ans[k])
### BUGGY CODE ###

from math import ceil
from bisect import bisect_right

def update(x, v):
  while x <= N:
    fw[x] += v
    x += x & -x

def s(x):
  res = 0
  while x:
    res += fw[x]
    x -= x & -x
  return res


N,D,A = map(int,input().split())
monsters = sorted([list(map(int,input().split())) for _ in range(N)])

fw = [0 for _ in range(N + 1)]

nxt = []
j = 0
for i in range(N):
  while j < N and monsters[j][0] <= monsters[i][0] + 2 * D:
    j += 1
  nxt.append(j)

ans = 0
for i in range(N):
  h = s(i + 1) - s(0)
  if monsters[i][1] + h > 0:
    num_bomb = ceil((monsters[i][1] + h) / A)
    ans += num_bomb

    k = nxt[i]
    update(i + 1, -(num_bomb * A))
    update(k + 1, num_bomb * A)
    
print(ans)


### FIXED CODE ###

from math import ceil
from collections import deque

N,D,A = map(int,input().split())
monsters = sorted([list(map(int,input().split())) for _ in range(N)])

q = deque([])
s = 0

ans = 0
for i in range(N):
  while len(q) > 0 and q[0][0] < monsters[i][0]:
    s -= q[0][1]
    q.popleft()

  h = monsters[i][1] - s * A
  if h > 0:
    num_bombs = ceil(h / A)

    q.append((monsters[i][0] + 2 * D, num_bombs))
    s += num_bombs
    ans += num_bombs
    
print(ans)
### BUGGY CODE ###

s=str(input())
n=len(s)
ans=0
if 'ABC' not in s:
    print(0)
elif 'ABC' in s:
        p=s.count('ABC')
        while n>0:
            s=s.replace('ABC','BCA')
            q=s.count('ABC')
            n=n-1 
            ans=ans+q
            
        print(p+ans)


### FIXED CODE ###

def test(s):

	res = 0
	aAdd = 0
	last = ''
	tmp = ''
	for i in xrange(len(s)):
		if tmp and tmp > i:
			continue
		if s[i] == 'A':
			aAdd += 1
		elif s[i:i+2] == 'BC':
			# print aAdd
			res = res + aAdd
			tmp = i + 2
		else:
			aAdd = 0
			last = s[i]


	return res
s=raw_input()
print test(s)
### BUGGY CODE ###

import heapq
h,w = map(int,input().split())
si,sj = map(int,input().split())
gi,gj = map(int,input().split())
si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
grid = []
for _ in range(h):
    grid.append(input())
dist = {(i,j):float("inf") for i in range(h) for j in range(w)}
dist[si,sj] = 0
heap = [(0,si,sj)]
while heap:
    mindist,i,j = heapq.heappop(heap)
    if (i,j) == (gi,gj):
        print(mindist)
        break
    if mindist > dist[i,j]: continue
    for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
        if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
            if dist[ni,nj] > dist[i,j]:
                dist[ni,nj] = dist[i,j]
                heapq.heappush(heap,(dist[ni,nj],ni,nj))
    for ni in range(i-2,i+3):
        if not (0 <= ni and ni < h): continue
        for nj in range(j-2,j+3):
            if not (0 <= nj and nj < w): continue
            if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                if dist[ni,nj] > dist[i,j] + 1:
                    dist[ni,nj] = dist[i,j] + 1
                    heapq.heappush(heap,(dist[ni,nj],ni,nj))
 
else:
    print(-1)

### FIXED CODE ###

from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())