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

from scipy.sparse.csgraph import dijkstra
import sys 
input = sys.stdin.readline

def solve():
  n = int(input())
  d = [[float("Inf")]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
  d = dijkstra(d)
  q,k = (int(i) for i in input().split())
  for i in range(q):
    res = 0
    x,y = (int(i) for i in input().split())
    res = d[x-1][k-1] + d[k-1][y-1]
    print(int(res))
solve()

### FIXED CODE ###


import sys 
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  d = [[]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1].append((b-1,c))
    d[b-1].append((a-1,c))
  q,k = (int(i) for i in input().split())
  #kからの距離を計算する
  d2 = [10**10]*n
  visit = [False]*n
  query = deque([(k-1,0)]) #始点、距離
  while query:
    place,dist = query.pop()
    if visit[place]:
      continue
    else:
      visit[place] = visit
      d2[place] = dist
      for i in range(len(d[place])):
        np,nc = d[place][i]
        if not visit[np]:
          query.append((np,nc+dist))
  for i in range(q):
    x,y = (int(i) for i in input().split())
    print(int(d2[x-1] + d2[y-1]))

solve()
### BUGGY CODE ###

inr = lambda: list(map(int, input().split()))
inn = lambda: input()

N,Q = inr()
S = inn()
for q in range(Q):
    l,r = inr()
    bubun = S[l-1:r]

    bbb = ""
    for b in bubun:
        if b in ["A","C"]:
            bbb += b
        
    print(bbb.count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
pref = [0]
for i in range(1,n):
  if s[i-1:i+1] == "AC": 
      pref.append(pref[-1]+1)
  else: 
      pref.append(pref[-1])
for i in range(q):
    l,r = map(int,input().split())
    print(pref[r-1]-pref[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

def main():
    N, M = map(int, input().split())
    C = []
    for i in range(M):
        a, b = map(int, input().split())
        p = min(a, b)
        q = max(a, b)
        C.append([p,q])
    D = get_unique_list(C)
    F = [1]*(N+1)
    for a, b in D:
        F[a] += 1
    ans = max(F)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return -self.parents[self.find(x)]

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return -self.parents[self.find(x)]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N+1)
    ans = 1
    if M == 0:
        print(ans)
        return

    for i in range(M):
        x, y = map(int, input().split())
        ans = max(uf.union(x,y), ans)
    print(ans)

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

K = int(input())

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b)

total = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            total += gcd(gcd(a,b),c)
print(total)


### FIXED CODE ###

K = int(input())

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a % b)

total = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            total += gcd(gcd(a,b),c)

            
print(total)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = []
    for _ in range(N):
        a = list(map(int, input().split()))
        q = collections.deque()
        for i in a:
            q.append(i)
        Q.append(q)
    days = 0
    while True:
        if all(len(q) == 0 for q in Q):
            break
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(len(Q)):
            if len(Q[i]) == 0 or gamed[i] != 0:
                continue
            game = False
            for j in range(i+1, len(Q)):
                if len(Q[j]) == 0 or gamed[j] != 0:
                    continue
                if Q[i][0] == j+1 and Q[j][0] == i+1:
                    Q[i].popleft()
                    Q[j].popleft()
#                    print("game:", j+1, i+1, days)
                    b = True
                    gamed[i] = 1
                    gamed[j] = 1
                    break
            if game:
                break
        days += 1
        if not b:
            print(-1)
            return
    print(days)
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

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

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0]*(N+1)
dp[0] = 1
for i in range(1, N+1):
  if i in a:
    continue
  if i > 1:
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
  else:
    dp[i] = dp[0] % 1000000007
print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0]*(N+1)
dp[0] = 1
for i in a:
  dp[i] = -1
for i in range(1, N+1):
  if dp[i] == -1:
    dp[i] = 0
    continue
  if i > 1:
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
  else:
    dp[i] = dp[0] % 1000000007
print(dp[N])
### BUGGY CODE ###

h,w = map(int,input().split())
a = ['#'*(w+2)]+['#'+input()+'#' for _ in range(h)]+['#'*(w+2)]
ans = 0
queue = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if a[i][j]=='#':
            queue.append([i,j])
while True:
    if queue == []:
        break
    l = []
    for _ in range(len(queue)):
        q = queue.pop()
        if q[0]>1 and a[q[0]-1][q[1]]=='.':
            l.append([q[0]-1,q[1]])
        if q[1]>1 and a[q[0]][q[1]-1]=='.':
            l.append([q[0],q[1]-1])
        if q[0]<h and a[q[0]+1][q[1]]=='.':
            l.append([q[0]+1,q[1]])
        if q[1]<w and a[q[0]][q[1]+1]=='.':
            l.append([q[0],q[1]+1])
        a[q[0]-1] = a[q[0]-1][:q[1]]+'#'+a[q[0]-1][q[1]+1:]
        a[q[0]] = a[q[0]][:q[1]-1]+'###'+a[q[0]][q[1]+2:]
        a[q[0]+1] = a[q[0]+1][:q[1]]+'#'+a[q[0]+1][q[1]+1:]
    queue = l
    ans += 1
print(ans-1)

### FIXED CODE ###

h,w = map(int,input().split())
a = [input() for _ in range(h)]
ans = 0
queue = []
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            queue.append([i,j])
from collections import deque
queue = deque(queue)
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
dp = [[10**4]*w for _ in range(h)]
for i,j in queue:
    dp[i][j] = 0
while len(queue):
    y,x = queue.popleft()
    d = dp[y][x]
    for dx,dy in dxy:
        nx, ny = x+dx, y+dy
        if not 0<=nx<=w-1:
            continue
        elif not 0<=ny<=h-1:
            continue
        elif dp[ny][nx]<=d+1:
            continue
        dp[ny][nx] = d+1
        queue.append((ny,nx))
print(max([max(dp[row]) for row in range(h)]))
### 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)





#各Bの下に置けるCの数を保存
Bcounter = [0]*N

for i in range(N):
    Bcounter[i] = N - bts(C,B[i]+1,0)

for i in range(1,N):
    Bcounter[i] = Bcounter[i-1] + Bcounter[i]
Bcounter=[0]+Bcounter


res = 0
for i in range(N):
    a = A[i]
    #a以上で最小のb
    minb = bts(B,a+1)
    #本来なら、最小のb以降のBを一つ一つ足し上げていく
    res += Bcounter[-1] - Bcounter[minb]

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 ###

s=list(input())

right = [0]

left = [0]

count = 0
for i in range(len(s)):
    if s[i] == '<':
        count += 1
    else:
        count = 0
    right.append(count)
count = 0
for i in range(len(s)-1,-1,-1):
    if s[i] == '>':
        count += 1
    else:
        count = 0
    left.insert(0,count)

ans = 0

for i in range(len(s)+1):
    ans += max(right[i],left[i])
print(ans)


### FIXED CODE ###

s=list(input())

right = [0]

left = [0]

count = 0
for i in range(len(s)):
    if s[i] == '<':
        count += 1
    else:
        count = 0
    right.append(count)
count = 0
for i in range(len(s)-1,-1,-1):
    if s[i] == '>':
        count += 1
    else:
        count = 0
    left.append(count)
left.reverse()

ans = 0

for i in range(len(s)+1):
    ans += max(right[i],left[i])
print(ans)
### BUGGY CODE ###

k = int(input())
#k = 3

class GCD:
    def __init__(self):
        self.cache = {}
        self.cache3 = {}
    def gcd2(self, a, b):
        a, b = sorted([a, b], reverse=True)
        if (a in self.cache and b in self.cache[a]):
            return self.cache[a][b]
        if (a % b == 0):
            if (a not in self.cache):
                self.cache[a] = {}
            self.cache[a][b] = b
            return b
        return self.gcd2(b, a % b)
    def gcd3(self, a, b, c):
        a, b, c = sorted([a, b, c], reverse=True)
        if (a in self.cache3 and b in self.cache3[a] and c in self.cache3[a][b]):
            return self.cache3[a][b][c]
        if (a not in self.cache3):
            self.cache3[a] = {}
        if (b not in self.cache3[a]):
            self.cache3[a][b] = {}
        result = self.gcd2(self.gcd2(a, b), c)
        self.cache3[a][b][c] = result
        return result

a = 1
b = 1
c = 1
result = 0
client = GCD()
while (a <= k):
    b = 1
    while (b <= k):
        c = 1
        while (c <= k):
            result += client.gcd3(a, b, c)
            c += 1
        b += 1
    a += 1
print(result)


### FIXED CODE ###

k = int(input())
#k = 200

class GCD:
    def __init__(self):
        self.cache = {}
        self.cache3 = {}
    def gcd2(self, a, b):
        a, b = sorted([a, b], reverse=True)
        if (a in self.cache and b in self.cache[a]):
            return self.cache[a][b]
        if (a % b == 0):
            if (a not in self.cache):
                self.cache[a] = {}
            self.cache[a][b] = b
            return b
        return self.gcd2(b, a % b)
    def gcd3(self, a, b, c):
        a, b, c = sorted([a, b, c], reverse=True)
        if (a in self.cache3 and b in self.cache3[a] and c in self.cache3[a][b]):
            return self.cache3[a][b][c]
        if (a not in self.cache3):
            self.cache3[a] = {}
        if (b not in self.cache3[a]):
            self.cache3[a][b] = {}
        result = self.gcd2(self.gcd2(a, c), b)
        self.cache3[a][b][c] = result
        return result

a = 1
b = 1
c = 1
result = 0
client = GCD()
while (a <= k):
    b = a
    while (b <= k):
        interval = client.gcd2(a, b)
        c = b
        while (c <= k):
            if (a == b and b == c):
                result += client.gcd2(interval, c)
            elif(a != b and b != c and a != c):
                result += client.gcd2(interval, c) * 6
            else:
                result += client.gcd2(interval, c) * 3
            c += 1
        b += 1
    a += 1
print(result)
### BUGGY CODE ###

n=int(input())
a=2
while True:
  if a<=n:
    a*=2

print(a/2)

### FIXED CODE ###

n=int(input())
a=1
while True:
  if a<=n:
    a*=2
  else:
    break

print(a//2)
### BUGGY CODE ###

# 参考URL
# https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


N, K, L = map(int, input().split())

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for _ in range(K):
    a, b = map(int, input().split())
    uf_road.union(a-1, b-1)
    
for _ in range(L):
    a, b = map(int, input().split())
    uf_train.union(a-1, b-1)

ans = []
for i in range(N):
    links = set(uf_road.members(i)) & set(uf_train.members(i))
    ans.append(len(links))
    
print(' '.join(map(str, ans)))

### FIXED CODE ###

# 参考URL
# https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]


N, K, L = map(int, input().split())

uf_road = UnionFind(N)
uf_train = UnionFind(N)

for _ in range(K):
    a, b = map(int, input().split())
    uf_road.union(a-1, b-1)
    
for _ in range(L):
    a, b = map(int, input().split())
    uf_train.union(a-1, b-1)

from collections import defaultdict

d = defaultdict(int)
for i in range(N):
    d[(uf_road.find(i), uf_train.find(i))]+=1
    
ans = []
for i in range(N):
    ans.append(d[(uf_road.find(i), uf_train.find(i))])

print(' '.join(map(str, ans)))
### BUGGY CODE ###

import sys
input=sys.stdin.readline


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

edge=[[] for _ in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    u-=1;v-=1
    edge[u].append(v)

res=[0]*n

def solve(p,x):
    que=[p]
    while que:
        p=que.pop()
        res[p]+=x
        for e in edge[p]:
            que.append(e)
    return


for i in range(q):
    p,x=map(int,input().split())
    p-=1
    solve(p,x)

print(*res)

### FIXED CODE ###

import sys
from collections import deque
def main():
    input=sys.stdin.readline
    n,q=map(int,input().split())

    edge=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1;v-=1
        edge[u].append(v)
   
    cost=[0]*n
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        cost[p]+=x

    for idx,e in enumerate(cost):
        if e==0:continue
        for f in edge[idx]:
            cost[f]+=e

    print(*cost)

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

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ab_total_list = []
total_list = []

for i in A:
    for j in B:
        ab_total_list.append(i+j)
for i in ab_total_list:
    for j in C:
        total_list.append(i+j)
total_list.sort()
total_list.reverse()
for i in range(0, K):
    print(total_list[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ab_total_list = []
total_list = []

A.sort()
A.reverse()
if len(A) > K:
    A = A[0:K+1]

B.sort()
B.reverse()
if len(B) > K:
    B = B[0:K+1]

C.sort()
C.reverse()
if len(C) > K:
    C = C[0:K+1]

ab_total_list = []
for i in A:
    for j in B:
        ab_total_list.append(i+j)

ab_total_list.sort()
ab_total_list.reverse()
if len(ab_total_list) > K:
    ab_total_list = ab_total_list[0:K+1]

for i in range(0, K):
    for j in range(0, int(K/(i+1))):
        if j >= len(C) or i >= len(ab_total_list):
            break
        total = ab_total_list[i] + C[j]
        total_list.append(total)
        if (i*j) > K:
            break

total_list.sort()
total_list.reverse()
for i in range(0, K):
    print(total_list[i])
### BUGGY CODE ###

#!/usr/bin/env python3

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


a = [0]
b = [0]

for i in range(N):
    a.append(a[-1] + A[i])


for i in range(M):
    b.append(b[-1] + B[i])

ret = 0
for i in range(N+1):
    for j in range(M+1):
        if a[i] + b[j] <= K:
            ret = max(i+j, ret)
        else:
            break

print(ret)


### FIXED CODE ###

#!/usr/bin/env python3

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


a = [0]
b = [0]

for i in range(N):
    a.append(a[-1] + A[i])


for i in range(M):
    b.append(b[-1] + B[i])

ret = 0
j = M
for i in range(N+1):
    if a[i] > K:
        break
    while a[i] + b[j] > K:
        j -= 1

    ret = max(i+j, ret)


print(ret)
### BUGGY CODE ###

#coding:utf-8
x, y = map(int, input().split())

mod = 10**9 + 7
f = [1]
for i in range(10**6):
    f.append(f[-1] * (i+1) % mod)
    
def nCr(n, r):
    return f[n] * pow(f[r], f[r] ** (mod-2), mod) * pow(f[n-r] ** (mod-2), mod) % mod

def main():
    if (x + y) % 3 != 0 or (x + y) // 3 < abs(x - y):
        print(0)
        return

    n = (x + y) // 3
    r = n - abs(x - y)
    print(nCr(n, r))
    return
    
main()

### FIXED CODE ###

#coding:utf-8
x, y = map(int, input().split())

mod = 10**9 + 7
f = [1]
for i in range(10**6):
    f.append(f[-1] * (i+1) % mod)
    
def nCr(n, r):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def main():
    if (x + y) % 3 != 0 or (x + y) // 3 < abs(x - y):
        print(0)
        return
    
    n = (x + y) // 3
    r = n // 2 - abs(x-y) // 2
    print(nCr(n, r))
    return
    
main()
### BUGGY CODE ###

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

data = [[] for _ in range(3*N)]

for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    data[3*u].append(3*v+1)
    data[3*u+1].append(3*v+2)
    data[3*u+2].append(3*v)

S,T = map(int,input().split())
S -= 1
T -= 1

inf = 10**6
stack = [[3*S,0]]
time = [inf] * (3*N)

while stack:
    x = stack.pop()
    for y in data[x[0]]:
        if time[y] > x[1] + 1:
            time[y] = x[1] + 1
            stack.append([y,x[1] + 1])

if time[3*T] == inf:
    print(-1)
else:
    print(time[3*T]//3)

### FIXED CODE ###

from collections import deque

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

data = [[] for _ in range(3*N)]

for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    data[3*u].append(3*v+1)
    data[3*u+1].append(3*v+2)
    data[3*u+2].append(3*v)

S,T = map(int,input().split())
S -= 1
T -= 1

inf = 10**6
stack = deque([[3*S,0]])
time = [inf] * (3*N)

while stack:
    x = stack.popleft()
    for y in data[x[0]]:
        if time[y] > x[1] + 1:
            time[y] = x[1] + 1
            stack.append([y,x[1] + 1])

if time[3*T] == inf:
    print(-1)
else:
    print(time[3*T]//3)
### BUGGY CODE ###

import math
n = int(input())
c_t = 0
c_a = 0
for i in range(n):
    t, a = [int(x) for x in input().split(" ")]
    #print(min(c_t / t, c_a / a))
    init = int(math.ceil(max(min(c_t / t, c_a / a), 1)))
    for j in range(init,10**18):
        if t*j >= c_t and a*j >= c_a:
            c_t = t*j
            c_a = a*j
            #print("->" + str(j))
            break
print(c_t + c_a)


### FIXED CODE ###

import math
n = int(input())
c_t = 0
c_a = 0
for i in range(n):
    t, a = [int(x) for x in input().split(" ")]
    #print(min(c_t / t, c_a / a))
    init = int(max(c_t // t, c_a // a, 1))
    for j in range(init,10**18):
        if t*j >= c_t and a*j >= c_a:
            c_t = t*j
            c_a = a*j
            #print("->" + str(j))
            break
print(c_t + c_a)
### BUGGY CODE ###

# div2019C - AB Substrings
from itertools import permutations


def main():
    N = int(input())
    S = tuple(input().rstrip() for _ in range(N))
    ans = 0
    for perm in permutations(S, N):
        x = "".join(perm)
        ans = max(ans, x.count("AB"))
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# div2019C - AB Substrings
def main():
    N, *S = open(0).read().split()
    ans, ab, start_b, end_a = 0, 0, 0, 0
    for s in S:
        if s[0] == "B" and s[-1] == "A":
            ab += 1
        elif s[0] == "B":
            start_b += 1
        elif s[-1] == "A":
            end_a += 1
        ans += s.count("AB")
    if start_b + end_a == 0:
        ans += max(0, ab - 1)
    else:
        ans += ab + min(start_b, end_a)
    print(ans)


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

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

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
mod=10**9+7
      
def cmb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

print( ((2 ** n -1) - cmb(n, a, mod) - cmb(n, b, mod)) %mod)

### FIXED CODE ###

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

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
mod=10**9+7
      
def cmb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

print( ((2 ** n -1) - cmb(n, a, mod) - cmb(n, b, mod)) %mod)