Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
class Cmb:
    def __init__(self, N, mod=10**9+7):
        self.fact = [1,1]
        self.fact_inv = [1,1]
        self.inv = [0,1]
        
        """ 階乗を保存する配列を作成 """
        for i in range(2, N+1):
            self.fact.append((self.fact[-1]*i) % mod)
            self.inv.append((-self.inv[mod%i] * (mod//i))%mod)
            self.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=10**9+7):
        if (r<0) or (n<r):
            return 0
        return self.fact[n] * self.fact_inv[n-r] % mod

from collections import deque
n,k = map(int,input().split())
mod = 10**9 + 7
es = [[] for _ in range(n+1)]
d = [0]*(n+1)
for _ in range(n-1):
    a,b = map(int,input().split())
    es[a].append(b)
    es[b].append(a)
    d[a] += 1
    d[b] += 1

root = -1
for i in range(1, n+1):
    if d[i] == 1:
        root = i
        break

num_child = [0]*(n+1)
que = deque([])
for c in es[root]:
    que.append((root, c))

while que:
    p,c = que.pop()
    num_child[p] += 1
    for nx in es[c]:
        if nx!=p:
            que.append((c, nx))

c = Cmb(N=n)
ans = k

for e,child in enumerate(num_child[1:]):
    if e+1==root:
        cand = k-1
    else:
        cand = k-2
    if child==0:
        continue
    else:
        ans = ans*(c(cand, child)) % mod
print(ans%mod)

Fixed submission:
class Cmb:
    def __init__(self, N, mod=10**9+7):
        self.fact = [1,1]
        self.fact_inv = [1,1]
        self.inv = [0,1]
        
        """ 階乗を保存する配列を作成 """
        for i in range(2, N+1):
            self.fact.append((self.fact[-1]*i) % mod)
            self.inv.append((-self.inv[mod%i] * (mod//i))%mod)
            self.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=10**9+7):
        if (r<0) or (n<r):
            return 0
        return self.fact[n] * self.fact_inv[n-r] % mod

from collections import deque
n,k = map(int,input().split())
mod = 10**9 + 7
es = [[] for _ in range(n+1)]
d = [0]*(n+1)
for _ in range(n-1):
    a,b = map(int,input().split())
    es[a].append(b)
    es[b].append(a)
    d[a] += 1
    d[b] += 1

root = -1
for i in range(1, n+1):
    if d[i] == 1:
        root = i
        break

num_child = [0]*(n+1)
que = deque([])
for c in es[root]:
    que.append((root, c))

while que:
    p,c = que.pop()
    num_child[p] += 1
    for nx in es[c]:
        if nx!=p:
            que.append((c, nx))

c = Cmb(N=k)
ans = k

for e,child in enumerate(num_child[1:]):
    if e+1==root:
        cand = k-1
    else:
        cand = k-2
    if child==0:
        continue
    else:
        ans = ans*(c(cand, child)) % mod

print(ans%mod)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n,m = map(int,input().split())
es = [[] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,input().split())
    es[u].append(v)
to = [[] for _ in range(n+1)]
for i in range(1, n+1):
    que = deque([])
    for j in es[i]:
        que.append((j, 1))
    while que:
        v,c = que.popleft()
        if c > 3:
            continue
        elif c==3:
            if v  not in to[i]:
                to[i].append(v)
        else:
            for j in es[v]:
                que.append((j, c+1))
s,t = map(int,input().split())
visited = [False]*(n+1)
que = deque([])
for st in to[s]:
    que.append((st, 1))
ans = -1
while que:
    v,c = que.popleft()
    if visited[v]:
        continue
    elif v==t:
        ans = c
        break
    else:
        visited[v] = True
        for nx in to[v]:
            que.append((nx,c+1))
print(ans)

Fixed submission:
n,m = map(int,input().split())
if m==0:
    print(-1)
    exit()
es = [[] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,input().split())
    es[u].append(v)
s,t = map(int,input().split())

INF = 10**9
dist = [[INF,INF,INF] for _ in range(n+1)]

d = 0
q = [s]

while q:
    d += 1
    r = d%3
    qq = []
    for u in q:
        for v in es[u]:
            if dist[v][r] == INF:
                dist[v][r] = d
                qq.append(v)
    q = qq

d = dist[t][0]
print(-1 if d==INF else d//3)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n,m = map(int,input().split())
es = [[] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,input().split())
    es[u].append(v)
to = [[] for _ in range(n+1)]
for i in range(1, n+1):
    que = deque([])
    for j in es[i]:
        que.append((j, 1))
    while que:
        v,c = que.popleft()
        if c > 3:
            continue
        elif c==3:
            if v  not in to[i]:
                to[i].append(v)
        else:
            for j in es[v]:
                que.append((j, c+1))
s,t = map(int,input().split())
visited = [False]*(n+1)
que = deque([])
for st in to[s]:
    que.append((st, 1))
ans = -1
while que:
    v,c = que.popleft()
    if visited[v]:
        continue
    elif v==t:
        ans = c
        break
    else:
        visited[v] = True
        for nx in to[v]:
            que.append((nx,c+1))
print(ans)

Fixed submission:
n,m = map(int,input().split())
if m==0:
    print(-1)
    exit()
es = [[] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,input().split())
    es[u].append(v)
s,t = map(int,input().split())

INF = 10**9
dist = [[INF,INF,INF] for _ in range(n+1)]

d = 0
q = [s]

while q:
    d += 1
    r = d%3
    qq = []
    for u in q:
        for v in es[u]:
            if dist[v][r] == INF:
                dist[v][r] = d
                qq.append(v)
    q = qq

d = dist[t][0]
print(-1 if d==INF else d//3)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,c,d = map(int,input().split())
cnt = 0
for i in range(a,b+1):
    if i%c==0 or i%d==0:
        cnt += 1
print(b+1-a-cnt)

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


def lcm(a, b):
    return a * b // gcd (a, b)

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

b_num = B//C + B//D - B//lcm(C, D)
a_num = (A-1)//C + (A-1)//D - (A-1)//lcm(C, D)

print((B-A+1) -(b_num - a_num))

Buggy python submission (verdict: Time Limit Exceeded):
a,b,c,d = map(int,input().split())
cnt = 0
for i in range(a,b+1):
    if i%c!=0 and i%d!=0:
        cnt += 1
print(cnt)

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


def lcm(a, b):
    return a * b // gcd (a, b)

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

b_num = B//C + B//D - B//lcm(C, D)
a_num = (A-1)//C + (A-1)//D - (A-1)//lcm(C, D)

print((B-A+1) -(b_num - a_num))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
lst = []
for i in range(n):
    x,y = map(int,input().split())
    lst.append([x,y])
lst.sort()
pmn = lst[0][0]
pmx = lst[-1][0]

lst.sort(key=lambda x:x[1])
qmn = lst[0][1]
qmx = lst[-1][1]

res = 0
for p in range(pmx+1 - pmn):
    for q in range(qmx+1 - qmn):
        cnt = 0
        for i in range(n):
            tmp_x, tmp_y = lst[i][0], lst[i][1]
            if ([p,q]!=[0,0]) and ([tmp_x+p, tmp_y+q] in lst):
                cnt += 1
        res = max(res, cnt)
print(n - res)

Fixed submission:
import itertools
from collections import Counter
n = int(input())
xy = [[int(x) for x in input().split()] for _ in range(n)]
vectors = []
for xy1, xy2 in itertools.combinations(xy,2):
    p = xy2[0] - xy1[0]
    q = xy2[1] - xy1[1]
    vectors.append((p, q))
    vectors.append((-p, -q))
c = Counter(vectors)
if n>=2:
    x = max(c.values())
    res = n - x
else:
    res = 1
print(res)
Buggy python submission (verdict: Runtime Error):
n = int(input())
lst = [int(i) for i in input().split()]
for i in range(n):
    s1=0
    for j in range(i):
        s1+=lst[j]
    s2=sum(lst)-s1
    if i==1:
        ans=abs(s1-s2)
    elif abs(s1-s2)<ans:
        ans=abs(s1-s2)
print(ans)

Fixed submission:
n = int(input())
lst = [int(i) for i in input().split()]
for i in range(n):
    s1=0
    for j in range(i):
        s1+=lst[j]
    s2=sum(lst)-s1
    if i==0:
        ans=abs(s1-s2)
    elif abs(s1-s2)<ans:
        ans=abs(s1-s2)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7
n,m = map(int,input().split())
lst = [int(input()) for _ in range(m)]
dp = [0]*(n+1)
for i in range(1,n+1):
    if i in lst:
        continue
    elif i==1:
        dp[i] = 1
    elif i==2:
        dp[i] = dp[1]+1
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
print(dp[n])

Fixed submission:
mod = 1000000007
N,M = list(map(int,input().split()))

b = [0]*(N+2)
b[0]=1

for i in range(M):
    b[int(input())] = -1

for i in range(N):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]
print(b[N]%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b,c,d = map(int,input().split())
s = input()
ng = '##'
if c < d:
    rt1 = s[a-1:c]
    rt2 = s[b-1:d]
    if (ng not in rt1) and (ng not in rt2):
        print('Yes')
    else:
        print('No')
else:
    rt2 = s[b-1:d]
    if ng in rt2:
        print('No')
    else:
        for i in range(b-1, d):
            if s[i] != '#':
                tmp_s = s[:i]+'#'+s[i+1:]
                rt1 = tmp_s[a-1:c]
                if ng not in rt1:
                    print('Yes')
                    exit()
        print('No')

Fixed submission:
n,a,b,c,d = map(int,input().split())
s = input()
ng = '##'
if c < d:
    if (ng in s[b-1:d]) or (ng in s[a-1:c]):
        print('No')
    else:
        print('Yes')
else:
    if ('...' not in s[b-2:d+1]):
        print('No')
    else:
        print('Yes')

Buggy python submission (verdict: Time Limit Exceeded):
n,a,b,c,d = map(int,input().split())
s = input()
ng = '##'
if c < d:
    rt1 = s[a-1:c]
    rt2 = s[b-1:d]
    if (ng not in rt1) and (ng not in rt2):
        print('Yes')
    else:
        print('No')
else:
    rt2 = s[b-1:d]
    if ng in rt2:
        print('No')
    else:
        for i in range(b-1, d):
            if s[i] != '#':
                tmp_s = s[:i]+'#'+s[i+1:]
                rt1 = tmp_s[a-1:c]
                if ng not in rt1:
                    print('Yes')
                    exit()
        print('No')

Fixed submission:
n,a,b,c,d = map(int,input().split())
s = input()
ng = '##'
if c < d:
    if (ng in s[b-1:d]) or (ng in s[a-1:c]):
        print('No')
    else:
        print('Yes')
else:
    if ('...' not in s[b-2:d+1]):
        print('No')
    else:
        print('Yes')
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
res = 0

for i in range(2**n):
    ptn = format(i, 'b').rjust(n, '0')
    light = True
    for j in range(m):
        tmp = 0
        for n in range(1, s[j][0]+1):
            if ptn[s[j][n] - 1] == '1':
                tmp += 1
        if tmp%2 != p[j]:
            light = False
    if light:
        res += 1
print(res)

Fixed submission:
N,M = map(int,input().split())
s = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0

for i in range(2**N):
    ptn = bin(i)[2:].rjust(N,'0')
    light = True
    for j in range(M):
        tmp = 0
        for n in range(1,s[j][0] + 1):
            if ptn[s[j][n]-1]=='1':
                tmp += 1
        if tmp % 2 != p[j] % 2:
            light = False
    if light:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
r,d,x = map(int,input().split())
for i in range(1,11):
  w = r*x - d
  x = w
  print(W)

Fixed submission:
r,d,x = map(int,input().split())
for i in range(1,11):
    w = r*x - d
    x=w
    print(w)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n,m = map(int,input().split())
lst = list(map(int,input().split()))
lst.sort()

for i in range(m):
    b,c = map(int,input().split())
    pos = bisect.bisect_left(lst,c)
    for j in range(min(b,pos)):
        lst[j] = c
    lst.sort()
print(sum(lst))

Fixed submission:
n,m = map(int,input().split())
l_a = sorted(list(map(int,input().split())))
l_bc = [list(map(int,input().split())) for _ in range(m)]
l_bc.sort(key = lambda x:x[1],reverse = True)
for b,c in l_bc:
    l_a.extend([c]*b)
    if len(l_a) > 2*n:
        break

l_a.sort(reverse = True)
print(sum(l_a[:n]))
Buggy python submission (verdict: Time Limit Exceeded):
r,g,b,n = map(int,input().split())
cnt = 0
for i in range(n//r + 1):
    for j in range(n//g + 1):
        t = n - i*r - j*g
        if t%b==0 and t//b>=0:
            cnt += 1
print(cnt)

Fixed submission:
r,g,b,n = map(int,input().split())
cnt = 0
for i in range(n//r + 1):
    for j in range(n//g + 1):
        t = n - i*r - j*g
        if t%b==0 and t//b>=0:
            cnt += 1
print(cnt)
Buggy python submission (verdict: Runtime Error):

n = int(input())
lst = [input() for _ in range(n)]

finA = 0
topB = 0
B2A = 0
cnt = 0

for l in lst:
    cnt += l.count('AB')
    if l[0]=='B' and l[-1]=='A':
        B2A += 1
    else:
        if l[0]=='B':
            topB += 1
        elif l[-1]=='A':
            finA += 1

if BtoA==0:
    cnt += min(finA, topB)
else:
    if finA==0 and topB==0:
        cnt += BtoA - 1
    else:
        cnt += BtoA + min(finA, topB)
print(cnt)

Fixed submission:
n = int(input())
lst = [input() for _ in range(n)]

finA = 0
topB = 0
BtoA = 0
cnt = 0
for l in lst:
    cnt += l.count('AB')
    if l[0]=='B' and l[-1]=='A':
        BtoA += 1
    else:
        if l[0]=='B':
            topB += 1
        elif l[-1]=='A':
            finA += 1

if BtoA==0:
    cnt += min(finA, topB)
else:
    if finA==0 and topB==0:
        cnt += BtoA - 1
    else:
        cnt += BtoA + min(finA, topB)
print(cnt)
Buggy python submission (verdict: Runtime Error):
import numpy as np
def divisor(n):
    tank = []
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            tank.append(i)
            if i!=n//i:
                tank.append(n//i)
    tank.sort()
    return tank

n = int(input())
tank = np.array(divisor(n))
print((tank-1).sum() - 1)

Fixed submission:

import numpy as np
def divisor(n):
    tank = []
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            tank.append(i)
            if i!=n//i:
                tank.append(n//i)
    tank.sort()
    return tank

n = int(input())
tank = np.array(divisor(n))
res = 0
for i in range(len(tank)):
    x = tank[i] - 1
    if x!=0 and n%x==n//x:
        res += x
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import fractions

n = int(input())
lst = [int(i) for i in input().split()]
gcd = []

for i in range(n):
    f = 0
    for j in range(n):
        if f==0 and j!=i:
            f = lst[j]
        elif j!=i:
            f = fractions.gcd(f,lst[j])
    gcd.append(f)
print(max(gcd))

Fixed submission:
import fractions
from functools import reduce

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

left = [0] * (n+1)
right = [0] * (n+1)

for i in range(n):
    left[i+1] = (fractions.gcd(left[i],a[i]))
    right[n-i-1] = (fractions.gcd(right[n-i],a[n-i-1]))

ans = 0
for i in range(n):
    ans = max(ans,fractions.gcd(left[i],right[i+1]))
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = input()
k = int(input())
c = s[k]
ans = ''
for i in range(n):
    if s[i] == c:
        ans += c
    else:
        ans += '*'
print(ans)

Fixed submission:
n = int(input())
s = input()
k = int(input())
c = s[k-1]
ans = ''
for i in range(n):
    if s[i] == c:
        ans += c
    else:
        ans += '*'
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

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 = [a + b for (a,b) in list(itertools.product(A,B))]
AB.sort(reverse = True)
ans = [ab + c for (ab,c) in list(itertools.product(AB[:min(3000,x*y*z)],C))]
ans.sort(reverse = True)
for i in range(k):
    print(ans[i])

Fixed submission:
import itertools

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 = [a + b for (a,b) in list(itertools.product(A,B))]
AB.sort(reverse = True)
ans = [ab + c for (ab,c) in list(itertools.product(AB[:min(3000,x*y*z)],C))]
ans.sort(reverse = True)
for i in range(k):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int,input().split())
s = input()
lst = []
ans = []
for i in range(n-1):
    if s[i:i+2] == 'AC':
        lst.append(i+1)

for i in range(q):
    cnt = 0
    l,r = map(int,input().split())
    for j in range(len(lst)):
        if l<=lst[j]<r:
            cnt += 1
    ans.append(cnt)

for i in range(q):
    print(ans[i])

Fixed submission:
from itertools import accumulate
n,q = list(map(int,input().split()))
s = input()
A = [list(map(int,input().split())) for i in range(q)]

flg = []
for i in range(n-1):
    tmp_s = s[i:i+2]
    if tmp_s == 'AC':
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))


for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int,input().split())
s = input()
ans = []
for i in range(q):
    l,r = map(int,input().split())
    cnt = 0
    for i in range(l,r):
        if s[i-1:i+1]=='AC':
            cnt += 1
    ans.append(cnt)
for j in range(q):
    print(ans[j])

Fixed submission:
from itertools import accumulate
n,q = list(map(int,input().split()))
s = input()
A = [list(map(int,input().split())) for i in range(q)]

flg = []
for i in range(n-1):
    tmp_s = s[i:i+2]
    if tmp_s == 'AC':
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))


for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int,input().split())
s = input()
ans = []
for i in range(q):
    l,r = map(int,input().split())
    txt = s[l-1:r]
    
    cnt = 0
    for j in range(len(txt)-1):
        if txt[j]=='A' and txt[j+1]=='C':
            cnt += 1
    ans.append(cnt)

for i in range(q):
    print(ans[i])

Fixed submission:
from itertools import accumulate
n,q = list(map(int,input().split()))
s = input()
A = [list(map(int,input().split())) for i in range(q)]

flg = []
for i in range(n-1):
    tmp_s = s[i:i+2]
    if tmp_s == 'AC':
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))


for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
visited = [[False]*w for _ in range(h)]

def dfs(y,x):
    visited[y][x] = True
    blk, wht = 0,0
    for dy,dx in zip((-1,1,0,0),(0,0,-1,1)):
        ny,nx = y+dy, x+dx
        if (not (0<=ny<h)) or (not (0<=nx<w)) or visited[ny][nx]:
            continue
        if s[y][x]!=s[ny][nx]:
            nb,nw = dfs(ny,nx)
            blk += nb
            wht += nw
    if s[y][x]=='#':
        blk += 1
    else:
        wht += 1
    return blk, wht

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            blk, wht = dfs(i,j)
            ans += blk*wht
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
visited = [[False]*w for _ in range(h)]

def dfs(y,x):
    visited[y][x] = True
    blk, wht = 0,0
    for dy,dx in zip((-1,1,0,0),(0,0,-1,1)):
        ny,nx = y+dy, x+dx
        if (not (0<=ny<h)) or (not (0<=nx<w)) or visited[ny][nx]:
            continue
        if s[y][x]!=s[ny][nx]:
            nb,nw = dfs(ny,nx)
            blk += nb
            wht += nw
    if s[y][x]=='#':
        blk += 1
    else:
        wht += 1
    return blk, wht

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            blk, wht = dfs(i,j)
            ans += blk*wht
print(ans)

Buggy python submission (verdict: Runtime Error):
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
visited = [[False]*w for _ in range(h)]

def dfs(y,x):
    visited[y][x] = True
    blk, wht = 0,0
    for dy,dx in zip((-1,1,0,0),(0,0,-1,1)):
        ny,nx = y+dy, x+dx
        if (not (0<=ny<h)) or (not (0<=nx<w)) or visited[ny][nx]:
            continue
        if s[y][x]!=s[ny][nx]:
            nb,nw = dfs(ny,nx)
            blk += nb
            wht += nw
    if s[y][x]=='#':
        blk += 1
    else:
        wht += 1
    return blk, wht

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            blk, wht = dfs(i,j)
            ans += blk*wht
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
h,w = map(int,input().split())
s = [list(input()) for _ in range(h)]
visited = [[False]*w for _ in range(h)]

def dfs(y,x):
    visited[y][x] = True
    blk, wht = 0,0
    for dy,dx in zip((-1,1,0,0),(0,0,-1,1)):
        ny,nx = y+dy, x+dx
        if (not (0<=ny<h)) or (not (0<=nx<w)) or visited[ny][nx]:
            continue
        if s[y][x]!=s[ny][nx]:
            nb,nw = dfs(ny,nx)
            blk += nb
            wht += nw
    if s[y][x]=='#':
        blk += 1
    else:
        wht += 1
    return blk, wht

ans = 0
for i in range(h):
    for j in range(w):
        if not visited[i][j]:
            blk, wht = dfs(i,j)
            ans += blk*wht
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
lst = list(map(int,input().split()))
dp = [float('inf')]*n
dp[0] = 0
for i in range(1, min(k, len(lst))):
    dp[i] = abs(lst[i] - lst[0])
for i in range(k, n):
    for j in range(1, k+1):
        dp[i] = min(dp[i], dp[i-j]+abs(lst[i]-lst[i-j]))
print(dp[-1])

Fixed submission:
n,k = map(int,input().split())
lst = list(map(int,input().split()))

dp = [float('inf')]*n
dp[0] = 0
for i in range(1, min(k, len(lst))):
    dp[i] = abs(lst[i] - lst[0])
for i in range(k, n):
    for j in range(1, k+1):
        dp[i] = min(dp[i], dp[i-j]+abs(lst[i]-lst[i-j]))
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
def knapsack_1(N, W, lst):
    #N : 品物数
    #W : 重みの総和
    #lst (wi,vi) : 商品iの重みwi、価値vi
    
    #dp[i][j] : i番目の品物から重さの総和がj以下になるように選んだ場合の価値の総和の最大値
    dp = [[0 for i in range(W+1)] for _ in range(N+1)]
    
    for i in range(N):
        for j in range(W+1):
            if j < lst[i][0]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j],dp[i][j - lst[i][0]] + lst[i][1])
    return dp[N][W]


n,w = map(int,input().split())
lst = []
for i in range(n):
    w_, v_ =  map(int,input().split())
    lst.append((w_, v_))
print(knapsack_1(n,w,lst))

Fixed submission:
n,w = map(int,input().split())

lstw, lstv = [], []
for i in range(n):
    w_,v_ = map(int,input().split())
    lstw.append(w_)
    lstv.append(v_)

dp = [[0 for i in range(w+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j < lstw[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-lstw[i]]+lstv[i])
print(dp[n][w])

Buggy python submission (verdict: Time Limit Exceeded):
n,w = map(int,input().split())

lstw, lstv = [], []
for i in range(n):
    w_,v_ = map(int,input().split())
    lstw.append(w_)
    lstv.append(v_)

#dp[i+1][j] := i番目までの商品で重さの総和がj以下の最大価値
dp = [[0 for i in range(w+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j < lstw[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-lstw[i]]+lstv[i])
print(dp[n][w])

Fixed submission:
n,w = map(int,input().split())

lstw, lstv = [], []
for i in range(n):
    w_,v_ = map(int,input().split())
    lstw.append(w_)
    lstv.append(v_)

dp = [[0 for i in range(w+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j < lstw[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-lstw[i]]+lstv[i])
print(dp[n][w])