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

from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    pre1 = []
    pre2 = []
    que = deque()
    for e in range(n):
        que.append(e)
        dis = [0 for _ in range(n)]
        did = [False for _ in range(n)]
        did[e] = True
        if e == k-1:
            pre1.append(0)
        while que:
            tank = deque()
            while que:
                i = que.pop()
                for j in range(len(graph[i])):
                    go = graph[i][j][0]
                    d = graph[i][j][1]
                    if did[go]:
                        continue
                    dis[go] = dis[i] + d
                    if k-1 == go:
                        pre1.append(dis[go])
                        tank=deque()
                        que=deque()
                        break
                    tank.append(go)
                    did[go] = True
            que = tank
    que = deque()
    que.append(k-1)
    dis = [0 for _ in range(n)]
    did = [False for _ in range(n)]
    did[k-1] = True
    while que:
        tank = []
        while que:
            i = que.pop()
            for j in range(len(graph[i])):
                go = graph[i][j][0]
                d = graph[i][j][1]
                if did[go]:
                    continue
                dis[go] = dis[i] + d
                tank.append(go)
                did[go] = True
        que = tank
    pre2 = dis

    pre1 = tuple(pre1)
    pre2 = tuple(pre2)
    for _ in range(q):
        x,y = map(int,input().split())
        print( pre1[x-1] + pre2[y-1] ) 

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    que = deque([k-1])
    dis = [-1 for _ in range(n)]
    dis[k-1]=0
    while que:
        i = que.pop()
        for j in range(len(graph[i])):
            go = graph[i][j][0]
            d = graph[i][j][1]
            if dis[go]==-1:
                dis[go] = dis[i] + d
                que.append(go)
    for _ in range(q):
        x,y = map(int,input().split())
        print( dis[x-1] + dis[y-1] ) 

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

import fractions
A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

get_primes(10**2)

for p in get_primes(10**6):
  if p > C:
    break
  if C % p == 0:
    pfac.append(p)
    while C % p == 0:
      C //= p
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)

### FIXED CODE ###

import fractions
import math

A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

def get_primes2(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n == 1:
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

for q in get_primes2(min(C, 10**6)):
  if q ** 2 > C:
    break
  if C % q == 0:
    pfac.append(q)
    while C % q == 0:
      C //= q
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)
### BUGGY CODE ###

H, N = map(int, input().split(" "))
dp = [[float('inf') for i in range(H + 1)] for j in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[i][j] != float('inf'):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            dp[i][min(j + A, H)] = min(dp[i][min(j + A, H)], dp[i][j] + B)
print(dp[N][H])


### FIXED CODE ###

import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [1e10 for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != 1e10:
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print(dp[H])
### BUGGY CODE ###

import numpy as np
s=input()
A=np.array([0,0,0,0])
B=np.array([0,0,0,0])
C=np.array([0,0,0,0])
t=0
for c in s:
	if c=="A":
		A[0]+=1
	if c=="B":
		B+=A
	if c=='C':
		C+=B
	if c=='?':
		C+=np.roll(B,1)
		B+=np.roll(A,1)
		A[1]+=1
		t+=1
ans=0
for i in range(4):
	ans+=pow(3,t-i)*C[i]
print(int(ans%1000000007))

### FIXED CODE ###

#a,b=map(int,input().split())
import numpy as np

s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=wayC+wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))
### BUGGY CODE ###

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

MOD = 998244353
cmbarr = [1] * (N)
for r in range(N-1):
    cmbarr[r+1] = cmbarr[r] * (N - 1 - r) // (r + 1)

A = [M*pow(M-1,N-1-i,MOD) % MOD for i in range(K+1)]
A = [A[i] * cmbarr[i] % MOD for i in range(K+1)]
print(sum(A) % MOD)

### FIXED CODE ###

N,M,K = list(map(int,input().split()))
MOD = 998244353

fac = [1] * (N+1)
inv = [1] * (N+1)
ifac = [1] * (N+1)
for i in range(2,N+1):
    fac[i]=(fac[i-1]*i)%MOD
    inv[i]= -(inv[MOD%i]*(MOD//i))%MOD
    ifac[i]=(ifac[i-1]*inv[i])%MOD

cmbarr = [1] * N
for r in range(N-1):
    cmbarr[r+1] = cmbarr[r] * (N - 1 - r) * inv[r + 1] % MOD

A = [M*pow(M-1,N-1-i,MOD)*cmbarr[i] % MOD for i in range(K+1)]
print(sum(A) % MOD)
### BUGGY CODE ###

import collections

n, m = map(int, input().split())
if m == 0:
    print(1)
    exit()
if m == 1:
    print(2)
    exit()
boss = {i: 0 for i in range(1, n + 1)}

def look_boss(num):
    if boss[num] == 0:
        return num
    while num != boss[num]:
        num = boss[num]
    return num

for _ in range(m):
    a, b = map(int, input().split())
    boss_a = look_boss(a)
    boss[a] = boss_a
    boss_b = look_boss(b)
    boss[b] = boss_b
    if boss_a != boss_b:
        boss[boss_b] = boss_a

count = [0]*(n+1)
for i in range(1, n+1):
    count[look_boss(i)] += 1
print(max(count))


### FIXED CODE ###

import collections

n, m = map(int, input().split())
if m == 0:
    print(1)
    exit()
if m == 1:
    print(2)
    exit()
boss = list(range(n))

def look_boss(target):
    num = target
    while num != boss[num]:
        num = boss[num]
    boss[target] = num
    return num

for _ in range(m):
    a, b = map(int, input().split())
    boss_a = look_boss(a-1)
    boss_b = look_boss(b-1)
    if boss_a != boss_b:
        boss[boss_b] = boss_a

count = [0]*n
for i in range(n):
    count[look_boss(i)] += 1
print(max(count))
### BUGGY CODE ###

n, x = map(int,input().split())

if n % 2 == 0 and n//2 == x:
    print(3 * x)
    exit()

if x > n // 2:
    x = n - x

xx = x
yy = n - x

ans = n
i = 0
f = False

while True:
    if yy >= xx:
        ans += 2 * xx
        yy -= xx

        if yy == 0:
            ans -= xx
            f = True
            break

    if xx > yy:
        ans += yy * 2
        xx -= yy

        if xx == 0:
            ans -= yy
            f = True
            break

print(ans)


### FIXED CODE ###

n, x = map(int,input().split())

if n % 2 == 0 and n//2 == x:
    print(3 * x)
    exit()

if x > n // 2:
    x = n - x

xx = x
yy = n - x


ans = n
i = 0

while True:
    
    if yy >= xx:
        ans += 2 * (yy // xx) * xx
        yy %= xx

        if yy == 0:
            ans -= xx
            break

        if yy < xx:
            tmp = xx
            xx = yy
            yy = tmp

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

from sys import stdin
A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
resultList = [ A - c for c in range(C + 1) if c == K - A - B]
print(max(resultList))


### FIXED CODE ###

from sys import stdin
A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
if (A >= K):
    print(K)
else:
    if (B >= (K - A)):
        print(A)
    else:
        print(2*A + B - K)
### BUGGY CODE ###

import itertools,sys
eq=[""]*10
eq[0]="{0}"
eq[1]=eq[0]+"+2*{1}"
eq[2]=eq[1]+"+3*{2}"
eq[3]=eq[2]+"+4*{3}"
eq[4]=eq[3]+"+5*{4}"
eq[5]=eq[4]+"+6*{5}"
eq[6]=eq[5]+"+7*{6}"
eq[7]=eq[6]+"+8*{7}"
eq[8]=eq[7]+"+9*{8}"
eq[9]=eq[8]+"+10*{9}"
for a in sys.stdin:
  c=0
  n,s=map(int,a.split())
  for e in itertools.permutations(range(10),n):
    if eval(eq[n-1].format(*e))==s: c+=1
  print c

### FIXED CODE ###

import sys
K=1024
N=331
R=range(K)
B=[1,2,4,8,16,32,64,128,256,512]
C=[0]*K
D=[[0 for i in range(N)]for j in R]

for i in R:
  s=format(i,'b')
  n=s.count('1')
  C[i]=n
  if n==1:D[i][B.index(i)]=1
  else:
    for j in range(len(s)):
      if s[-j-1]=='1':
        dp=n*j
        i2=i-B[j]
        for k in range(N-dp):
          D[i][k+dp]+=D[i2][k]
   
for a in sys.stdin:
  n,s=map(int,a.split())
  x=0
  if s<N:x=sum([D[i][s] for i in R if C[i]==n])
  print x
### BUGGY CODE ###

n = int(input())
l = []
ans = 0

for i in range(n):
    a = sorted(input())
    l.append("".join(a))

sl = set(l)


for i in sl:
    com = l.count(i)
    ans += com*(com - 1)//2

print(ans)

### FIXED CODE ###

n = int(input())
d = {}
ans = 0

for i in range(n):
    s = "".join(sorted(input()))
    if s in d:
        d[s] += 1
    else:
        d[s] = 1

for i in d.values():
    ans += i*(i - 1)//2

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

n,k,q = map(int,input().split())
l = []
l2 = []
for i in range(q):
    l.append(int(input()))
for i in range(0,n):
    if k + l.count(i+1) - q>0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k,q = map(int,input().split())
l = [0]*n
l2 = []
for i in range(q):
    l[int(input())-1] += 1
for i in range(0,n):
    if k + l[i] - q>0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

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

dp = [float("inf") for _ in range(N)]
derta = [[-1 for i in range(N)] for j in range(N)]

def cost(n, m):
  if derta[n][m] == -1:
    derta[n][m] = abs(h[n] - h[m])
    return derta[n][m]
  else:
    return derta[n][m]

dp[0] = 0

for i in range(N):
  for j in range(1, K + 1):
    if (i + j) <= N -1:
      dp[i + j] = min(dp[i + j], dp[i] + cost(i, i + j))

print(dp[N - 1])

### FIXED CODE ###

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

dp = [float("inf") for _ in range(N)]

def cost(n, m):
  return abs(h[n] - h[m])

dp[0] = 0

for i in range(N):
  for j in range(1, K + 1):
    if (i + j) <= N -1:
      dp[i + j] = min(dp[i + j], dp[i] + cost(i, i + j))

print(dp[-1])
### BUGGY CODE ###

from collections import Counter
from itertools import combinations
import sys
input = sys.stdin.readline
n = int(input())
cnt = Counter(["".join(sorted(input().split()[0])) for _ in range(n)])
print(sum([len(list(combinations([""] * cnt[c], 2))) for c in cnt]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = ["".join(sorted(input().split()[0])) for _ in range(n)]
cnt = {}
result = 0
for si in s:
    if si in cnt:
        result += cnt[si]
        cnt[si] += 1
    else:
        cnt[si] = 1
print(result)
### BUGGY CODE ###

def calc_cost2(h, k):
    n = len(h)
    if (n == 0):
        return 0

    cost = list()
    cost.append(0)
    for i in range(1, len(h)):        
        tmp = cost[i-1] + abs(h[i] - h[i-1])
        for s in range(max(0, i-k), i):
            tmp = min(tmp, cost[s] + abs(h[i] - h[s]))

        cost.append(tmp)

    return cost[n-1]

if __name__ == "__main__":
    n, k = list(map(int, input().split(" ")))
    h = list(map(int, input().split(" ")))
    res = calc_cost2(h, k)
    print(res)

### FIXED CODE ###

def calc_cost2(h, k):
    n = len(h)
    if (n == 0):
        return 0

    cost = n * [None]
    cost[0] = 0
    for i in range(1, len(h)):
        cost[i] = min([cost[s] + abs(h[i] - h[s]) for s in range(max(0, i-k), i)])
        #cost[i] = min(map(lambda s: cost[s] + abs(h[i] - h[s]), range(max(0, i-k), i)))

    return cost[n-1]


if __name__ == "__main__":
    n, k = list(map(int, input().split(" ")))
    h = list(map(int, input().split(" ")))
    res = calc_cost2(h, k)
    print(res)
### BUGGY CODE ###

n = int(input())

res = 1
big = 10**9 + 7
for i in range(n):
    res *= (i+1)
    
print(res%big)

### FIXED CODE ###

n = int(input())

res = 1
big = 10**9 + 7
for i in range(n):
    res *= (i+1)
    res %= big
    
print(res)
### BUGGY CODE ###

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

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

SC=[0,0,0,0]#0個,1個,2個,3個

for a in A:
    SC[a]+=1
SC=tuple(SC)

DAYSDICT=dict()

def days(SC):
    if DAYSDICT.get(SC)!=None:
        return DAYSDICT[SC]

    if SC[1]<0 or SC[2]<0 or SC[3]<0:
        return 0

    k=SC[1]+SC[2]+SC[3]

    if k==0:
        return 0

    DAYSDICT[SC]=N/k+days((SC[0]+1,SC[1]-1,SC[2],SC[3]))*SC[1]/k+days((SC[0],SC[1]+1,SC[2]-1,SC[3]))*SC[2]/k+days((SC[0],SC[1],SC[2]+1,SC[3]-1))*SC[3]/k
    return DAYSDICT[SC]

print(days(SC))

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

SC=[0,0,0]#1個,2個,3個

for a in A:
    SC[a-1]+=1
one,two,three=SC

DAYSDICT=[[[0.0]*301 for j in range(301)] for k in range(301)]
DAYSDICT[0][0][0]=0
def days(one,two,three):
    ANS=N
    if one>0:
        ANS+=DAYSDICT[one-1][two][three]*one
    if two>0:
        ANS+=DAYSDICT[one+1][two-1][three]*two
    if three>0:
        ANS+=DAYSDICT[one][two+1][three-1]*three
        
    DAYSDICT[one][two][three]=ANS/(one+two+three)


for k in range(three+1):
    for j in range(two+three+1-k):
        for i in range(one+two+three+1-j-k):
            if i==j==k==0:
                continue
            days(i,j,k)

print(DAYSDICT[one][two][three])
### BUGGY CODE ###

N = W = 0
g = []
MAX_V = 100100


def get_input():
    global N, W, g
    N, W = map(int, input().split())
    g = []
    for _ in range(N):
        g.append([int(x) for x in input().split()])


def dpcalc():
    global N, W, g
    # 動的計画法のテーブルを初期化
    dp = [[10 ** 11] * (MAX_V + 1) for _ in range(N + 1)]

    # テーブルをiの小さい方から順に計算してゆく
    for i in range(1, N + 1):
        for j in range(MAX_V + 1):
            w, v = g[i - 1]
            if j - v > 0:
                dp[i][j] = min(dp[i - 1][j - v]  +  w, dp[i - 1][j])
            else:
                dp[i][j] = min(dp[i - 1][j], w)

    for i in range(MAX_V, -1, -1):
        if dp[N][i] <= W:
            return i
    return 0


get_input()
print(dpcalc())


### FIXED CODE ###

import numpy as np

N = W = 0
g = []
MAX_V = 100100


def get_input():
    global N, W, g
    N, W = map(int, input().split())
    g = []
    for _ in range(N):
        g.append([int(x) for x in input().split()])


def dpcalc():
    global N, W, g
    # 動的計画法のテーブルを初期化
    dp = np.full((N + 1, MAX_V + 1), 10 ** 11)
    # dp = [[10 ** 11] * (MAX_V + 1) for _ in range(N + 1)]

    # テーブルをiの小さい方から順に計算してゆく
    r = 1
    for i in range(1, N + 1):
        w, v = g[i - 1]
        dp[i][:v + 1] = np.minimum(dp[i - 1][:v + 1], w)
        dp[i][v + 1:v + r] = np.minimum(dp[i - 1][1: r] + w, dp[i - 1][v + 1:v + r] )
        
        r += v
        
    for i in range(MAX_V, -1, -1):
        if dp[N][i] <= W:
            return i
    return 0


get_input()
print(dpcalc())
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import numpy as np

N, M, K = map(int, input().split())
A=np.array(list(map(int, input().split())))
B=np.array(list(map(int, input().split())))


sum_A = np.cumsum(A)
sum_B = np.cumsum(B)
list_N = [0 for i in range(len(A)+1)]

pre_n = len(B)

for i in range(len(A)+1):
    if i == 0:
        buf = sum_B[:pre_n]
        num_B = len(buf[buf<=K])
        pre_n = num_B
        list_N[i] = i + num_B
    else:
        if K>=sum_A[i-1]:
            buf = sum_B[:pre_n]
            num_B = len(buf[buf<=(K-sum_A[i-1])])
            pre_n = num_B
            list_N[i] = i + num_B
        else:
            list_N[i] = 0
    
print(np.max(list_N))

### FIXED CODE ###

# coding: utf-8
# Your code here!
from itertools import accumulate
#import numpy as np

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

sum_A = list(accumulate(A))
sum_B = list(accumulate(B))


#sum_A = np.cumsum(A)
#sum_B = np.cumsum(B)

list_N = [0 for i in range(len(A)+1)]

pre_n = len(B)

for i in range(len(A)+1):
    if i == 0:
        num_B = 0
        for j in range(pre_n)[::-1]:
            if sum_B[j] <= K:
                num_B = j+1
                break
            else:
                continue
        #len(buf[buf<=K])
        pre_n = num_B
        list_N[i] = i + num_B
    else:
        if K>=sum_A[i-1]:
            num_B = 0
            for j in range(pre_n)[::-1]:
                if sum_B[j] <= (K-sum_A[i-1]):
                    num_B = j+1
                    break
                else:
                    continue
            #len(buf[buf<=(K-sum_A[i-1])])
            pre_n = num_B
            list_N[i] = i + num_B
            #print(K-sum_A[i-1])
            #print(i, num_B)
        else:
            list_N[i] = 0
    
#print(A)
#print(B)
#print(sum_A)
#print(sum_B)
#print(list_N)
print(max(list_N))
### BUGGY CODE ###

s = input()[::-1]
num = 0
last = 0
d = 1
count={}
for k in range(2019):
    count[k] = 0
    
count[0] =1  # 割り切れるとき

for i in s:
    num = (int(i) * d + num)%2019
    
    d *= 10
    count[num] += 1
    
ans = 0
for j in range(2019):
    ans += count[j] * (count[j]-1) //2
print(ans)

### FIXED CODE ###

s = input()[::-1]
num = 0
last = 0
d = 1
count={}
for k in range(2019):
    count[k] = 0
    
count[0] =1  # 割り切れるとき

for i in s:
    num = (int(i) * d + num)%2019
    
    d *= 10
    d %= 2019
    count[num] += 1
    
ans = 0
for j in range(2019):
    ans += count[j] * (count[j]-1) //2
print(ans)
### BUGGY CODE ###

def lcs(s,t):
    m = len(s)
    n = len(t)

    dp = [[0]*(n+1) for _ in range(m+1)]

    for i in range(1,m+1):
        for j in range(1,n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = 1+ dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    
    
    substr = ""
    i,j = m,n
    while i>0 and j>0:
        if s[i-1] == t[j-1]:
            substr+=s[i-1]
            i-=1
            j-=1
        elif dp[i][j-1]>dp[i-1][j]:
            j-=1
        else:
            i-=1
    return substr[::-1]
    
    

# s = "abracadabra"
# t = "avadakedavra"
# s = "axyb"
# t = "abyxb"
s = input()
t = input()
print(lcs(s,t))

### FIXED CODE ###

def lcs(s,t):
    m = len(s)
    n = len(t)

    dp = [[0]*(n+1) for _ in range(m+1)]

    for i in range(1,m+1):
        for j in range(1,n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = 1+ dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    
    
    substr = ""
    i,j = m,n
    while i>0 and j>0:
        if s[i-1] == t[j-1]:
            substr+=s[i-1]
            i-=1
            j-=1
        elif dp[i][j-1]>dp[i-1][j]:
            j-=1
        else:
            i-=1
    return substr[::-1]
    
    

# s = "abracadabra"
# t = "avadakedavra"
# s = "axyb"
# t = "abyxb"
s = input()
t = input()
print(lcs(s,t))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def dfs(v,path):
  for u in g[v]:
    if check[u]==0:
      check[u]=1
      return dfs(u,path+[u])
  else:
    return path

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  u,v=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
check=[0]*(n+1)
check[1]=1
ans=dfs(1,[])[::-1]
ans+=[1]
ans+=dfs(1,[])
print(len(ans))
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def dfs(v,path):
  for u in g[v]:
    if check[u]==0:
      check[u]=1
      path.append(u)
      return dfs(u,path)
  else:
    return path

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  u,v=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
check=[0]*(n+1)
check[1]=1
ans=dfs(1,[])[::-1]
ans+=[1]
ans+=dfs(1,[])
print(len(ans))
print(*ans)
### BUGGY CODE ###

MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if i%50==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

print(dp[n][5]%MOD)

### FIXED CODE ###

MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
count=0
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if count%50==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      count+=1
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

print(dp[n][5]%MOD)
### BUGGY CODE ###

from copy import deepcopy

def solve():
    s = [_ for _ in raw_input()]
    ans = 0
    chlist = []
    for i in range(len(s) - 2):
        if s[i] == 'A':
            chlist.append(i)
    found = True
    while found:
        found = False
        tmp_cl = deepcopy(chlist)
        for it in range(len(tmp_cl)):
            i = chlist[it]
            if s[i:(i+3)] == ['A', 'B', 'C']:
                s[i], s[i+1], s[i+2] = 'B', 'C', 'A'
                chlist[it] = i + 2
                ans += 1
                found = True
    print ans

if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve2():
    s = raw_input()
    s = s.replace('BC', 'X')
    ans = 0
    acc_A = 0
    for ele in s:
        if ele == 'A':
            acc_A += 1
        elif ele == 'X':
            ans += acc_A
        else:
            acc_A = 0
    print ans

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

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

c = [1]

def calc(x):
    for j in range(2, x):
        if x % j == 0:
            return
    c.append(x)
for i in range(2,min(n[0],n[1])+1):
    if n[0] % i == 0 and n[1] % i == 0:
        calc(i)

print(len(c))


### FIXED CODE ###

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

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

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

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

    return arr

d = gcd(n[0],n[1])

c = factorization(d)


print(len(c))