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

# Coins Respawn
import sys
sys.setrecursionlimit(10**7)
from collections import deque
N, M, P = map(int, input().split())
graph = []
d = deque()

# グラフの整形

from_1 = [[] for i in range(N+1)]
from_N = [[] for i in range(N+1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    from_1[a].append(b)
    from_N[b].append(a)
    d.append((a, b, P-c))


accessible_1 = [False for i in range(N+1)]
accessible_N = [False for i in range(N+1)]


def dfs_1(s):
    accessible_1[s] = True
    for node in from_1[s]:
        if accessible_1[node] == False:
            dfs_1(node)


def dfs_N(s):
    accessible_N[s] = True
    for node in from_N[s]:
        if accessible_N[node] == False:
            dfs_N(node)


dfs_1(1)
dfs_N(N)

isok = [False for i in range(N+1)]
for i in range(N+1):
    if accessible_1[i] and accessible_N[i]:
        isok[i] = True


while d:
    p, q, weight = d.popleft()
    if isok[p] and isok[q]:
        graph.append((p, q, weight))

# ベルマンフォード


def bellman_ford(s,n):
    dist = [10**20 for i in range(n+1)]
    dist[s] = 0
    for i in range(1, n+1):
        flag = False
        for some in graph:
            a, b, d = some[0], some[1], some[2]
            newlen = dist[a]+d
            if newlen < dist[b]:
                flag = True
                dist[b] = newlen
        if not flag:
            break
        if i == n:
            return False
    return dist

K=bellman_ford(1,N)
if K==False:
     print(-1)
else:
    print(max(0,-K[N]))

### FIXED CODE ###

# Coins Respawn
import sys
sys.setrecursionlimit(10**7)
from collections import deque
N, M, P = map(int, input().split())
graph = []
d = deque()

# グラフの整形

from_1 = [[] for i in range(N+1)]
from_N = [[] for i in range(N+1)]

for _ in range(M):
    a, b, c = map(int, input().split())
    from_1[a].append(b)
    from_N[b].append(a)
    d.append((a, b, P-c))


accessible_1 = [False for i in range(N+1)]
accessible_N = [False for i in range(N+1)]


def dfs_1(s):
    accessible_1[s] = True
    for node in from_1[s]:
        if accessible_1[node] == False:
            dfs_1(node)


def dfs_N(s):
    accessible_N[s] = True
    for node in from_N[s]:
        if accessible_N[node] == False:
            dfs_N(node)


dfs_1(1)
dfs_N(N)

isok = [False for i in range(N+1)]
for i in range(N+1):
    if accessible_1[i] and accessible_N[i]:
        isok[i] = True


while d:
    p, q, weight = d.popleft()
    if isok[p] and isok[q]:
        graph.append((p, q, weight))

# ベルマンフォード


def bellman_ford(s,n):
    dist = [10**20 for i in range(n+1)]
    dist[s] = 0
    for i in range(1, n+1):
        flag = False
        for some in graph:
            a, b, d = some[0], some[1], some[2]
            newlen = dist[a]+d
            if newlen < dist[b]:
                flag = True
                dist[b] = newlen
        if not flag:
            break
        if i == n:
            return False
    return dist

K=bellman_ford(1,N)
if K==False:
     print(-1)
else:
    print(max(0,-K[N]))
### BUGGY CODE ###

N, K = map(int, input().split())
scores = list(map(int, input().split()))
grades =[]
for i in range(K+1,N+2):
    before = 1
    for j in range(K):
        before = before*scores[i-j-2]
    grades.append(before)

for k in range(N-K):
    if grades[k]>=grades[k+1]:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

N, K = map(int, input().split())
scores = list(map(int, input().split()))

for k in range(N-K):
    if scores[k] >= scores[k+K]:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

import math
def c(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
mod = 10**9+7
n,a,b = map(int, input().split())
ans = 2**n-1
ans -= c(n,a)+c(n,b)
print(ans%mod)

### FIXED CODE ###

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

mod = 10**9+7
ans = pow(2,n,mod)-1

nca = 1
ncb = 1

for i in range(b):
    ncb = ncb*(n-i)%mod
    ncb *= pow(i+1,mod-2,mod)
    if i+1==a:
        nca = ncb

ans -= nca+ncb
print(ans%mod)
### BUGGY CODE ###

from collections import deque
N = int(input())
A = sorted(list(map(int, input().split())))

ans = 0
  
while True:
  d = A.pop(0)
  if d in A:
    ans -= 1
  
  for a in A[::-1]:
    if a % d == 0:
      A.remove(a)
  ans += 1
  if A:
    True
  else:
    break
  
print(ans)

### FIXED CODE ###

from numba import njit
import numpy as np

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

@njit
def main(A):
  count = np.zeros(10**6 + 10, np.int32)
  
  for i in range(N):
    a = A[i]
    if count[a] > 1:
      continue
    count[::a] += 1
    
  ans = 0
  for i in range(N):
    ans += count[A[i]] == 1
    
  #print(count[:100])
  return ans
  
print(main(np.array(A, np.int32)))
### BUGGY CODE ###

# cook your dish here
n=int(input())
a=[int(x) for x in input().split()]
ans=1  
sorted(a)
for i in range(n):
    ans*=a[i]
    if ans==0:
        break
    if ans>(int)(1e18):
        ans=-1
print(ans)

### FIXED CODE ###

# cook your dish here
n=int(input())
a=[int(x) for x in input().split()]
ans=1  
mod=int(1e18)
for i in range(n):
    if a[i]==0:
        ans=0 
        break 
for i in range(n):
    ans*=a[i]
    if ans>mod:
        ans=-1 
        break 
    if ans==0:
        break
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

N,Q = map(int, input().split())
graph = [[] for _ in range(N)]
counter = [0]*N
for i in range(N-1):
    a,b = map(int, input().split()) 
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def dfs(v, parent):
    for i in graph[v]:
        if i==parent:
            continue
        counter[i] += counter[v]
        dfs(i, v)
        
dfs(0, -1)
print(*counter)   

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

N,Q = map(int, input().split())
graph = [[] for _ in range(N)]
counter = [0]*N
for i in range(N-1):
    a,b = map(int, input().split()) 
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def dfs(v, parent):
    for i in graph[v]:
        if i==parent:
            continue
        counter[i] += counter[v]
        dfs(i, v)
        
dfs(0, -1)
print(*counter)
### BUGGY CODE ###

from itertools import accumulate

def S(a, b):
    return cl[b] - (0 if a == 0 else cl[a-1])

def partial(start, end, last):
    odiff = None
    for c in range(start, end+1):
        p = S(start,c)
        q = S(c+1,end)
        diff = abs(p-q)
        if odiff is None:
            odiff = diff
        if odiff < diff:
            return c, mp, mq
        odiff = diff
        mp = p
        mq = q

if __name__ == '__main__':
    # read input
    n = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(l))
    clen = len(l)

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    result = None
    c1 = 1
    c3 = 3
    for i in range(1,clen-2):
        # LEFT
        (c1, mb, mc) = partial(0, i, c1)
        # RIGHT
        c3, md, me = partial(i+1, clen-1, c3)

        # evaluate
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        if result is None:
            result = diff
        else:
            if result > diff:
                result = diff

    print(result)

### FIXED CODE ###

from itertools import accumulate

def Sdiff(s, m, e):
    # Sdiff(s, m, e) = [A_s, A_s+1 ..., A_m] [A_m+1 .... A_e]
    #    L = cl[m]-cl[s-1], R = cl[e] - cl[m]
    # diff(L,R) = abs(cl[m] - cl[s-1] - cl[e] + cl[m]) = abs(2*cl[m] - cl[s-1] - cl[e])

    x = 0 if s == 0 else cl[s-1]
    return abs(2*cl[m] - x - cl[e])

def partial(start, end, last):
    #print("partial: {}-{} last:{}".format(start,end, last))
    odiff = Sdiff(start, last, end)

    for c in range(last, end):
        diff = Sdiff(start, c, end)
        #print("partial loop: c:{}, diff:{} -> {}".format(c, odiff, diff))
        if odiff < diff:
            return c-1
        odiff = diff
    return c

if __name__ == '__main__':
    # read input
    N = int(input())
    l = list(map(int, input().split()))
    # create cumlative list first
    cl = list(accumulate(l))

    #  0  F(i)      i i+1 G(i)      len-1
    #  |------|------|-------|-------|
    #         c0    c1       c2
    #  <-----L------> <------R------->
    # pick up a c1 (i:i+1) and evaluate
    result = 9 * 10e9
    c1 = 0
    c3 = 2
    for i in range(1, N-2):
        #print("LEFT:RIGHT {}/={}=/{}".format(l[0:i+1], i, l[i+1: N]))
        # LEFT
        c1 = partial(0, i, c1)
        # RIGHT
        c3 = partial(i+1, N-1, c3)

        # evaluate
        mb = cl[c1]
        mc = cl[i] - mb
        md = cl[c3] - cl[i]
        me = cl[N-1] - cl[c3]
        diff = abs(max(mb, mc, md, me) - min(mb, mc, md, me))
        #print("\t\t{}/{}/{}: [{} {} {} {}]".format(c1, i, c3, mb, mc, md, me))
        #print("\t\tdiff={}".format(diff))
        if diff < result:
            result = diff

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

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

f=1
c=0
for i in l:
    f*=i
    
if f > 10**18:
    print(-1)
else:
    print(f)

### FIXED CODE ###

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

f=1
c=0
for i in l:
    f*=i
    if f > 10**18:
        c=1
        break
    
if 0 in l:
    print(0)
elif c==1:
    print(-1)
else:
    print(f)
### BUGGY CODE ###

N = int(input())

A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))


"""
minnum以上で最小の数のindexを返す。無いときはlen(List)を返す
計算量log(len(List))
"""
def bts(List,minnum,under=0):
    if List[0]>=minnum:
        return under
    if List[-1]<minnum:
        return len(List)+under
    i = int(len(List)/2)
    if List[i]>=minnum and List[i-1]<minnum:
        return i + under
    if List[i]<minnum:
        return bts(List[i+1:],minnum,under+i+1)
    return bts(List[:i],minnum,under)


res = 0
for i in range(N):
    b = B[i]
    a = bts(A,b)
    c = N - bts(C,b+1)
    res += a*c

print(res)


### FIXED CODE ###

N = int(input())

A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))


"""
minnum以上で最小の数のindexを返す。無いときはlen(List)を返す
計算量log(len(List))

def bts(List,minnum,under=0):
    if List[0]>=minnum:
        return under
    if List[-1]<minnum:
        return len(List)+under
    i = int(len(List)/2)
    if List[i]>=minnum and List[i-1]<minnum:
        return i + under
    if List[i]<minnum:
        return bts(List[i+1:],minnum,under+i+1)
    return bts(List[:i],minnum,under)

"""

def binary_search(list, item):
    if list[0]>=item:
        return 0
    if list[-1]<item:
        return len(list)

    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess >= item and list[mid-1] < item:
            return mid
        if guess >= item:
            high = mid -1
        else:
            low = mid + 1

    return None

res = 0
for i in range(N):
    b = B[i]
    a = binary_search(A,b)
    c = N - binary_search(C,b+1)
    res += a*c

print(res)
### BUGGY CODE ###

n = int(input())
nums = [int(input()) for _ in range(n)]
memo = set(nums)
ans = 0
for m in memo:
    if nums.count(m)%2: ans += 1
print(ans)

### FIXED CODE ###

memo = set()
for i in range(int(input())):
    a = input()
    if a in memo: memo.remove(a)
    else: memo.add(a)
print(len(memo))
### BUGGY CODE ###

import re
n,q = map(int, input().split())
s = input()
l = [0]*q
r = [0]*q
for i in range(q):
  l[i],r[i] = map(int, input().split())

counts = [0]*n

pattern = "AC"
result = re.finditer(pattern, s)
for res in result:
  counts[res.start()] = 1

for i in range(q):
  print(sum(counts[l[i]-1:r[i]-1]))

### FIXED CODE ###

n,q = map(int, input().split())
s = input()

counts = [1 if s[i:i+2]=="AC" else 0 for i in range(n)]

cum_counts=[0]*n
for i in range(1,n):
  cum_counts[i]=cum_counts[i-1]+counts[i-1]

#print(counts)
#print(cum_counts)

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

n = int(input())
arr = input().split(' ')
arr = [int(i) for i in arr]
count = 0
for idx in range(n):
  num = arr[idx]
  comp = min(arr[:idx+1])
  if num <= comp:
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
arr = input().split(' ')
arr = [int(i) for i in arr]
count = 0
minimum = arr[0]
for idx in range(n):
  num = arr[idx]
  if num <= minimum:
    minimum = num
    count += 1
print(count)
### BUGGY CODE ###

N, K = [int(x) for x in input().split()]
P = [0] + [int(x) for x in input().split()]
C = [0] + [int(x) for x in input().split()]

max_score = max(C[1:])
for init in range(1, N + 1):   # 初めの場所をinitとする
    score = [0]  # k回移動後のスコア
    i = init
    for k in range(1, K + 1):
        i = P[i]  # k回移動後に着くところ
        score.append(score[-1] + C[i])
        max_score = max(max_score, score[k])
        if i == init:  # ループ検出
            loop_score = score[-1]
            loop_len = k
            if loop_score > 0:
                max_score = max(max_score, max(score[j] + loop_score * ((K - j) // loop_len) for j in range(1, loop_len + 1)))
            break

print(max_score)

### FIXED CODE ###


from collections import defaultdict
INF = float('inf')
N, K = [int(x) for x in input().split()]
P = [0] + [int(x) for x in input().split()]
C = [0] + [int(x) for x in input().split()]

max_score = -INF
for init in range(1, N + 1):   # 初めの場所をiとする
    score = defaultdict(int)  # int/bool/list....
    # visited = defaultdict(init)  # int/bool/list....
    visited = [-1] * (N + 1)
    visited[init] = 0  # 何回移動後に着いたか？
    i = init
    max_init = -INF
    for k in range(1, K + 1):
        prev = i
        i = P[i]    # k回移動後に着くところ



        # if not visited[i]:
        if visited[i] < 0:  # まだ訪れてなかった
            visited[i] = k
            score[i] = score[prev] + C[i]
            max_init = max(max_init, score[i])
            continue

        loop_score = (score[prev] + C[i]) - score[i]
        loop_len = k - visited[i]

        score[i] = score[prev] + C[i]
        max_init = max(max_init, score[i])

        if k == K:
            break # これ以上移動できない

        start = i   # ループを開始するノード
        loop_num = (K - k) // loop_len # ループをあと何回回れるか
        loop_rem = (K - k) % loop_len

        if loop_rem == 0:
            loop_num -= 1
            loop_rem = loop_len

        jj = start
        temp = 0
        temp_max = 0
        for l in range(loop_rem):
            jj = P[jj]
            temp += C[jj]
            temp_max = max(temp_max, temp)

        # loop_max = temp_max + max(loop_num * loop_score, 0)
        loop_max = temp_max + loop_num * loop_score
        max_init = max(max_init, score[start] + loop_max)
        break

    max_score = max(max_score, max_init)

if max_score == -INF:
    max_score = max(C[1:])

print(max_score)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m=(int(i) for i in input().split())
a = [int(input()) for i in range(m)]
#print(n,m,a)

d=[0 for i in range(100000+10)]
p=1000000007
#n=100
#a=[1, 23, 45, 67, 89]

d[0]=1
if a.count(1) == 0:
    d[1]=1
else:
    d[1]=0
    
if a.count(2) == 0:
    d[2]=d[1]+d[0]
else:
    d[2]=0
    
for i in range(2,n+1):
    if a.count(i) == 0:
        d[i]=d[i-1]+d[i-2]
        d[i]=d[i]%p
    else:
        d[i]=0
#print(d)

print(d[n]%p)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m=(int(i) for i in input().split())
a = [int(input()) for i in range(m)]
#print(n,m,a)

d=[0 for i in range(100000+10)]
p=1000000007
#n=100
#a=[1, 23, 45, 67, 89]
aa=[0 for i in range(100000+10)]

for i in a:
    aa[i]=1
#print(aa)

d[0]=1
if aa[1] == 0:
    d[1]=1
else:
    d[1]=0
    
if aa[2] == 0:
    d[2]=d[1]+d[0]
else:
    d[2]=0
    
for i in range(2,n+1):
    if aa[i] == 0:
        d[i]=d[i-1]+d[i-2]
        d[i]=d[i]%p
    else:
        d[i]=0
#print(d)

print(d[n]%p)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,W = map(int, input().split())
dp = [0 for _ in range(W+1)]
for _ in range(N):
	w,v = map(int, input().split())
	for i in range(W,0,-1):
		if i>=w:
			dp[i] = max(dp[i],dp[i-w]+v)
	
print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
	N,W = map(int, input().split())
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = map(int, input().split())
		for i in range(W,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = a
				else:
					dp[i] = b
		
	print(dp[-1])

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

import sys
from collections import Counter

read = sys.stdin.read


def sieve_of_eratosthenes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def prime_factorize(n):
    a = []
    for i in primes:
        while n % i == 0:
            a.append(i)
            n //= i
        if n == 1:
            return a


N, *A = map(int, read().split())
mod = 10 ** 9 + 7

primes = sieve_of_eratosthenes(10 ** 6)
dic = {i: 0 for i in primes}

n = len(primes)
p = [0] * n
for i in A:
    if i == 1:
        continue
    tmp = Counter(prime_factorize(i))
    for key, value in tmp.items():
        # print(key, value)
        if dic[key] < value:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    if j == 0:
        continue
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = 0
for i in A:
    answer += lcm * pow(i, mod - 2, mod)
    answer %= mod

print(answer)


### FIXED CODE ###

import sys
from collections import Counter

read = sys.stdin.read


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def sieve_of_eratosthenes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def prime_factorize(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


N, *A = map(int, read().split())
mod = 10 ** 9 + 7

primes = sieve_of_eratosthenes(max(A) + 1)
dic = {i: 0 for i in primes}

n = len(primes)
p = [0] * n
for i in A:
    tmp = Counter(prime_factorize(i))
    for key, value in tmp.items():
        #print(key, value)
        if dic[key] < value:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    if j == 0:
        continue
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = 0
for i in A:
    answer += lcm * pow(i, mod - 2, mod)
    answer %= mod

print(answer)
### BUGGY CODE ###

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

for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

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

for x in a:
    if x in ans.keys():
        ans[x] += 1
    else:
        ans[x]=1

for i in range(1,n+1):
    print(ans.get(i,0))
### BUGGY CODE ###

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

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

Swap=["" for i in range(M)]

for i in range(M):
    Swap[i]=set(map(int,input().split()))


Y=[set() for i in range(N)]
Unstacked=list(range(M))

Y[0]=Y[0]|Swap[0]
Unstacked.remove(0)
j=0
k=0

while True:
    while Unstacked !=[]:
        s=Unstacked[j]

        if Y[k] & Swap[s] !=set():

            Y[k]=Y[k]|Swap[s]
            del Unstacked[j]
            #print(Y,j,Unstacked)
            j=0

        elif j <len(Unstacked)-1:
            j+=1

        else: break

    if Unstacked != []:
        
        k+=1
        Y[k]=Swap[Unstacked[0]]
        Unstacked.remove(Unstacked[0])
        j=0

    else:
        break


#print(Y,j,k,Unstacked)

Other=set(range(1,N+1))
for l in range(k+1):
    Other=Other - Y[l]
    #print(l,Y,Other)

#print(Other)

Other=list(Other)

count=0

for i in range(k+1):
    for j in list(Y[i]):
        if P[j-1] in Y[i]:
            #print(i,j,P[j-1],Y[i])
            count+=1
        

for m in Other:
    if P[m-1]==m:
        #print(m)
        count+=1

print(count)

### FIXED CODE ###

N, M = map(int,input().split())
P=list(map(int,input().split()))

Group=[i for i in range(N+1)]


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

for i in range(N):
    if find(P[i])==find(i+1):
        count+=1


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

import sys

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

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)

sys.exit()


### FIXED CODE ###

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

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)
### BUGGY CODE ###

import sys
n = int(sys.stdin.readline().strip())
list = []
ans = 0
for x in range(n):
  list.append(sorted(sys.stdin.readline().strip()))
for i in range(len(list)-1):
  for j in range(i+1, n):
    if list[i] == list[j]:
      ans +=1
print(ans)

### FIXED CODE ###

import sys
n = int(sys.stdin.readline().strip())
list = [''.join(sorted(sys.stdin.readline().strip())) for i in range(n)]
d = {}
ans = 0
for x in list:
  if x in d:
    ans += d[x]
    d[x] += 1
  else:
    d[x] = 1
print(ans)
### BUGGY CODE ###

def give(list):
    i=0
    count=0
    while i<len(list)-2:
        if list[i]=='A' and list[i+1]=='B' and list[i+2]=='C':
            count+=1
            list[i]='B'
            list[i+1]='C'
            list[i+2]='A'
            if i>=1:
                i-=1
            else:
                i+=2
        else:
            i+=1
    return count
s=list(input())
print(give(s))


### FIXED CODE ###

def give(list):
    i=0
    count=0
    count1=0
    while i<len(list)-2:
        if list[i]=='A':
            count1+=1
            if list[i]=='A' and list[i+1]=='B' and list[i+2]=='C':
                list[i+2]='A'
                
                i+=2
                count+=count1
                count1-=1
                
            else:
                i+=1
        else:
            count1=0
            i+=1
    return count
s=list(input())
print(give(s))