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

S = input()
T = input()

dic = {chr(s): [] for s in range(ord("a"), ord("z") + 1)}
for i, s in enumerate(S):
    dic[s].append(i + 1)

out = 0
cnt = -1
V = [0] * len(T)
for i, t in enumerate(T):
    if dic[t]:
        for l in dic[t]:
            if cnt < l:
                V[i] = l
                cnt = l
                break
        else:
            cnt = dic[t][0]
            V[i] = cnt
    else:
        out = 1
        break
if out == 1:
    print(-1)
else:
    cnt = 0
    for i in range(len(V)-1):
        if V[i+1] <= V[i]:
            cnt += 1
    if cnt == 0:
        print(V[-1])
    elif V[-1] == len(S):
        print(len(S) * (cnt + 1))
    else:
        print(len(S) * cnt + V[-1])
a = 0

### FIXED CODE ###

import bisect
S = input()
T = input()

dic = {chr(s): [] for s in range(ord("a"), ord("z") + 1)}
for i, s in enumerate(S):
    dic[s].append(i + 1)

out = 0
cnt = -1
V = [0] * len(T)
for i, t in enumerate(T):
    if dic[t]:
        """
        for l in dic[t]:
            if cnt < l:
                V[i] = l
                cnt = l
                break
        else:
            cnt = dic[t][0]
        """

        idx = bisect.bisect(dic[t], cnt)
        if idx == len(dic[t]):
            V[i] = dic[t][0]
            cnt = dic[t][0]
        else:
            V[i] = dic[t][idx]
            cnt = dic[t][idx]

    else:
        out = 1
        break
if out == 1:
    print(-1)
else:
    cnt = 0
    for i in range(len(V)-1):
        if V[i+1] <= V[i]:
            cnt += 1
    if cnt == 0:
        print(V[-1])
    elif V[-1] == len(S):
        print(len(S) * (cnt + 1))
    else:
        print(len(S) * cnt + V[-1])
a = 0
### BUGGY CODE ###

num = list(map(int, input().split()))

loop = [0]

for i in loop:
  if num[0] < num[1]:
    difference = abs(num[0] - num[1])
    if difference > num[0]:
      break
    else:
      num[0] = difference
      break
  elif num[1] == 1:
    num[0] = 0
    break
  elif num[1] == 0:
    break
  num[0] = num[0] % num[1]
  num[0] = abs(num[0] - num[1])
  loop.append(i+1)

print(num[0])

### FIXED CODE ###

num = list(map(int, input().split()))

loop = [0]

for i in loop:
  if num[0] < num[1]:
    difference = abs(num[0] - num[1])
    if difference > num[0]:
      break
    else:
      num[0] = difference
      break
  elif num[1] == 1:
    num[0] = 0
    break
  elif num[1] == 0:
    break
  if i == 0:
    num[0] = num[0] % num[1]
  num[0] = abs(num[0] - num[1])
  loop.append(i+1)

print(num[0])
### BUGGY CODE ###

def resolve_D():
    max_ = 0
    res = 0
    n, k = map(int, input().split())
    l = list(map(int, input().split()))
    for i in range(0, n-k+1):
        total = sum(l[i:i+k])
        if total > max_:
            max_ = total
            max_i = i
    for j in l[max_i:max_i+k]:
        res += j * (j + 1) / 2 / j
    print(res)
resolve_D()

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
q = list(map(int,input().split()))
q = np.array(q)
 
p = (q + 1) /2
p = p.tolist()
a = sum(p[:K])
mx = a
 
for i in range(0,N-K):
    a = a - p[i] + p[i+K]
    if a > mx:
        mx = a
print(mx)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
c=[0]*n
c[1]=abs(h[0]-h[1])
for i in range(2,n):
    for j in range(max(0,i-k),i):
        if c[i]==0:
            c[i]=c[j]+abs(h[i]-h[j])
        else:
            c[i]=min(c[i],c[j]+abs(h[i]-h[j]))
print(c[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
c=[0]*n
for i in range(1,n):
    c[i]=min([cj+abs(h[i]-hj) for cj,hj in zip(c[max(0,i-k):i],h[max(0,i-k):i])])
print(c[-1])
### BUGGY CODE ###

import bisect

n = int(input())
l = list(int(x) for x in input().split())
l.sort()
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += i-bisect.bisect_left(l[:i], l[j]-l[i]+1)
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(int(x) for x in input().split())
l.sort()
ans = 0
for i in range(n):
    for j in range(i+1, n):
        key = bisect.bisect_left(l, l[j]-l[i]+1)
        ans += max([0, i-key])
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    S = input()
    r_inds = []
    g_inds = []
    b_inds = []
    for i in range(len(S)):
        if S[i] == "R":
            r_inds.append(i)
        elif S[i] == "G":
            g_inds.append(i)
        else:
            b_inds.append(i)

    total_comb = len(r_inds)*len(g_inds)*len(b_inds)
    ded = 0
    for i in r_inds:
        for j in g_inds:
            s_ind = min(i, j)
            b_ind = max(i, j)
            diff = b_ind - s_ind
            bigger_ind = b_ind + diff
            smaller_ind = s_ind - diff
            if bigger_ind < len(S) and bigger_ind in b_inds:
                ded += 1
            if smaller_ind >= 0 and smaller_ind in b_inds:
                ded += 1
            if diff % 2 == 0:
                mid_diff = diff // 2
                mid_ind = s_ind + mid_diff
                if mid_ind in b_inds:
                    ded += 1
    print(total_comb - ded)

            
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    S = input()
    r_inds = []
    g_inds = []
    b_inds = []
    for i in range(len(S)):
        if S[i] == "R":
            r_inds.append(i)
        elif S[i] == "G":
            g_inds.append(i)
        else:
            b_inds.append(i)

    total_comb = len(r_inds)*len(g_inds)*len(b_inds)
    ded = 0
    for i in r_inds:
        for j in g_inds:
            s_ind = min(i, j)
            b_ind = max(i, j)
            diff = b_ind - s_ind
            bigger_ind = b_ind + diff
            smaller_ind = s_ind - diff
            if bigger_ind < len(S) and bigger_ind in b_inds:
                ded += 1
            if smaller_ind >= 0 and smaller_ind in b_inds:
                ded += 1
            if diff % 2 == 0:
                mid_diff = diff // 2
                mid_ind = s_ind + mid_diff
                if mid_ind in b_inds:
                    ded += 1
    print(total_comb - ded)

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

#!/usr/bin/env python3
#ABC137 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,num_v, start):
    #start → iの最短距離
    #start:始点, num_v:頂点数, edges:[辺の始点, 辺の終点, 辺のコスト]
    dist = [-float('inf') for _ in range(num_v)]
    #dist[i] := s→iの最短距離
    dist[start] = 0
    flg = 0
    for _ in range(10):
        update = False
        for i in range(num_v):
            for edge in edges:
                e_from, e_to, e_cost = edge
                if e_from != -float('inf') and dist[e_to] < dist[e_from] + e_cost:
                    dist[e_to] = dist[e_from] + e_cost
                    update = True
        if not update:
            flg = 1
            break
    return dist, flg

n,m,p = LI()
edge = []
for _ in range(m):
    a,b,c = LI()
    edge.append([a-1,b-1,c-p])
d,f = Bellman_Ford(edge,n,0)
if d[-1] < 0:
    print(0)
elif not f:
    print(-1)
else:
    print(d[-1])


### FIXED CODE ###

#!/usr/bin/env python3
#ABC137 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Bellman_Ford(edges,num_v, start):
    #start → iの最短距離
    #start:始点, num_v:頂点数, edges:[辺の始点, 辺の終点, 辺のコスト]
    dist = [-float('inf') for _ in range(num_v)]
    #dist[i] := s→iの最短距離
    dist[start] = 0
    flg = 0
    for i in range(num_v):
        update = False
        for edge in edges:
            e_from, e_to, e_cost = edge
            if e_from != -float('inf') and visited[e_to] and dist[e_to] < dist[e_from] + e_cost:
                dist[e_to] = dist[e_from] + e_cost
                update = True
        if not update:
            flg = 1
            break
    return dist, flg

n,m,p = LI()
edge = []
f = defaultdict(dict)
for _ in range(m):
    a,b,c = LI()
    edge.append([a-1,b-1,c-p])
    f[b-1][a-1] = 1
visited = [False]*n
def dfs(x):
    visited[x] = True
    for t in f[x].keys():
        if not visited[t]:
            dfs(t)
dfs(n-1)
d,f = Bellman_Ford(edge,n,0)
if not f:
    print(-1)
else:
    print(max(0,d[-1]))
### BUGGY CODE ###

H,W,M=map(int, input().split())
#nrow=[0]*H
#ncol=[0]*W
xcoord=[]
ycoord=[]

import collections

for _ in range(M):
	h,w=map(int, input().split())
#	nrow[h-1]+=1
#	ncol[w-1]+=1
	xcoord+=[w-1]
	ycoord+=[h-1]

ncol=collections.Counter(xcoord)
nrow=collections.Counter(ycoord)


#print(nrow) #dict of y-coord
#print(ncol) #dict of x-coord

row_cand=[]
col_cand=[]

a=max(nrow.values())
for i in nrow.keys():
	if nrow[i]==a:
		row_cand+=[i]


#print(row_cand)

b=max(ncol.values())
for i in ncol.keys():
	if ncol[i]==b:
		col_cand+=[i]

#print(col_cand)



#print(xcoord,ycoord)


count_intersection=0
for i in range(len(xcoord)):
	if (xcoord[i] in col_cand) and (ycoord[i] in row_cand):
		count_intersection+=1

if count_intersection==len(col_cand)*len(row_cand):
	print(a+b-1)
else:
	print(a+b)



# 2darray [[0] * 4 for i in range(3)]
# import itertools

### FIXED CODE ###

H,W,M=map(int, input().split())
nrow=[0]*H
ncol=[0]*W
xycoord=[]

for _ in range(M):
	h,w=map(int, input().split())
	nrow[h-1]+=1
	ncol[w-1]+=1
	xycoord+=[[w-1,h-1]]

#ncol=collections.Counter(xcoord)
#nrow=collections.Counter(ycoord)

a=max(nrow)
b=max(ncol)
row_cand=set([i for i, x in enumerate(nrow) if x == a])
col_cand=set([i for i, x in enumerate(ncol) if x == b])


flag=0
for i in xycoord:
	if (i[0] in col_cand) and (i[1] in row_cand):
		flag+=1

if flag<(len(col_cand)*len(row_cand)):
	print(max(nrow)+max(ncol))
else:
	print(max(nrow)+max(ncol)-1)



# 2darray [[0] * 4 for i in range(3)]
# import itertools
### BUGGY CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    ans%=mod
print(ans%mod)


### FIXED CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)
### BUGGY CODE ###

import math

[n,m] = [int(x) for x in input().split(" ")]
an = [int(x) for x in input().split(" ")]
an.sort(reverse=True)

for i in range(m):
    max_value = an[0]
    an[0] = max_value / 2
    an.sort(reverse=True)

discounted_an = [math.floor(x) for x in an]
print(sum(discounted_an))

### FIXED CODE ###

import math

[n,m] = [int(x) for x in input().split(" ")]
an = [int(x) for x in input().split(" ")]
an.sort(reverse=True)

log2_an = [math.ceil(math.log2(x) + 1) for x in an]
max_log2 = log2_an[0]
rest_ticket = m

for i in range(max_log2):
    cnt = log2_an.count(log2_an[0])
    if(cnt <= rest_ticket):
        for j in range(cnt):
            an[j] = an[j] / 2
            log2_an[j] -= 1
    else:
        for j in range(rest_ticket):
            an[j] = an[j] / 2
        break
    rest_ticket -= cnt
    an.sort(reverse=True)

discounted_an = [math.floor(x) for x in an]
print(sum(discounted_an))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(1,N+1):
    ans=A.count(i)
    print(ans)

### FIXED CODE ###

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

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
q = [list(map(int, input().split())) for i in range(m)]

g = [[] for i in range(n+1)]

for i in range(m):
    a, b, c = q[i]
    g[a].append((b, c))
    g[b].append((a, -c))

people = [-10**10] * (n+1)

flag = 1
for i in range(1, n+1):
    if people[i] != -10**10:
        continue
    q = [i]
    while q:
        now = q.pop()
        for next, dist in g[now]:
            if people[next] == -10**10:
                q.append(next)
                people[next] = people[now] + dist
            else:
                if people[next] == people[now] + dist:
                    continue
                else:
                    flag = 0
                    break
        if flag == 0:
            break

if max(people[1:]) - min(people[1:]) > 10**9:
    flag = 0
    
if flag == 1:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
q = [list(map(int, input().split())) for i in range(m)]

g = [[] for i in range(n+1)]

for i in range(m):
    a, b, c = q[i]
    g[a].append((b, c))
    g[b].append((a, -c))

people = [-10**10] * (n+1)

flag = 1
for i in range(1, n+1):
    if people[i] != -10**10:
        continue
    q = [i]
    people[i] = 0
    while q:
        now = q.pop()
        for next, dist in g[now]:
            if people[next] == -10**10:
                q.append(next)
                people[next] = people[now] + dist
            else:
                if people[next] == people[now] + dist:
                    continue
                else:
                    flag = 0
                    break
        if flag == 0:
            break

if max(people[1:]) - min(people[1:]) > 10**9:
    flag = 0

if flag == 1:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import numpy as np

n, K = map(int, input().split())
h = np.array(list(map(int,input().split())))

cost_dp = np.array([float('inf')]*n)
cost_dp[0] = 0

for i in range(1,n):
    k = min(i,K)
    cost_dp[i] = np.min(cost_dp[i-k:i]+np.absolute(h[i-k:i]-h[i]))

print(int(cost_dp[-1]))

### FIXED CODE ###

import numpy as np

n, K = map(int, input().split())
h = np.array(list(map(int,input().split())))

cost_dp = np.array([100000000]*n)
cost_dp[0] = 0

for i in range(1,n):
    k = min(i,K)
    cost_dp[i] = np.min(cost_dp[i-k:i]+np.absolute(h[i-k:i]-h[i]))

print(int(cost_dp[-1]))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
b = set(a)
ans = 0
for k in b:
	ans = max(ans, a.count(k) + a.count(k + 1) + a.count(k - 1))
print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

N = int(input())
a = sorted(list(map(int, input().split())))

ans = 1
for i in range(N):
    X = a[i]
    res = bisect_right(a, X+1) - bisect_left(a, X-1)
    ans = max(res, ans)

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

import numpy as np

def calculate(h, w, arr):
    L = np.zeros([h, w])
    U = np.zeros([h, w])
    D = np.zeros([h, w])
    R = np.zeros([h, w])

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == "#":
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1

            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == "#":
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            if arr[ih][iw] == "#":
                continue
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = list(input())
    arr.append(q)

calculate(H, W, arr)


### FIXED CODE ###

def calculate(h, w, arr):
    L = [[0]*w for i in range(h)]
    U = [[0]*w for i in range(h)]
    D = [[0]*w for i in range(h)]
    R = [[0]*w for i in range(h)]

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == 1:
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1

            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == 1:
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = input()
    tmp = []
    for qs in q:
        if qs == "#":
            tmp.append(1)
        if qs == ".":
            tmp.append(0)
    arr.append(tmp)

calculate(H, W, arr)
### BUGGY CODE ###

N, K = map(int, input().split())
a = [int(input())-1 for _ in [0]*N]
end = set()
end2 = set()
add = end.add
add2 = end2.add
result = 0
for i in range(N-1, -1, -1):
    if a[i] == -1:
        result += 1
    elif i in end:
        continue
    else:
        v = i
        l = 0
        n = 0
        while a[v] != -1:
            if v not in end2 and l < K:
                n += 1
                add2(v)
            l += 1
            add(v)
            v = a[v]
        result += n


print(result)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
N, K = map(int, readline().split())
a = [int(readline())-1 for _ in [0]*N]
result = a.count(-1)

nodes = set()
node_add = nodes.add
hoge = set()
hoge_add = hoge.add
for i in range(N):
    if a[i] in hoge:
        node_add(a[i])
    hoge_add(a[i])

visited = set()
add = visited.add
startnode = {v: K-1 for v in {i for i in range(N) if a[i] > -1} - set(a)}
while startnode:
    nextnode = dict()
    for v, l in startnode.items():
        #print("start:", v, "length:", l)
        result += (v not in visited)
        add(v)
        v = a[v]
        while a[v] > -1 and v not in nodes and l > 0:
            #print(v)
            if v not in visited:
                result += 1
                add(v)
            l -= 1
            v = a[v]
        if a[v] > -1 and v in nodes and l > 0:
            #print("->", v)
            nextnode[v] = max(nextnode.get(v, 0), l-1)
    startnode = nextnode

print(result)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())

to_battle_with = [deque([i - 1 for i in map(int, input().split())]) for _ in range(n)]

day_count = 0
remained_battles = (n * (n - 1)) // 2

while remained_battles:
    battled_today = set()

    no_battle_today = True
    for player in range(n):
        if not to_battle_with[player]:
            continue

        next_opponent = to_battle_with[player][0]
        if player in battled_today or next_opponent in battled_today:
            continue

        if not to_battle_with[next_opponent]:
            continue

        if to_battle_with[next_opponent][0] == player:
            battled_today.add(next_opponent)
            battled_today.add(player)
            to_battle_with[player].popleft()
            to_battle_with[next_opponent].popleft()
            remained_battles -= 1
            no_battle_today = False
    if no_battle_today:
        print(-1)
        break
    day_count += 1

if not no_battle_today:
    print(day_count)


### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

to_battle_with = [deque([i - 1 for i in map(int, input().split())]) for _ in range(n)]


def update_battle(player, battle_set, to_battle_with):
    if not to_battle_with[player]:
        return
    next_opponent = to_battle_with[player][0]
    if not to_battle_with[next_opponent]:
        return
    if to_battle_with[next_opponent][0] == player:
        if player > next_opponent:
            player, next_opponent = next_opponent, player
        battle_set.add((player, next_opponent))


battles_today = set()
for player in range(n):
    update_battle(player, battles_today, to_battle_with)

day_count = 0
battle_count = 0
num_all_battles = (n * (n - 1)) // 2

while battles_today:
    battles_tomorrow = set()
    for p1, p2 in battles_today:
        battle_count += 1
        to_battle_with[p1].popleft()
        to_battle_with[p2].popleft()
        for p in [p1, p2]:
            update_battle(p, battles_tomorrow, to_battle_with)
    battles_today = battles_tomorrow
    day_count += 1

if battle_count == num_all_battles:
    print(day_count)
else:
    print(-1)
### BUGGY CODE ###

import math


def main():
        
    N,D,A = map(int, input().split())

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

    xh.sort()

    ans = 0
    for i in range(N):
        if xh[i][1] <= 0:
            continue


        
        cnt = math.ceil(xh[i][1] / A)
        ans += cnt
        xh[i][1] = 0

        if cnt == 0:
            continue

        d = cnt*A
        for j in range(i+1, N):

            if xh[j][0] > xh[i][0] + 2*D:
                break
            xh[j][1] -= d


    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import math
from collections import deque

def main():
        
    N,D,A = map(int, input().split())

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

    xh.sort()

    ans = 0
    q = deque()
    dmg = 0
    for i in range(N):
        # 過去に使った爆弾で、現在地点まで攻撃が届かないものは効果切れにする
        while q and q[0][0] < xh[i][0]:
            _, d = q.popleft()
            dmg -= d

        # それまでの攻撃でその地点の敵が死んでいるので、その敵に対しては新たに爆弾を使わない
        if xh[i][1] - dmg <= 0:
            continue

        remaining = xh[i][1] - dmg

        cnt = math.ceil(remaining / A)
        ans += cnt
        dmg += cnt * A
        # その敵に対して爆弾を使ったので、追加
        q.append((xh[i][0] + 2*D, cnt*A))


    print(ans)

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

import re
S = input()
pattern = r"(A+(BC)*A*(BC)+)+"
pattern2 = r"(A|BC)"
match_iter = re.finditer(pattern, S)
# print([i.group() for i in match_iter])
count = 0
for match in match_iter: ## AABCBCAABCBC
    string = match.group()
    match2 = re.findall(pattern2, string)
    cntA = 0
    for string2 in match2:
        if string2 == "A":
            cntA += 1
        else:
            count += cntA
print(count)

### FIXED CODE ###

S = input()
S = S.replace("BC","X")
count = 0
cntA = 0
for c in S:
    if c == "A":
        cntA += 1
    elif c == "X":
        count += cntA
    else:
        cntA = 0
print(count)