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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

s = input()
s = deque(s)
q = INT()


L = [S_LIST() for i in range(q)]
for i in range(q):
    if L[i][0] == "1":
        s.reverse()
    else:
        query, sent = int(L[i][1]), str(L[i][2])
        if query == 1:
            s.appendleft(sent)
        else:
            s.append(sent)
print("".join(list(s)))

    




### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

s = input()
s = deque(s)
q = INT()

r_count = 0
L = [S_LIST() for i in range(q)]
for i in range(q):
    if L[i][0] == "1":
        r_count ^= 1
        # s.reverse()
    else:
        query, sent = int(L[i][1]), str(L[i][2])
        if r_count == 0:
            if query == 1:
                s.appendleft(sent)
            else:
                s.append(sent)
        else:
            if query == 2:
                s.appendleft(sent)
            else:
                s.append(sent)

if r_count != 0:
    s.reverse()
print("".join(list(s)))
### BUGGY CODE ###

N = int(input())
S = []

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

S_KEYS = set(S)


n= 1

for key in S_KEYS:
    m = S.count(key)
    if n < m:
        n = m
        
ANS = []
for key in S_KEYS:
    if S.count(key) == n:
        ANS +=[key]

ANS= sorted(ANS)
 
for key in ANS:
        print(key)

### FIXED CODE ###

N = int(input())
S = []

dic_={}
n = 1

for i in range(N):
    a = input()
    if a in dic_.keys():
        b = dic_.get(a) + 1
        dic_.update({a: b})
        if n < b:
            n = b
    else:
        dic_.update({a: 1})

ANS = []

for i in dic_:
    if dic_.get(i) == n:
        ANS += [i]

ANS = sorted(ANS)

for key in ANS:
        print(key)
### BUGGY CODE ###

class Node:

    def __init__(self, i):
        self.index = i
        self.parent = self

    def root(self):
        if self.parent == self:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

    def unite(self, other):
        self.root().parent = other.root()

    def is_unite(self, other):
        return self.root() == other.root()


def solve(N, K, L, PQs, RSs):
    road_cities = [Node(i) for i in range(N + 1)]
    train_cities = [Node(i) for i in range(N + 1)]

    for p, q in PQs:
        road_cities[p].unite(road_cities[q])

    # print("road")
    # for c in road_cities[1:]:
    #     print(c.index, "-> ", c.root().index)

    for r, s in RSs:
        train_cities[r].unite(train_cities[s])

    # print("train")
    # for c in train_cities[1:]:
    #     print(c.index, "-> ", c.root().index)

    counts = []

    for n1 in range(1, N + 1):
        count = 0
        for n2 in range(1, N + 1):
            if n1 == n2:
                count += 1
            elif road_cities[n1].is_unite(road_cities[n2]) and \
                    train_cities[n1].is_unite(train_cities[n2]):
                count += 1
        counts.append(str(count))
    return " ".join(counts)


if __name__ == "__main__":
    N, K, L = map(int, input().split(" "))
    PQs = []
    RSs = []
    for _ in range(K):
        PQs.append(tuple(map(int, input().split(" "))))
    for _ in range(L):
        RSs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, L, PQs, RSs))


### FIXED CODE ###

from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]

    def root(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.root(self.parents[i])
            return self.parents[i]

    def unite(self, i, j):
        self.parents[self.root(self.parents[i])] = self.root(j)

    def is_unite(self, i, j):
        return self.root(i) == self.root(j)


def solve(N, K, L, PQs, RSs):
    road_cities = UnionFind(N)
    train_cities = UnionFind(N)

    for p, q in PQs:
        road_cities.unite(p, q)
    for r, s in RSs:
        train_cities.unite(r, s)

    counts = Counter([
        (road_cities.root(i), train_cities.root(i))
        for i in range(1, N + 1)
    ])

    ans = [
        counts[(road_cities.root(i), train_cities.root(i))]
        for i in range(1, N + 1)
    ]

    return " ".join([str(c) for c in ans])


if __name__ == "__main__":
    N, K, L = map(int, input().split(" "))
    PQs = []
    RSs = []
    for _ in range(K):
        PQs.append(tuple(map(int, input().split(" "))))
    for _ in range(L):
        RSs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, L, PQs, RSs))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from copy import *

H, W = map(int, input().split())
A = [input() for i in range(H)]
q = deque()
c = [[-1] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append((i, j))
            c[i][j] = 0
D = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while q:
    y, x = q.popleft()
    for dy, dx in D:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and c[ny][nx] == -1:
            q.append((ny, nx))
            c[ny][nx] = c[y][x]+1
print(max([max(l) for l in c]))


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from copy import *

H, W = map(int, input().split())
A = [input() for i in range(H)]
q = deque()
c = [[-1] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append((i, j))
            c[i][j] = 0
D = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while q:
    y, x = q.popleft()
    for dy, dx in D:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and c[ny][nx] == -1:
            q.append((ny, nx))
            c[ny][nx] = c[y][x]+1
print(max([max(l) for l in c]))
### BUGGY CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


n = int(input())

ans = 0

for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            cnt = gcd(i, j, k)
            ans += cnt

print(ans)


### FIXED CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


n = int(input())

ans = 0

for i in range(1, n + 1):
    for j in range(i, n + 1):
        for k in range(j, n + 1):
            cnt = gcd(i, j, k)
            if i == j and j == k:
                ans += cnt
            elif (i == j and i != k) or (i == k and i != j) or (j == k and j != i):
                ans += cnt * 3
            else:
                ans += cnt * 6

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

n, k = map(int, input().split())
height = []
for _ in range(n):
    h = int(input())
    height.append(h)

height.sort()

ans = 10**10
for i in range(n-k+1):
    temp = height[i:i+k]
    if temp[-1] - temp[0] < ans:
        ans = temp[-1] - temp[0]

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
height = []
for _ in range(n):
    h = int(input())
    height.append(h)

height.sort()

ans = 10**10
for i in range(n-k+1):
    ans = min(ans, height[i+k-1] - height[i])

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

import math

N = int(input())
A_lis = list(input().split())
r = 10 ** 9 + 7
count = 2 ** (int(math.floor(N/2)))

for i in range(N):
    if N % 2 == i % 2:
        if A_lis.count(str(i)) != 0:
            count = 0
            break
        else:
            continue
    else:
        if i == 0:
            if A_lis.count(str(i)) == 1:
                continue
            else:
                count = 0
                break
        elif A_lis.count(str(i)) != 2:
            count = 0
            break
        else:
            continue
        
print(count)


### FIXED CODE ###

import numpy as np
from collections import Counter
mo = 1000000007
r = range
 
n = int(input())
a = np.array(list(map(int, input().split())))
 
c = Counter(a.tolist())
 
if n % 2 == 1 and (0 not in c or c[0] != 1): print(0); exit();
 
for i in r(n//2):
    x = i * 2 + (1 if n % 2 == 0 else 2)
    if x not in c or c[x] != 2: print(0); exit();
 
print(2 ** (n//2) % mo)
### BUGGY CODE ###

# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数を２つのグループに分ける

import itertools

def main():
  a, b = map(int, input().split())
  c = gojo(a,b)
  
  fac = [1]
  fac = facto(c)
  #print(fac)
  print(max(1, len(fac)))  
  
def facto(n):
  if n == 1:
    return []
  elif n == 2:
    return[1, 2]
  elif n % 2 == 0:
    fac = [1, 2]
  else:
    fac = [1]
  
  max_n = n + 1 # int(n ** 0.5 + 2)
  
  is_prime = [True for x in range(max_n)]
  for cursor in range(3, max_n, 2):
    if is_prime[cursor]:
      if n % cursor == 0:
        fac.append(cursor)
        while n % cursor == 0:
          n //= cursor
        if n == 1:
          break
      for i in range(cursor, max_n, cursor):
        is_prime[i] = False
  
  if len(fac) == 1:
    fac.append(n)
    
  return fac
  
def gojo(a,b):
  if b > a:
    a, b = b, a
  c = a % b
  if c == 0:
    return(b)
  else:
    return gojo(b, c)

if __name__ == "__main__":
  main()


### FIXED CODE ###

# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数＋１が答え

import itertools
from fractions import gcd
from math import ceil

def main():
  a, b = map(int, input().split())
  fac = facto(gcd(a,b))
  print(len(fac))  
  
def facto(n):
  fac = [1]
  if n == 1:
    return [1]
  elif n % 2 == 0:
    fac = [1, 2]
    while n % 2 == 0:
      n = n // 2
  
  max_n = ceil(n ** 0.5) + 1
  
  is_prime = [True for x in range(max_n)]
  for cursor in range(3, max_n, 2):
    if is_prime[cursor]:
      if n % cursor == 0:
        fac.append(cursor)
        while n % cursor == 0:
          n = n // cursor
        if n == 1:
          break
      for i in range(cursor, max_n, cursor):
        is_prime[i] = False
  if n != 1:
    fac.append(n)
  return fac

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

#ABC 072 C
N=int(input())
A=[int(j) for j in input().split()]
cnt=0
for a in A:
    tmp=0
    for i in range(len(A)):
        if -1<= A[i]-a <=1:
            tmp+=1
    cnt=max(tmp,cnt)
print(cnt)

### FIXED CODE ###

#ABC 072 C
N=int(input())
A=[int(j) for j in input().split()]
cnt=[0]*(10**6)
for a in A:
    cnt[a]+=1
    cnt[a+1]+=1
    cnt[a+2]+=1
print(max(cnt))
### BUGGY CODE ###

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

k = 10**9+7

ans = 0
for s in range(len(A)-1):
    ans += A[s]*sum(A[s+1:])

print(ans%k)

### FIXED CODE ###

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

k = 1000000007

sm = sum(A)

ans = 0
for s in range(len(A)-1):
    #ans += A[s]*sum(A[s+1:])
    sm -= A[s]
    ans += A[s]*sm

if ans>1000000007:
    print(ans%k)
else:
    print(ans)
### BUGGY CODE ###

n, W = map(int, input().split())
dp = [0]*(W+1)
for _ in range(n):
    w, v = map(int, input().split())
    tmp_dp = [max(dp[sum_w], dp[sum_w - w] + v) for sum_w in range(w, W+1)]
    dp[w:] = tmp_dp
print(max(dp))

### FIXED CODE ###

n, W = map(int, input().split())
dp = [0]*(W+1)
for _ in range(n):
    w, v = map(int, input().split())
    tmp_dp = [max(dp[sum_w], dp[sum_w - w] + v) for sum_w in range(w, W+1)]
    dp[w:] = tmp_dp
print(max(dp))
### BUGGY CODE ###

import math
num_limit = int(input())
s_limit = int(num_limit**0.5)
for i in range(1,num_limit+1):
    xyz_list = []
    xyz_count = 0
    s_limit_1 = int(i ** 0.5)
    for j in range(1,s_limit+1):
        if i <= j**2:
            break
        for k in range(1,j+1):
            if i <= j**2 + k**2 + j*k:
                break
            for l in range(1,k+1):
                if i < j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    break
                elif i == j**2 + k**2 + l**2 + j*k + k*l + l*j:
                    if j > k:
                        if k > l:
                            xyz_count += 6
                        else:
                            xyz_count += 3
                    elif k == l:
                        xyz_count += 1
                    else:
                        xyz_count += 3
    print(xyz_count)

### FIXED CODE ###

num_limit = int(input())
num_list = [0] * num_limit
j_limit = int(num_limit ** 0.5)
for j in range(1,j_limit+1):
    for k in range(1,j + 1):
        for l in range(1,k+1):
            if num_limit >= j**2 + k**2 + l**2 + j*k + k*l + l*j:
                if j > k:
                    if k > l:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 6
                    else:
                        num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                elif k > l:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 3
                else:
                    num_list[j**2 + k**2 + l**2 + j*k + k*l + l*j-1] += 1
for i in num_list:
    print(i)
### BUGGY CODE ###

import itertools

N,K=map(int, input().split())
l=[int(x) for x in input().split()]

max=-3

for i in list(itertools.combinations(l,K)):
    if sum(i)>=max:
        max=sum(i)

print(max)

### FIXED CODE ###

N,K=map(int, input().split())
l=[int(x) for x in input().split()]

buf=sorted(l,reverse=True)
result=0

for i in range(K):
    result+=buf[i]

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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    X = list(map(int, input().split()))
    for i in range(N):
        tmp = X[:i]
        tmp.extend(X[i + 1:])
        tmp.sort()
        print(tmp[N // 2 - 1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    X = list(map(int, input().split()))
    x = sorted(X)[N // 2 - 1:N // 2 + 1]
    for i in X:
        print(x[i <= x[0]])


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

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

ans = 0
kinds = [set() for _ in range(N + 1)]
history = dict()

for i in range(N - 1, -1, -1):
    kinds[i] = kinds[i + 1].union(S[i])

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if not history.get((S[i], S[j],)):
            ans += len(kinds[j+1])
            history[(S[i], S[j],)] = 1

print(ans)


### FIXED CODE ###

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

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            fi = S.find(str(i))
            if fi < 0:
                continue
            fj = S[fi+1:].find(str(j))
            if fj < 0:
                continue
            fk = S[fi+fj+2:].find(str(k))
            if fk < 0:
                continue
            ans += 1

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

a,b,n = map(int,input().split())
ans = 0
for i in range(1,min(10**7+1,n+1)):
    ans = max(ans,((a * i)//b -a * (i//b)))
print(ans)

### FIXED CODE ###

import random

a,b,n = map(int,input().split())
ans = 0

for i in range(10 ** 6):
    num = random.randint(0,n)
    ans = max(ans,(a * num)//b - a * (num//b))
print(ans)
### BUGGY CODE ###

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    
    like=[False]*(n+1)
    for i in range(1,n+1,2):
        if(is_prime[i]==False):
            continue
        else:
            if(is_prime[int((i+1)/2)]==True):
                like[i]=True
            
    return  like
    #return [i for i in range(n + 1) if is_prime[i]]
q=int(input())
table=primes(10**5+10)
for i in range(q):
    l,r=map(int,input().split())
    accum=[0]
    for i in range(1,r+2):
        if(table[i]==True):
            accum.append(accum[i-1]+1)
        else:
            accum.append(accum[i-1])
    print(accum[r]-accum[l-1])

### FIXED CODE ###

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    
    like=[False]*(n+1)
    for i in range(1,n+1,2):
        if(is_prime[i]==False):
            continue
        else:
            if(is_prime[int((i+1)/2)]==True):
                like[i]=True
            
    return  like
    #return [i for i in range(n + 1) if is_prime[i]]
q=int(input())
table=primes(10**5+10)
accum=[0]
for i in range(1,10**5+5):
        if(table[i]==True):
            accum.append(accum[i-1]+1)
        else:
            accum.append(accum[i-1])
for i in range(q):
    l,r=map(int,input().split())
    print(accum[r]-accum[l-1])
### BUGGY CODE ###

N=int(input())
s=[int(input()) for i in range(N)]
i=0
while i>=0 :
    i+=1
    for j in range(N):
        if (max(s)*i)%s[j]!=0:
            break
    else:
        print(max(s)*i)
        exit()

### FIXED CODE ###

def f(a,b):
    x,y=a,b
    while b>0:
        a,b=b,a%b
    return (x//a)*y
s=1    
N=int(input())
for i in range(N):
    a=s
    b=int(input())
    s=f(a,b)
print(s)
### BUGGY CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

M, = map(int, sys.stdin.readline().rstrip().split(" "))

def too_slow(d_pairs):
    ds = []
    for d, c in d_pairs:
        for _ in range(c):
            ds.append(d)
    d, c = 0, 0
    for next_d in ds:
        c += 1
        d += next_d
        if d >= 10:
            d = d % 10 + 1
            c += 1
    return c-1


def contract_list(ds):
    d, c = 0, -1
    for next_d, next_c in ds:
        c += next_c
        c += 1
        d += next_d
        if d >= 10:
            d = d % 10 + 1
            c += 1
        # print(d, c)
    return d, c

def contract_pair(d, orig_c):
    c = 0
    ds = [(d, c)]
    for _ in range(int(math.log(orig_c, 2)) + 1):
        d = d + d
        c = c*2 +1
        if d >= 10:
            d = d % 10 + 1
            c += 1
        ds.append((d, c))
    # print(ds)

    ds_for_calc = []
    for i, b in enumerate(reversed(bin(orig_c)[2:])):
        # print(bin(orig_c), b)
        if b == "1":
            ds_for_calc.append(ds[i])
    # print("for_cal", ds_for_calc)

    return contract_list(ds_for_calc)


ds_for_calc = []
orig_ds = []
for _ in range(M):
    d, c = map(int, sys.stdin.readline().rstrip().split(" "))
    orig_ds.append((d, c))
    ds_for_calc.append(contract_pair(d, c))
    # print(ds_for_calc[-1])
# print("last_list", ds_for_calc)
answer = contract_list(ds_for_calc)[1]
# print(too_slow(orig_ds), answer)
assert too_slow(orig_ds) == answer
print(answer)

exit(0)


### FIXED CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

M, = map(int, sys.stdin.readline().rstrip().split(" "))
total_sum = 0
total_digits = 0
for _ in range(M):
    d, c = map(int, sys.stdin.readline().rstrip().split(" "))
    total_digits += c
    total_sum += d*c
answer = ((total_sum-1) // 9) + total_digits -1
print(answer)
exit(0)
### BUGGY CODE ###

N = int(input())


def p_f(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


hoge = p_f(N)

DP = [1]

if len(hoge) == 1:
    print(hoge[0]-1)
else:
    Min = 10**12

    for i in range(len(hoge)):
        for j in range(len(DP)):
            x = DP[j]*hoge[i]
            DP.append(x)
            if (x + (N // x) - 2) < Min:
                Min = (x + (N // x) - 2)

    print(Min)

### FIXED CODE ###

N = int(input())


def make_divisors(n):  # 任意の整数の約数をリストで返す関数
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    divisors.sort()
    return divisors


List = make_divisors(N)

if len(List) % 2 == 1:
    print(List[len(List) // 2] * 2 - 2)
else:
    print(List[len(List) // 2 - 1] + (List[len(List) // 2] - 2))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    S = input().strip()
    Q = int(input())

    rev = 0
    for i in range(Q):
        A = [x for x in input().split()]
        if len(A) == 1:
            rev = (rev + 1) % 2
        else:
            f = int(A[1])
            c = A[2]
            if f == 1:
                if rev == 0:
                    S = c + S
                else:
                    S = S + c
            else:
                if rev == 0:
                    S = S + c
                else:
                    S = c + S

    if rev == 0:
        print(S)
    else:
        print(S[::-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    S = input().strip()
    Q = int(input())

    rev = 0
    sdeq = collections.deque()
    for s in S:
        sdeq.append(ord(s) - ord('a'))

    for i in range(Q):
        A = [x for x in input().split()]
        if len(A) == 1:
            rev = (rev + 1) % 2
        else:
            f = int(A[1])
            c = A[2]
            if f == 1:
                if rev == 0:
                    sdeq.appendleft(ord(c) - ord('a'))
                else:
                    sdeq.append(ord(c) - ord('a'))
            else:
                if rev == 0:
                    sdeq.append(ord(c) - ord('a'))
                else:
                    sdeq.appendleft(ord(c) - ord('a'))

    if rev == 0:
        for i in list(sdeq):
            print(chr(i + ord('a')), end="")
    else:
        for i in list(sdeq)[::-1]:
            print(chr(i + ord('a')), end="")
    print()



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

import re
import sys
input = sys.stdin.readline

s = input()
s = s.replace('BC', 'D')
s = re.split('[BC]', s)
res = 0

for kk in s:
  if not kk:
    continue
  while 'AD' in kk:
    res += kk.count('AD')
    kk = kk.replace('AD', 'DA')
    
print(res)

### FIXED CODE ###

import re
import sys
input = sys.stdin.readline

s = input()
s = s.replace('BC', 'D')
s = re.split('[BC]', s)
res = 0

for kk in s:
  if not kk:
    continue
  d = 0
  for a in kk[::-1]:
    if a == 'D':
      d += 1
    else:
      res += d
    
print(res)