Harryxun/stf_run huggingface dataset:
import copy
h, w, k = map(int, input().split())
hw = []
mas = []
mas_su = 0

for i in range(h):
    hwi = input()
    masi = []
    for j in range(w):
        if hwi[j] == "#":
            masi.append(1)
        else:
            masi.append(0)

    mas_su += sum(masi)
    mas.append(masi)

l = 2**(h+w)
ans = 0

for i in range(l):
    test = copy.deepcopy(mas)
    num = 0
    for j in range(h+w):
        if ((i >> j) & 1):
            if j < h:
                for p in range(w):
                    if test[j][p]==1:
                        test[j][p] = 0
                        num += 1
            else:
                for p in range(h):
                    if test[p][j-w]==1:
                        test[p][j-w] = 0
                        num += 1
    if mas_su-num == k:
        ans += 1

print(ans)

### FIXED CODE ###

import copy
h, w, k = map(int, input().split())
hw = []
mas = []
mas_su = 0

for i in range(h):
    hwi = input()
    masi = []
    for j in range(w):
        if hwi[j] == "#":
            masi.append(1)
        else:
            masi.append(0)

    mas_su += sum(masi)
    mas.append(masi)

l = 2**(h+w)
ans = 0

for i in range(l):
    test = copy.deepcopy(mas)
    num = 0
    for j in range(h+w):
        if ((i >> j) & 1):
            if j < h:
                for p in range(w):
                    if test[j][p]==1:
                        test[j][p] = 0
                        num += 1
            else:
                for p in range(h):
                    if test[p][j-h]==1:
                        test[p][j-h] = 0
                        num += 1
    if mas_su-num == k:
        ans += 1

print(ans)
N = int(input())
li = list(map(int,input().split()))
li2 = []
key =[0] #key ０でおｋ　１で1下げ
cnt = 0
flg = True
if N == 1:
    ans ="Yes"
    flg = False
while flg :
    cur1 = li[cnt]
    cur2 = li[cnt+1]
    sa = cur2 - cur1
    if key[cnt] == 0:
        if sa < -1:
            ans = "No"
            flg = False
        elif sa == -1:
            key.append(1)
        else:
            key.append(0)
    else:
        if sa < 0:
            ans = "No"
            flg = False
        else:
            key.append(0)
    if cnt == len(li)-1:
        ans = "Yes"
        flg = False
    cnt += 1
print(ans)

### FIXED CODE ###

N = int(input())
li = list(map(int,input().split()))
li2 = []
key =[0] #key ０でおｋ　１で1下げ
cnt = 0
flg = True
if N == 1:
    ans ="Yes"
    flg = False
while flg :
    cur1 = li[cnt]
    cur2 = li[cnt+1]
    sa = cur2 - cur1
    if key[cnt] == 0:
        if sa < -1:
            ans = "No"
            flg = False
        elif sa == -1:
            key.append(1)
            cnt += 1
        else:
            key.append(0)
            cnt += 1
    else:
        if sa < 0:
            ans = "No"
            flg = False
        elif sa == 0:
            key.append(1)
            cnt += 1
        else:
            key.append(0)
            cnt += 1
    if cnt == len(li)-1:
        ans = "Yes"
        flg = False
print(ans)
n, m = map(int,input().split())
a = [0] * n
b = [0] * n
for i in range(0,n):
    a[i], b[i] = map(int,input().split())

dict = {}
for i in range(0,n):
    dict[a[i]] = b[i]
    
for j in range(0,n-1):
    l = sorted(a)
    if l[j] == l[j-1]:
        dic[l[j]] = dic[l[j]]+dic[l[j-1]]
        dic[l[j-1]] = 0
        l[j-1] = -j

#print(l)
#print(dict)

ex = 0
num = 0

for i in range(0,n):
    #print(l[i])
    if num + dict[l[i]] <= m:
        ex = ex + l[i] * dict[l[i]]
        num = num + dict[l[i]]
    else:
        ex = ex + l[i] * (m - num)
        num = m
    #print([ex,num])
    if num == m:
        break

print(ex)





### FIXED CODE ###

##### C 再チャレンジ

##以下、二次元配列を、各リストの最初の要素でソートするアルゴリズム

def two_dim_merge_sort(arr):#＃arrは二次元配列
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = two_dim_merge_sort(left)
    right = two_dim_merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return two_dim_merge(left, right)


def two_dim_merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i][0] <= right[r_i][0]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

##ここまで

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

l = [0]*n

for i in range(0,n):
    l[i] = list(map(int,input().split()))

s = two_dim_merge_sort(l)

num = 0
ex = 0

for i in range(0,n):
    if num + s[i][1] <= m:
        ex = ex + s[i][0] * s[i][1]
        num = num + s[i][1]
    else:
        ex = ex + s[i][0] * (m-num)
        num = m
    if num == m:
        break
        
print(ex)
a, b, c = [int(input()) for_in range(3)]
if (a == b != c) or (b == c != a) or (c == a != b):
  print(2)
elif (a == b == c):
  print(1)
else:
  print(3)

### FIXED CODE ###

color = list(map(int,input().split()))
print(len(set(color)))
import itertools

def chkTrg(a,b,c):
    if (a + b > c and b + c > a and c + a > b) and (a != b and b != c and c != a):
        return True
    else:
        return False

N = int(input())
bars = [int(i) for i in input().split(" ")]

cnt = 0

for bar in itertools.combinations(bars, 3):
    if chkTrg(bar[0],bar[1],bar[2]):
        cnt += 1

print(cnt)import itertools

def chkTrg(a,b,c):
    if (a + b > c and b + c > a and c + a > b) and (a != b and b != c and c != a):
        return True
    else:
        return False

N = int(input())
bars = [int(i) for i in input().split(" ")]

cnt = 0

for bar in itertools.combinations(bars, 3):
    if chkTrg(bar[0],bar[1],bar[2]):
        cnt += 1

print(cnt)

### FIXED CODE ###

import itertools

def chkTrg(a,b,c):
    if (a + b > c and b + c > a and c + a > b) and (a != b and b != c and c != a):
        return True
    else:
        return False

N = int(input())
bars = [int(i) for i in input().split(" ")]

cnt = 0

for bar in itertools.combinations(bars, 3):
    if chkTrg(bar[0],bar[1],bar[2]):
        cnt += 1

print(cnt)
x = int(input())
if x == 0:
  pirnt("1")
else:
  print("0")

### FIXED CODE ###

x = int(input())
if x == 0:
  print("1")
else:
  print("0")
A,B,C,D = input().split()
count = 0
start = int(A)
finish = int(B)
ite = 100
for i in range(ite):
  if i == ite-1:
    nums = list(range(start *i, finish ))
  else:
    nums = list(range(start *i, start*(i+1) ))
  tmp = [x for x in nums if not x%int(C) == 0 and not x%int(D) == 0]
  count += len(tmp)
print(count)


### FIXED CODE ###

import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
A,B,C,D = input().split()
A = int(A)-1
s = lcm(int(C),int(D))
#s = int(C)*int(D)
#numac = int(A)//int(C)#10//6 = 1
#numad = int(A)//int(D)#10//8 = 1
#numacd = int(A)//s#10//24 = 0
numa = int(A)//int(C) + int(A)//int(D) - int(A)//s
#numa = 1
#numbc = int(B)//int(C)#40//6 = 6
#numbd = int(B)//int(D)#40//8 = 5
#numbcd = int(B)//s#40//24= 1
numb = int(B)//int(C) + int(B)//int(D) - int(B)//s
#numb = 1
print(int(B)-int(A)-(numb - numa))
def merge(A, left, mid, right):
	global count
	n1 = mid - left
	n2 = right - mid
	L=[]
	R=[]
	for i in range(n1-1):
		L[i] = append(A[left + i])
	for i in range(n2-1):
		R[i] =append(A[mid + i])
	L[n1] = 10e10
	R[n2] = 10e10
	i = 0
	j = 0
	for k in range(left , right-1):
		if L[i] <= R[j]:
			A[k] = L[i]
			i = i + 1
		else: 
 			A[k] = R[j]
 			j =	 j + 1

def mergeSort(A, left, right):
	if left+1 < right:
		mid = (left + right)//2
		mergeSort(A, left, mid)
		mergeSort(A, mid, right)
		merge(A, left, mid, right)
n = int(input())
A = list(map(int, input().split()))
count = 0
mergeSort(A, 0, len(A))
print(*A)
print(count)



### FIXED CODE ###

def merge(A, left, mid, right):
	global count
	n1 = mid - left
	n2 = right - mid
	L=[]
	R=[]
	
#	for i in range(n1):
#		L.append(A[left + i])
#	for i in range(n2):
#		R.append(A[mid + i])
	L=A[left:mid]
	R=A[mid:right]

	L.append(10e10)
	R.append(10e10)
	i = 0
	j = 0
	for k in range(left , right):
		count +=1
		if L[i] <= R[j]:
			A[k] = L[i]
			i = i + 1
		else: 
 			A[k] = R[j]
 			j =	 j + 1

def mergeSort(A, left, right):
	if left+1 < right:
		mid = (left + right)//2
		mergeSort(A, left, mid)
		mergeSort(A, mid, right)
		merge(A, left, mid, right)
		
n = int(input())
A = list(map(int, input().split()))
count = 0
mergeSort(A, 0, n)
print(*A)
print(count)
n = int(input())
a_list = list(map(int, input().split()))
dic = {}
i_list = []
for a in a_list:
    dic[a] = 0
for a in a_list:
    dic[a] += 1
    if dic[a] = 1:
        i_list.append(a)
ans = 0
for i in i_list:
    p = dic[i] - i 
    if p >= 0:
        ans += p
    else:
        ans += dic[i]
print(ans)

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
dic = {}
i_list = []
for a in a_list:
    dic[a] = 0
for a in a_list:
    dic[a] += 1
    if dic[a] == 1:
        i_list.append(a)
ans = 0
for i in i_list:
    p = dic[i] - i 
    if p >= 0:
        ans += p
    else:
        ans += dic[i]
print(ans)
s = input().split()
A = s[0]
B = s[1]
C = s[2]
D = s[3]
k = 0
for i in range(A,B+1):
  if i%C != 0 and i%D != 0:
    k = k + 1
print(k)

### FIXED CODE ###

s = input().split()
s = list(map(int,s))
A = s[0]
B = s[1]
C = s[2]
D = s[3]
if A%C > 0:
  i = B//C - A//C
else:
  i = B//C - A//C + 1
if A%D > 0:
  j = B//D - A//D
else:
  j = B//D - A//D + 1
from fractions import gcd
p = (C*D)//(gcd(C,D))
if A%p > 0:
  k = B//p - A//p
else:
  k = B//p - A//p + 1
print(B-A+1-(i + j - k))
N, K = map(int, input().split())
X = list(map(int, input().split()))
L = [0] + [x for x in X if x < 0][::-1]
R = [0] + [x for x in X if x >= 0]

ans = float("inf")
for i in range(K-len(R)+1, len(L)):
    if K - i < 0:
        continue

    ans = min(ans, abs(L[i]) * 2 + R[K-i])
print(ans)


### FIXED CODE ###

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

ans = float('inf')
for i in range(N-K+1):
    ans = min(ans, abs(X[i] - X[i+K-1]) + abs(X[i]))
    ans = min(ans, abs(X[i] - X[i+K-1]) + abs(X[i+K-1]))

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

A = A.sort()
b = set(A)
b = list(b)
a = [i for i in b if A.count(i) >= 2]

if len(a) <= 1:
    print(0)
else:
    a = set(a)
    a = list(a)
    a.reverse()
    print(a[0]*a[1])


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ch = [0]*2
i = 0
j = 2
ans = 1
a.sort()
a = a[::-1]
while True:
    if a[i] == a[i+1]:
        ch[0] = a[i]
        break
    else:
        i += 1
    if i == n-1:
        ans = 0
        break

while True:
    if ans == 0:
        break
    if a[i+j] == a[i+j+1]:
        ch[1] = a[i+j]
        break
    else:
        j += 1
    if i+j == n-1:
        ans = 0

if ans == 0:
    print(0)
else:
    print(ch[0]*ch[1])
N = int(input())
list = []
list = input().split()

M = 1

for i in range(1, N):
　　k = list[i]
　　t_list = list[0:i+1]
　　a_list = sorted(t_list, reverse=True)
　　if a_list[0] == k:
　　　　M += 1
print(M)

### FIXED CODE ###

N = int(input())
list = input().split()
ans = 0
maxHeight = -1
for i in range(N):
  if int(list[i]) >= maxHeight:
    ans += 1
    maxHeight = int(list[i])
print(ans)
#coding:utf-8
import itertools
import numpy as np

N,M = map(int,input().split())
cakeList = [list(map(int,input().split())) for i in range(N)]
cakeList = np.array(cakeList)
numList = [i for i in range(N)]


maxv = 0
if M < N/2:
    combi = list(itertools.combinations(numList,M))
    for indexs in combi:
        cakes = [cakeList[i] for i in indexs]
        cakes = np.array(cakes)
        total = [abs(np.sum(cakes[:,i])) for i in range(3)]
        total = sum(total)
        maxv = max(total,maxv)
    print(maxv)


else:
    M = N - M
    combi = list(itertools.combinations(numList,M))
    BDP = [np.sum(cakeList[:,i]) for i in range(3)]
    for indexs in combi:
        cakes = [cakeList[i] for i in indexs]
        cakes = np.array(cakes)
        total = [abs(BDP[i] - np.sum(cakes[:,i])) for i in range(3)]
        total = sum(total)
        maxv = max(maxv,total)
    print(maxv)


### FIXED CODE ###

#coding:utf-8
A,B = map(int, input().split())

if A <= 8 and B <= 8:
    print("Yay!")

else:
    print(":(")
s = input()
for k in range(len(s)//2-1, 0, -1)
  if s[:k] == s[k:2*k]: break
print(k)

### FIXED CODE ###

s = input()
for k in range(len(s)//2-1, 0, -1):
  if s[:k] == s[k:2*k]: break
print(k*2)
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())))
D = []
E = []
for i in range(x):
  for j in range(y):
    D.append(A[i]+B[j])
D.sort()
for i in range(z):
  for j in range(min(len(D),k)):
    E.append(C[i]+D[::-1][j])
print("\n".join(map(str,sorted(E)[::-1][:k])))


### FIXED CODE ###

import math
n = int(input())
l = [int(input()) for i in range(5)]
print(math.ceil(n/min(l))+4)
import math
a,b = map(int,input().split())
c = math.gcd(a,b)
print(int((a*b)/c))

### FIXED CODE ###

def gcd(a,b):
    return a if (b==0) else gcd(b,a%b)
a,b = map(int,input().split())
print(int((a*b)/gcd(a,b)))
def get_sieve_of_eratosthenes(x):
    data = [True] * (x + 1)
    data[0] = data[1] = False
    i = 2
    while i ** 2 <= x:
        if data[i]:
            for j in range(i + 1, x + 1):
                if j % i == 0:
                    data[j] = False
        i += 1
    return data


pn = get_sieve_of_eratosthenes(1000)
n = int(input())
cnt = 0
for i in range(n):
    a = int(input())
    if pn[a]:
        cnt += 1
print(cnt)



### FIXED CODE ###

import math


def isprime(x):
    for i in range(2,int(math.sqrt(x)) + 1):
        if x % i == 0:
            return 0
    return 1


n = int(input())
cnt = 0
for i in range(n):
    x = int(input())
    if isprime(x):
        cnt += 1
print(cnt)
i=0
while True:
    Indata = int(input())
    if Indata == 0:
        break
    else:
        i=i+1
        print("Case" +str(i) + ": " + str(Indata)


### FIXED CODE ###

i=0
while True:
    Indata = int(input())
    if Indata == 0:
        break
    else:
        i=i+1
        print("Case " +str(i) + ": " + str(Indata))
# 初期入力
#import numpy as np
import sys
input = sys.stdin.readline
N,M = (int(i) for i in input().split())
A = list(map(int, input().split()))
#A =np.array(A,dtype=np.int64)
take =[[-1] for i in range(M)]
for x in range(M):
    B,C = (int(i) for i in input().split())
    take[x] =B,C

#
A.sort()
take.sort(key=lambda x: x[1], reverse=True)
take =[(0,0)] +take
ind =[0]*(M+1)
for i in range(1,M+1): #初項に「０」足したから「M]まで
    ind[i] =ind[i-1] +take[i][0]
    if A[ind[i-1]] >take[i][1]:
        break
    for j in range(ind[i-1],ind[i]):
        if A[j] <take[i][1]:
            A[j] =take[i][1]
        else:
            break
    #A[ind[i-1]:ind[i]] =np.where(A[ind[i-1]:ind[i]] < take[i][1] ,take[i][1],A[ind[i-1]:ind[i]])
print(sum(A))

### FIXED CODE ###

# 初期入力
#import numpy as np
import sys
input = sys.stdin.readline
N,M = (int(i) for i in input().split())
A = list(map(int, input().split()))
take =[[-1] for i in range(M)]
for x in range(M):
    B,C = (int(i) for i in input().split())
    take[x] =B,C

#
A.sort()
take.sort(key=lambda x: x[1], reverse=True)
take =[(0,0)] +take
ind =[0]*(M+1)
for i in range(1,M+1): #初項に「０」足したから「M]まで
    ind[i] =ind[i-1] +take[i][0]
    if ind[i-1] >=N:
        break
    elif A[ind[i-1]] >=take[i][1]:
        break
    elif ind[i] <N and A[ind[i]] <take[i][1]: #全て一括で置き換える
        A[ind[i-1] :ind[i]] =[take[i][1] ] *(take[i][0]) 
    else:
        for j in range(ind[i-1],ind[i]): #最後は1つずつ確認しながら置き換える
            if N <= j:
                break
            if A[j] <take[i][1]:
                A[j] =take[i][1]
            else:
                break
print(sum(A))
import sys
input=sys.stdin.readline
d=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split()))for _ in range(d)]
t=[int(input())for _ in range(d)]
m=int(input())
dq=[list(map(int,input().split()))for _ in range(m)]
x=[[0]for _ in range(26)]
ans=0
for i in range(d):
  v=t[i]-1
  ans+=s[i][v]-c[v]*(i-x[v][-1]+1)*(i-x[v][-1])//2
  x[v].append(i+1)
for i in range(26):
  ans-=c[i]*(d+1-x[i][-1])*(d-x[i][-1])//2
  x[i].append(d+1)
print(ans)

### FIXED CODE ###

d=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split()))for _ in range(d)]
t=[int(input())-1 for _ in range(d)]
x=[0]*26
ans=0
for i in range(d):
  v=t[i]
  ans+=s[i][v]
  for j in range(26):
    if j==v:x[j]=0
    else:x[j]+=1
    ans-=c[j]*x[j]
  print(ans)
A,B = map(int,input().split())

p = A+B
m = A-B
M = A*B

L = []

L.append(p)
L.append(m)
L.append(M)

print(max(M))

### FIXED CODE ###

A,B = map(int,input().split())

p = A+B
m = A-B
M = A*B

L = []

L.append(p)
L.append(m)
L.append(M)

print(max(L))
A=int(input())
B=int(input())
C=A + B

if  A % 3 == 0 or B % 3 == 0 or C % 3 == 0:
 print("Possible")
else:
 print("Impossible")


### FIXED CODE ###

a,b=map(int,input().split())
c=a + b
 
if  a%3==0 or b%3==0 or c%3==0: print("Possible")
else: print("Impossible")
N = int(input())
s = []
for i in range(N):
    s.append(input())

M = int(input())
t = []
for i in range(M):
    t.append(input())

#print(s)
#print(t)
max_score = 0

for e in s:
    score = s.count(e) - t.count(e)
    if score > max_score:
        max_score = score

print(max_score)


### FIXED CODE ###

v =  [int(i) for i in input().split()]

if v[0] + v[1] >= v[2]:
    print("Yes")
else:
    print("No")
A B K = map(int,input().split())
d = []
m = 0
for i in range(1,101):
    if A % i == 0 and B % i == 0:
        d.append(i)
m = d[K-1]
print(m)

### FIXED CODE ###

A,B,K=map(int,input().split())
L=[]
for i in range(1,101):
  if A%(i)==0 and B%(i)==0 :
    L.append(i)
L.sort(reverse=True)
print(L[K-1])
s = input()
x, y = map(int, input().split())

MoveX, MoveY = [], []
dir = "X"
count = 0
for i in range(len(s)): 
    if s[i] == "T":
        if count:
            if dir == "X": MoveX.append(count)
            else: MoveY.append(count)
        count = 0
        dir = ("Y" if dir == "X" else "X")      
    else:
        count += 1
if s[-1] == "F":
    if dir == "X": MoveX.append(count)
    else: MoveY.append(count)

def DP(i, z, Move = list, memo = {}):
    if i == -1: 
        if z == 0: return True
        else: return False
    try:
        return memo[(i, z)]
    except KeyError:
        if DP(i-1, z-Move[i], Move, memo) or DP(i-1, z+Move[i], Move, memo): 
            memo[(i, z)] = True
            return True
        else: 
            memo[(i, z)] = False
            return False

memox, memoy = {}, {}
if DP(len(MoveX)-1, x, MoveX, memox) and DP(len(MoveY)-1, y, MoveY, memoy): print("Yes")
else: print("No")

### FIXED CODE ###

s = input()
x, y = map(int, input().split())

MoveX, MoveY = [], []
dir = "X"
count = 0
for i in range(len(s)): 
    if s[i] == "T":
        if count:
            if dir == "X": MoveX.append(count)
            else: MoveY.append(count)
        count = 0
        dir = ("Y" if dir == "X" else "X")      
    else:
        count += 1
if s[-1] == "F":
    if dir == "X": MoveX.append(count)
    else: MoveY.append(count)

iniX = 0
if s[0] == "F":
    iniX = MoveX.pop(0)

def DP(i, z, ini, Move = list):
    canMove = set([ini])
    for j in range(i):
        temp = []
        for item in canMove:
            temp.append(item+Move[j])
            temp.append(item-Move[j])
        canMove = set(temp)
    return z in canMove

if DP(len(MoveX), x, iniX, MoveX) and DP(len(MoveY), y, 0, MoveY): print("Yes")
else: print("No")
#python3
import sys
sys.setrecursionlimit(2000)

def main():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        tree[a].append(b)
    op = []
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        op.append((p, x))
    
    cntr = [0 for _ in range(n)]
    
    def dfs(node, p):
        lng = len(tree[node])
        cntr[node] += p
        if lng == 0:
            return
        for i in range(lng):
            next_node = tree[node][i]
            dfs(next_node, p)

    for node, p in op:
        dfs(node, p)
    for i in range(n):
        if i == n-1:
            print(cntr[i])
        else:
            print(cntr[i], end=' ')
main()


### FIXED CODE ###

#python3
from collections import deque 
def main():
    n, q = map(int, input().split())
    to = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        to[a].append(b)
        to[b].append(a)

    node = [0 for _ in range(n)]

    for _ in range(q):
        p, x = map(int, input().split())
        node[p-1] += x

    dq = deque() 
    dq.append(0)
    done = [0 for _ in range(n)]
    done[0] = 1
    while len(dq) > 0:
        x = dq.popleft()
        for i in to[x]:
            if done[i] == 1:
                continue
            node[i] += node[x]
            done[i] = 1 
            dq.append(i)

    for i in range(n):
        print(node[i]) if i == n-1 else print(node[i], end=' ')
main()
m={"A":list(input()),"B":list(input()),"C":list(input())}

t="A"
for i in range(100):
  if (len(m["A"]) == 0 and t == "A") or (len(m["C"]) == 0 and t == "B") or (len(m["C"]) == 0 and t == "C"):
    ans = t
    break
  c=m[t][0]
  for s in "ABC":
    if m[s][0] == c:
      m[s].pop(0)
  
  t=c.upper()
  
  
print(ans)

### FIXED CODE ###

m={"a":list(input()),"b":list(input()),"c":list(input())}

t="a"
while True:
  if len(m[t]) > 0:
    t = m[t].pop(0)
  else:
    print(t.upper())
    break
n, m = tuple(map(int, raw_input().split()))
x = sorted(list(map(int, raw_input().split())))
y = [tuple(map(int, raw_input().split())) for i in range(m)]
for b,c in y:
  while x[b-1] > c:
    b -= 1
  x[0:b] = [c]*b
  x.sort()
print(sum(x))


### FIXED CODE ###

n, m = tuple(map(int, raw_input().split()))
x = sorted(list(map(int, raw_input().split())))
y = [list(map(int, raw_input().split())) for i in range(m)]
y.sort(key = lambda x: x[1], reverse=True)
y_pos = 0
for index, value in enumerate(x):
  b = y[y_pos][0]
  c = y[y_pos][1]
  if value < c:
	  x[index] = c
	  y[y_pos][0] = b-1
	  if b == 1:
		  y_pos += 1
		  if y_pos == len(y):
			  break
  else:
	  break

print(sum(x))
n,k = map(str, input().split())
li = list(map(str, input().split()))
Li = list(n)
while len(set(Li)&set(li)):
  n = int(n)+1
  Li = list(str(n))
else: print("".join(Li))

### FIXED CODE ###

a,b,c = map(int, input().split())
if a==b and b<c: print("YES")
elif b==c and c<a: print("YES")
elif c==a and a<b: print("YES")
else: print("NO")
import sys
sys.setrecursionlimit(10**7)
a,b,n = map(int, input().split())

def num(x):
    return (a*x)//b - a*(x//b)

ma = num(1)

for i in range(2, n+1):
    if num(i) > ma:
        ma = num(i)
    else:
        if num(i) >= num(i-1):
        print(ma)
        exit()
print(ma)

### FIXED CODE ###

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

x =  min(b-1, n)
print(int(a*x/b) - a*int(x/b))