Harryxun/stf_run huggingface dataset:
def get():
    p,w = map(int, raw_input().split(","))
    for i in range(W-w,-1,-1):
        if bag[i] > 0 and bag[i]+p > bag[i+w]:
            bag[i+w] = bag[i]+p
    else:
        if p > bag[w]: bag[w] = p
    return
 
c = 1
while True:
    W = int(raw_input())
    if W == 0: break
    bag = [0]*(W+1)
    N = int(raw_input())
    for i in range(N): get()
    w_all = max(bag)
    money = bag.index(w_all)
    print "Case {}:\n{}\n{}".format(c,w_all,money)
    c += 1

### FIXED CODE ###

# coding: utf-8
# Here your code !
count = 1

while 1:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    data =[]
    dp = [[[-1,0]for i in range(W+1)]for i in range(N+1)]
    for i in range(N):
        data.append(input().split(","))

    for i in range(W+1):
        dp[N][i][0] = 0
    for i in reversed(range(N)):
        for capa in range(W+1):
            if int(data[i][1]) > capa:
                dp[i][capa][0] = dp[i+1][capa][0]
                dp[i][capa][1] = dp[i+1][capa][1]
            else:
                dp[i][capa][0] = max(int(data[i][0])+dp[i+1][capa-int(data[i][1])][0],dp[i+1][capa][0])
                dp[i][capa][1] = dp[i+1][capa][1]
                if dp[i][capa][0] != dp[i+1][capa][0]:
                    dp[i][capa][1] = int(data[i][1])+dp[i+1][capa-int(data[i][1])][1]
    print("Case " + str(count) +":")
    print(max(max(dp))[0])
    print(max(max(dp))[1])
 
    count += 1
n = list(input())

if n % 9 == 0:
    print('YES')
else:
    print('No')


### FIXED CODE ###

N = int(input())

if N % 9 == 0:
    print("Yes")
else:
    print("No")
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, Q = list(map(int, input().split()))
nodes = [[] for i in range(N)]
for i in range(N-1):
  r, e = list(map(int, input().split()))
  r, e = r - 1, e - 1
  nodes[r].append(e)
  nodes[e].append(r)
#print(nodes)

result = [0] * N
for i in range(Q):
  r, s = list(map(int, input().split()))
  result[r-1] += s

def dfs(r, prev=-1):
  for i in nodes[r]:
    if i == prev:
      continue
    result[i] += result[r]
    dfs(i, r)

if __name__ == "__main__":
  dfs(0)
  print(*result)


### FIXED CODE ###

#人の（ほぼ同じなのにうまくいかないので）
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
lines = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    lines[a-1].append(b-1)
    lines[b-1].append(a-1)
ans = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(v, parent):
    for u in lines[v]:
        if u != parent:
            ans[u] += ans[v]
            dfs(u, v)

dfs(0, -1)
print (*ans)
import math

n = int(input())
li = list(map(int,input().split()))
ans = 0

def gcd_list2(li):
    a = math.gcd(li[0],li[1])
    for i in range(n-1):
        a = math.gcd(a,li[i])
    return a

for i in range(n):
    li2 = li[:i] + li[i+1:]
    a = gcd_list2(li2)
    if a > ans:
        ans = a

print(ans)


### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0
lgcd = [0]*n
rgcd = [0]*n
lgcd[0] = li[0]
rgcd[-1] = li[-1]

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

for i in range(n-1):
    lgcd[i+1] = gcd(lgcd[i],li[i+1])
    rgcd[-i-2] = gcd(rgcd[-i-1],li[-(i+2)])

gcd_list = [gcd(lgcd[i],rgcd[i+2]) for i in range(n-2)]

gcd_list.append(lgcd[-2])
gcd_list.append(rgcd[1])

print(max(gcd_list))
N, A, B = input()

b_count = 0
for i in len(N):
  if i % (A+B) < A:
    b_count = b_count + 1
print(b_count)

### FIXED CODE ###

S = input()
N = int(S.split(' ')[0])
A = int(S.split(' ')[1])
B = int(S.split(' ')[2])
 
b_count = (N // (A+B)) * A
rem = N % (A+B)
b_count = b_count + min(rem, A)
print(b_count)
n=int(input())
print('ABC') if n<1200 elif n<2800 print('ARC') else print('AGC')

### FIXED CODE ###

n=int(input())
print('ABC') if n<1200 else print('ARC') if n<2800 else print('AGC')
import math
import copy
 
 
 
 
def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:
 
            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l
 

n=input()
s=input()

mod=1000000007
def help1(a):
    all=0
    a1=1

    
    b1=1
    while a!=0:
        a1=a1*a;
        a1=a1/b1;
        b1+=1
       
        a=a-1
        all=(all+a1)%mod
    return int(all)

def func():
    count=help1(len(s))
    dic={}

    for c in s:
        if c in dic:
            dic[c]=dic[c]+1
        else:
            dic[c]=1
    res=len(s)
    l=[]
    for k in dic:
        if dic[k]==1:
            l.append(k)
    for obj in l:
        del dic[obj]
        
    count2=1
    sum1=0
    for k in dic:
        sum1+=dic[k]
        count2=count2*(1+dic[k])



    number3=help1(sum1)-count2+1

    number4=help1(len(s)-sum1)+1

    number3=number3*number4
    return count-number3
  

print(func())


### FIXED CODE ###

import math
import copy
from collections import Counter
 
 
 
def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:
 
            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l
 

n=input()
s=input()

mod=7+10**9


def func():

    dic = Counter(s)
    ans = 1
    for x in dic:
        ans = ans*(dic[x]+1)%mod
    return ans-1
    
print(func())
n,q = map(int, input().split())
graph1 = [[] for _ in range(n+1)]
graph2 = [[] for _ in range(n+1)]
ans=[0]*(n+1)
reached=[0]*(n+1)
def main():
  for i in range(n-1):
    a,b = map(int, input().split())
    graph1[a].append(b)
    graph2[b].append(a)

  for i in range(q):
    p,x = map(int, input().split())
    ans[p] += x
  dfs(1) 
  print(' '.join([str(i) for i in ans[1:]]))

def dfs(i):
  if reached[i] == 1:
    return
  reached[i] = 1
  for g in graph1[i], graph2[i]:
    for j in g:
      if reached[j] == 1:
        continue
      ans[j] += ans[i]
      dfs(j)

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000000)
n,q = map(int, input().split())
graph1 = [[] for _ in range(n+1)]
graph2 = [[] for _ in range(n+1)]
ans=[0]*(n+1)
reached=[0]*(n+1)
def main():
  for i in range(n-1):
    a,b = map(int, input().split())
    graph1[a].append(b)
    graph2[b].append(a)

  for i in range(q):
    p,x = map(int, input().split())
    ans[p] += x
  dfs(1) 
  print(' '.join([str(i) for i in ans[1:]]))

def dfs(i):
  if reached[i] == 1:
    return
  reached[i] = 1
  for g in graph1[i], graph2[i]:
    for j in g:
      if reached[j] == 1:
        continue
      ans[j] += ans[i]
      dfs(j)

if __name__ == '__main__':
  main()
for i in range(Q):
    r = sys.stdin.readline().strip('\n')
    if r == '1':
        S = S[::-1]
    else:
        ni, f, c = r.split()
        if f=='1':
            S = c + S
        else:
            S+=c

print(S)

### FIXED CODE ###

import sys

S = input()

Q = int(input())
flag=0
mae = ''
matsu = ''

for i in range(Q):
    r = sys.stdin.readline().rstrip('\n')
    if r == '1':
        flag = 1 - flag
    else:
        ni, f, c = r.split()
        if f=='1':
            if flag == 0:
                mae += c
            else:
                matsu += c
        else:
            if flag == 0:
                matsu += c
            else:
                mae += c


if flag ==0:
    print(mae[::-1]+S+matsu)
else:
    print(matsu[::-1]+S[::-1]+mae)
S = list(input())
if len(S) == 4 and (S.count(S[1])) == 2  and len(set(s))==2:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

S = list(input())
if len(S) == 4 and (S.count(S[1])) == 2  and len(set(S))==2:
    print('Yes')
else:
    print('No')
i = 1
while True:
  x = int(input())
  if x: print("Case {}: {}".format(i, x)) else break
  i+=1


### FIXED CODE ###

i,x = 1,input()
while x != "0":
  print('Case '+str(i)+': '+x)
  i,x = i+1,input()
N=int(input())
V=sorted(list(map(int, input().split())), reverse=True)

result=V[0]
for i in range(1,N):
  result =(result + v[i])/2
print(result)


### FIXED CODE ###

n = int(input())
v = [int(e) for e in input().split()]
v.sort()
result = v[0]
for i in range(1, n):
  result = (result + v[i]) / 2
print(result)
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    prev_p = 1
    g = []
    while True:
        if g[:len(g)//2]==g[len(g)//2:] and len(g) > 0:
            break
        g.append(A[prev_p])
        prev_p = g[-1]  

    K = K % len(g)
    print(g[K-1])


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    prev_p = 1
    g = []
    seen = [0]*N
    i = 0
    while True:
        if seen[prev_p-1]:
            break
        seen[prev_p-1] = i
        g.append(A[prev_p-1])
        prev_p = g[-1]
        i += 1
    g_periodic = g[seen[prev_p-1]:]  
    g_before = g[:seen[prev_p-1]]

    if K <= len(g_before):
        print(g_before[K-1])
    else:
        K_new = (K - len(g_before)) % len(g_periodic)
        print(g_periodic[K_new-1])
if __name__ == '__main__':
    main()
x,y=map(int,input().split())
mod=10**9+7

a=(2*x-y)//3
b=(2*y-x)//3



if a!=(2*x-y)/3 or b!=(2*y-x)/3:
    print(0)
else:
    max=a+b+1
    fac=[0]*max
    finv=[0]*max
    inv=[0]*max

    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,max):
        fac[i]=fac[i-1]*i%mod
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        finv[i]=finv[i-1]*inv[i]%mod

    ans=fac[a+b]*(finv[a]*finv[b]%mod)%mod
    print(ans)

### FIXED CODE ###

x,y=map(int,input().split())
mod=10**9+7

a=(2*x-y)//3
b=(2*y-x)//3



if a!=(2*x-y)/3 or b!=(2*y-x)/3:
    print(0)
elif a<0 or b<0:
    print(0)
else:
    max=a+b+10
    fac=[0]*max
    finv=[0]*max
    inv=[0]*max

    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,max):
        fac[i]=fac[i-1]*i%mod
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        finv[i]=finv[i-1]*inv[i]%mod

    ans=fac[a+b]*(finv[a]*finv[b]%mod)%mod
    print(ans)
A, B = list(map(int, input().split()))
resutl = (A+B)/2 if (A+B)%2 == 0 else "IMPOSSIBLE"
print(result)

### FIXED CODE ###

A, B = list(map(int, input().split()))
result = (A+B)//2 if (A+B)%2 == 0 else "IMPOSSIBLE"
print(result)
# coding: utf-8
# hello worldと表示する
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

s=SI()
k=I()
n=len(s)
u=sorted(list(s))[0]
#print(s)
strs=[]
if n>=5:
    for i in range(n):
        if s[i]==u:
            for j in range(1,6):
                strs.append(s[i:i+j])
    #print(strs)
    #print(sorted(set(strs))[k-1])
else:
    for i in range(n):
        for j in range(i+1,n+1):
            #print(i,j)
            #print(s[i:j])
            strs.append(s[i:j])
#print(strs)
print(sorted(set(strs))[k-1])


### FIXED CODE ###

# coding: utf-8
# hello worldと表示する
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

s=SI()
k=I()
n=len(s)
strs=[]
for i in range(n):
    for j in range(1,k+1):
        strs.append(s[i:i+j])
print(sorted(list(set(strs)))[k-1])
n=int(input())
a=list(map(int,input().split()))
import sys
sum=0
cnt=0
# 奇数+
for i in range(n):
    z+=a[i]
    if i%2==0:
        if z<0:
            sum=z
        else:
            cnt+=(z+1)
            sum=-1
    else:
        if sum<=0:
            cnt+=(1-sum)
            sum=1
cnt_sbst=cnt
# 奇数-
for i in range(n):
    z+=a[i]
    if i%2==1:
        if sum>=0:
            cnt+=(z+1)
            sum=-1
    else:
        if sum<=0:
            cnt+=(1-z)
            sum=1
cnt_plus=cnt
ans=min(cnt_plus,cnt_sbst)
print(ans)




### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
sum=0
cnt=0
# 奇数+
for i in range(n):
    sum+=a[i]
    if i%2==0:
        if sum>=0:
            cnt+=(sum+1)
            sum=-1
    else:
        if sum<=0:
            cnt+=(1-sum)
            sum=1
cnt_sbst=cnt
# 奇数-
cnt=0
sum=0
for i in range(n):
    sum+=a[i]
    if i%2==1:
        if sum>=0:
            cnt+=(sum+1)
            sum=-1
    else:
        if sum<=0:
            cnt+=(1-sum)
            sum=1
cnt_plus=cnt
ans=min(cnt_plus,cnt_sbst)
print(ans)
from sys import stdin
from collections import deque, defaultdict as ddic
from itertools import combinations, permutations, product
import bisect
import heapq
from math import gcd
from operator import mul
import re


rs = lambda: stdin.readline().strip()
ri = lambda: int(rs())
rsl = lambda: stdin.readline().split()
rim = lambda: map(int, rsl())
ril = lambda: list(rim())


def findGCD(lst):
    ret = 1
    for i in range(len(lst)-1):
        ret = max(ret, gcd(lst[i], lst[i+1]))
    return ret


def findGCD2(lst, k):
    ret = 1
    for i in range(len(lst)-1):
        if i == k:
            continue
        ret = max(ret, gcd(lst[i], lst[i+1]))
    return ret



N = ri()
integers = list(rim())

lowest = [float('-inf'), float('-inf')]
for i in range(len(integers)-1):
    for j in range(i+1, len(integers)):
        temp = gcd(integers[i], integers[j])
        if temp > min(lowest):
            lowest[lowest.index(min(lowest))] = temp

print(max(lowest))

### FIXED CODE ###

from sys import stdin, exit
from fractions import gcd


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

# List if length of 2 or shorter
if len(A) <= 2:
    print(max(A))
    exit()

# Left Side = [A0, 0, 0, 0, 0]
left_side = [0 for _ in range(N)]
left_side[0] = A[0]

# Right Side = [0, 0, 0, 0, An]
right_side = [0 for _ in range(N)]
right_side[-1] = A[-1]

for i in range(N - 1):  # DP: L1 = gcd(L0, A1); Maximum GCD on very RIGHT of list  (Dir -->)
    left_side[i + 1] = gcd(left_side[i], A[i + 1])

for i in range(1, N):   # DP: Rn-2 = gcd(An-2, Rn-1); Maximum GCD on very LEFT of list  (Dir <--)
    right_side[-1 * (i+1)] = gcd(A[-1*(i+1)], right_side[-1*i])

max_gcd = 1

# Left
max_gcd = max(max_gcd, right_side[1])
# Max of Right and Left
max_gcd = max(max_gcd, left_side[-2])

for i in range(1, N - 1):
    left = left_side[i - 1]
    # We exclude the number at i here, and compare whether new gcd is greater than previous
    right = right_side[i + 1]

    max_gcd = max(max_gcd, gcd(left, right))

print(max_gcd)
import sympy
n,m = map(int,input().split())
l = m//n
a = list(sympy.divisors(m,generator=True))
c = 0
for i in range(1,len(a)):
    if a[i] > c and a[i] <= l:
        c = a[i]

print(c)

### FIXED CODE ###

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

def x():
    for i in range(l+1)[::-1]:
        if m % i == 0:
            return i
print(x())
N = int(input())
lis_h = list(map(int, input().split()))

for i in range(N,1,-1):
    if lis_h[i - 1] < lis_h[i - 2]:
        lis_h[i - 2] += -1
        if lis_h[i - 1] < lis_h[i - 2]:
            print("No")
            exit()
print("Yes")


### FIXED CODE ###

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

if lis[2] - (lis[0] - lis[1]) > 0:
    print(lis[2] - (lis[0] - lis[1]))
else:
    print(0)
n=int(input())
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=True
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    ans+=1
    if ans>1000:
    	flag=False
        semi=True
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  if not semi:
  	print(-1)
  else:
    print(499500)


### FIXED CODE ###

n=int(input())
import time
T=time.time()
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=False
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    if time.time()-T>1.5:
        flag=False
        semi=True
    ans+=1
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  if not semi:
    print(-1)
  if semi:
    print(499500)
input()
s = list(input())
print("".join(("*" if x != y else x for x in s[int(input())] for y in s )))

### FIXED CODE ###

import re
N = int(input())
S = input()
K = int(input())

w = S[K-1]
print(re.sub("[^#]", "*", S.replace(w, "#")).replace("#", w))
S=input()
N=len(S)
A=[int(i) for i in S]
B=["+" for i in range(N-1)]
output=S[0]
for i in range(2**N):
  for j in range(1,N):
    if (i>>j)&1:
      A[j]= -1*int(str(S[j]))
      B[j]=  "-"
  #print(A,B,sum(A))
  if sum(A) ==7:
    for i in range(1,N):
      output += B[i-1] + str(S[i])
    print(output+"=7")
    break


### FIXED CODE ###

S=input()
N=len(S)
A=[int(i) for i in S]
D=["+" for i in range(N-1)]
output=S[0]
for i in range(2**N):
  C=A
  B=D
  for j in range(N-1):
    if ((i>>j)&1):
      C[j+1]= -1*int(str(S[j+1]))
      B[j]=  "-"
    else:
      C[j+1]= int(str(S[j+1]))
      B[j]=  "+"
  #print(C,B,sum(C))
  if sum(C) ==7:
    for i in range(1,N):
      output += B[i-1] + str(S[i])
    print(output+"=7")
    break
import math
N,K=map(int,input().split())
sum=0
for i in range(1,N+1):
  if i>=K:
    sum=sum+(1/N)
  else:
    sum=sum+(1/N)*((1/2)**(math.ceil(math.log2(K/i)))
print(sum)

### FIXED CODE ###

import math
N,K=map(int,input().split())
sum=0
for i in range(1,N+1):
  if i>=K:
    sum=sum+(1/N)
  else:
    sum=sum+(1/N)*((1/2)**(math.ceil(math.log2(K/i))))
print(sum)
sa, sb, sc = [input() for i in range(3)]
sa, sb, sc = list(sa),list(sb),list(sc)

i = sa.pop(0)

while len(sa) != 0 and len(sb) != 0 and len(sb) != 0 : 
    if i =='a':
        i = sa.pop(0)
    if i =='b':
        i = sb.pop(0)
    if i =='c':
        i = sc.pop(0)

if len(sa) == 0:
    print('A')
elif len(sb) == 0:
    print('B')
elif  len(sc) == 0:
    print('C')

### FIXED CODE ###

# 入力
SA=list(input())
SB=list(input())
SC=list(input())

# 次に捨てる人（初期値は'A')
x='a'

while True:
  if x=='a':
    # リストの要素が0ならば終了する
    if len(SA)==0:
      print('A')
      exit()

    # 先頭要素を除去してxに代入
    x=SA[0]
    SA.remove(x)
  elif x=='b':
    # リストの要素が0ならば終了する
    if len(SB)==0:
      print('B')
      exit()

    # 先頭要素を除去してxに代入
    x=SB[0]
    SB.remove(x)
  else:
    # リストの要素が0ならば終了する
    if len(SC)==0:
      print('C')
      exit()

    # 先頭要素を除去してxに代入
    x=SC[0]
    SC.remove(x)
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
checked=[[0 for i in range(W)] for m in range(H)]

count=0
count2=0
for h1 in range(H):
    for w1 in range(W):
        if S[h1][w1]=="#" and checked[h1][w1]==0:
            checked[h1][w1]=1
            stack=deque([[h1,w1,"#"]])
            kuro=1
            siro=0
            count2+=1
            visited=set([h1*400+w1])
            print(stack)
            while stack:
                h,w,iro=stack.popleft()
                for y,x in [[-1,0],[1,0],[0,1],[0,-1]]:
                    Y,X=y+h,x+w
                    visitednum=Y*400+X
                    if 0<=Y<H and 0<=X<W and not visitednum in visited:
                        if iro=="#" and S[Y][X]==".":
                            siro+=1
                            visited.add(visitednum)
                            stack.append([Y,X,"."])
                        elif iro=="." and S[Y][X]=="#" and not visitednum in visited:
                            kuro+=1
                            visited[Y][X]=1
                            checked[Y][X]=1
                            visited.add(visitednum)
                            stack.append([Y,X,"#"])
            count+=kuro*siro
print(count)
print(count2)


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
checked=[[0 for i in range(W)] for m in range(H)]

count=0
count2=0
for h1 in range(H):
    for w1 in range(W):
        if S[h1][w1]=="#" and checked[h1][w1]==0:
            checked[h1][w1]=1
            stack=deque([[h1,w1,"#"]])
            kuro=1
            siro=0
            count2+=1
            visited=set([h1*400+w1])
            while stack:
                h,w,iro=stack.popleft()
                for y,x in [[-1,0],[1,0],[0,1],[0,-1]]:
                    Y,X=y+h,x+w
                    visitednum=Y*400+X
                    if 0<=Y<H and 0<=X<W and not visitednum in visited:
                        if iro=="#" and S[Y][X]==".":
                            siro+=1
                            visited.add(visitednum)
                            stack.append([Y,X,"."])
                        elif iro=="." and S[Y][X]=="#" and not visitednum in visited:
                            kuro+=1
                            checked[Y][X]=1
                            visited.add(visitednum)
                            stack.append([Y,X,"#"])
            count+=kuro*siro
print(count)