Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
A, B = map(int, input().split())
a = []
b = []
for i in range(1, A**(1/2)+1):
    if A % i == 0:
        a.append(i)
        a.append(A//i)
for i in range(1, B**(1/2)+1):
    if B % i == 0:
        a.append(i)
        a.append(B//i)

ans = 0
for i in a:
    for j in b:
        if gcd(i, j) == 1:
            ans += 1
print(ans)

Fixed submission:
A, B = map(int, input().split())
a = []
b = []
import random

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True


for i in range(1, int(A**(1/2))+1):
    if A % i == 0:
        a.append(i)
        a.append(A//i)
for i in range(1, int(B**(1/2))+1):
    if B % i == 0:
        b.append(i)
        b.append(B//i)

a = set(a)
b = set(b)
a = a & b

ans = 0
for i in a:
    if is_prime(i):
        ans += 1
print(ans+1)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())

cost = []
open = []
for i in range(m):
    a, b = map(int, input().split())
    c = set(list(map(int, input().split())))
    cost.append(a)
    open.append(c)

dp = [10**7] * (2**n)
dp[0] = 0
for i in range(m):
    key = []
    for j in range(1, n+1):
        if j in open[i]:
            key.append("1")
        else:
            key.append("0")
    key = "".join(key)
    key = int(key, 2)
    for j in range(2**n):
        next = j | key
        dp[next] = min(dp[next], dp[j] + cost[i])

if dp[2**n-1] == 10**7:
    print(-1)
else:
    print(dp[2**n-1])


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

cost = []
open = []
for i in range(m):
    a, b = map(int, input().split())
    c = set(list(map(int, input().split())))
    cost.append(a)
    open.append(c)

dp = [10**7] * (2**n)
dp[0] = 0
for i in range(m):
    key = []
    for j in range(1, n+1):
        if j in open[i]:
            key.append("1")
        else:
            key.append("0")
    key = "".join(key)
    key = int(key, 2)
    for j in range(2**n):
        next = j | key
        dp[next] = min(dp[next], dp[j] + cost[i])

if dp[2**n-1] == 10**7:
    print(-1)
else:
    print(dp[2**n-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ans = 0
for i in range(N):
    ans += i

print(ans)


Fixed submission:
N = int(input())
print(N*(N-1)//2)
Buggy python submission (verdict: Runtime Error):
from bisect import *
N = int(input())
S = input()

swapleft = []
swapright = []

for i in range(N):
    if S[i] == "B":
        if (i+1) % 2 == 0:
            swapright.append(i+1)
    else:
        if (i+1) % 2 == 1:
            swapright.append(i+1)

for i in range(N, 2*N):
    if S[i] == "B":
        if (i+1) % 2 == 1:
            swapleft.append(i+1)
    else:
        if (i+1) % 2 == 0:
            swapleft.append(i+1)

swapleft = set(swapleft)
swapright = set(swapright)

swapleft |= set([i for i in range(1, N+1)]) - swapright
swapright = set([i for i in range(1, 2*N+1)]) - swapleft
swapleft = list(swapleft)
swapleft.sort(reverse = True)
lmax = max(swapleft)
swapright = list(swapright)
swapright.sort()

ans = 1

for i in range(N):
    ans *= (N - bisect_left(swapright, swapleft[i]) - i)
    ans %= 1000000007


for i in range(1, N+1):
    ans *= i
    ans %= 1000000007

print(ans)


Fixed submission:
from bisect import *
N = int(input())
S = input()

swapleft = []
swapright = []

for i in range(N):
    if S[i] == "B":
        if (i+1) % 2 == 0:
            swapright.append(i+1)
    else:
        if (i+1) % 2 == 1:
            swapright.append(i+1)

for i in range(N, 2*N):
    if S[i] == "B":
        if (i+1) % 2 == 1:
            swapleft.append(i+1)
    else:
        if (i+1) % 2 == 0:
            swapleft.append(i+1)


swapleft = set(swapleft)
swapright = set(swapright)

if len(swapleft) > len(swapright):
    swapleft |= set([i for i in range(1, N+1)]) - swapright
    swapright = set([i for i in range(1, 2*N+1)]) - swapleft

else:
    swapright |= set([i for i in range(N+1, 2*N+1)]) - swapleft
    swapleft = set([i for i in range(1, 2*N+1)]) - swapright

if len(swapright) != len(swapleft):
    print(0)
else:

    swapleft = list(swapleft)

    swapleft.sort(reverse = True)
    swapright = list(swapright)
    swapright.sort()

    ans = 1

    for i in range(N):
        ans *= (N - bisect_left(swapright, swapleft[i]) - i)
        ans %= 1000000007


    for i in range(1, N+1):
        ans *= i
        ans %= 1000000007

    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
dp = [[0 for i in range(13)] for j in range(len(s)+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(len(s)):
    if s[i] == "?":
        for j in range(13):
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j]
                dp[i+1][(j*10+k)%13] %= mod
    else:
        for j in range(13):
            k = int(s[i])
            dp[i+1][(j*10+k)%13] += dp[i][j]
            dp[i+1][(j*10+k)%13] %= mod

print(dp[len(s)][5])


Fixed submission:
s = input()
dp = [[0 for i in range(13)] for j in range(len(s)+1)]
dp[0][0] = 1
mod = 10**9+7
for i in range(len(s)):
    if s[i] == "?":
        for j in range(13):
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j]
                dp[i+1][(j*10+k)%13] %= mod
    else:
        for j in range(13):
            k = int(s[i])
            dp[i+1][(j*10+k)%13] += dp[i][j]
            dp[i+1][(j*10+k)%13] %= mod

print(dp[len(s)][5])
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353
n = 10**6
g1 = [1, 1]
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans = cmb(M*3+N-1, N-1, mod)
for i in range(M*2+1, M*3+1):
    ans -= cmb(M*3-i+(N-1)-1, N-2, mod) * N - mod*mod
    ans = (ans+mod)%mod

for i in range(M+1, min(N, 3*M)+1):
    if (3*M - i) % 2 == 0:
        two = (3*M - i) // 2
        ans -= cmb(two+N-1, N-1, mod) * cmb(N, i, mod) - mod*mod
        ans = (ans+mod)%mod
print(ans)


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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353
n = 10**6*3
g1 = [1, 1]
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans = cmb(M*3+N-1, N-1, mod)
for i in range(M*2+1, M*3+1):
    ans -= cmb(M*3-i+(N-1)-1, N-2, mod) * N - mod*mod
    ans = (ans+mod)%mod

for i in range(M+1, min(N, 3*M)+1):
    if (3*M - i) % 2 == 0:
        two = (3*M - i) // 2
        ans -= cmb(two+N-1, N-1, mod) * cmb(N, i, mod) - mod*mod
        ans = (ans+mod)%mod
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
anslist = []

for i in range(1,n-1):
  if a[i] < 0:
    anslist.append([a[-1], a[i]])
    a[-1] -= a[i]
  else:
    anslist.append([a[0], a[i]])
    a[0] -= a[i]
anslist.append([a[-1], a[0]])
ans = a[-1]-a[0]
print(ans)
for i in range(len(anslist)):
  print(anslist[i][0], anslist[i][1])
    
  
      


Fixed submission:
n,k=map(int,input().split())
if k == 1:
  print(0)
else:
  print(n-k)
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(input())

light = [[None for i in range(W)] for j in range(H)]

for i in range(H):
    j = 0
    count = 0
    before = 0
    while j <= W-1:
        if grid[i][j] == ".":
            count += 1
        else:
            for k in range(before, j):
                light[i][k] = count
            light[i][j] = 0
            before = j+1
            count = 0
        j += 1
    else:
        if count >= 0:
            for k in range(before, j):
                light[i][k] = count

light2 = [[None for i in range(W)] for j in range(H)]

for i in range(W):
    j = 0
    count = 0
    before = 0
    while j <= H-1:
        if grid[j][i] == ".":
            count += 1
        else:
            for k in range(before, j):
                light2[k][i] = count
            light2[j][i] = 0
            before = j+1
            count = 0
        j += 1
    else:
        if count >= 0:
            for k in range(before, j):
                light2[k][i] = count

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, light[i][j] + light2[i][j])
print(ans-1)


Fixed submission:
H, W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(input())

light = [[None for i in range(W)] for j in range(H)]

for i in range(H):
    j = 0
    count = 0
    before = 0
    while j <= W-1:
        if grid[i][j] == ".":
            count += 1
        else:
            for k in range(before, j):
                light[i][k] = count
            light[i][j] = 0
            before = j+1
            count = 0
        j += 1
    else:
        if count >= 0:
            for k in range(before, j):
                light[i][k] = count

light2 = [[None for i in range(W)] for j in range(H)]

for i in range(W):
    j = 0
    count = 0
    before = 0
    while j <= H-1:
        if grid[j][i] == ".":
            count += 1
        else:
            for k in range(before, j):
                light2[k][i] = count
            light2[j][i] = 0
            before = j+1
            count = 0
        j += 1
    else:
        if count >= 0:
            for k in range(before, j):
                light2[k][i] = count

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, light[i][j] + light2[i][j])
print(ans-1)
Buggy python submission (verdict: Time Limit Exceeded):
L = input()
ans = 0
n = len(L)
def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        x %= 1000000007
        n //= 2

    return K * x
count = 0
for i in range(len(L)):
    if i == 0:
        ans += (pow(3,n-1) + 2) % 1000000007
        count += 1
    else:
        if L[i] == "1":
            ans += (pow(3,n-1)+1)%1000000007*(pow(2,count)%1000000007)
            count += 1
    n -= 1
print(ans%1000000007)


Fixed submission:
L = input()
ans = 0
n = len(L)
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

count = 0
for i in range(len(L)):
    if i == 0:
        ans += (power_func(3,n-1,1000000007) + 2)
        ans %= 1000000007
        count += 1
    else:
        if L[i] == "1":
            ans += (power_func(3,n-1,1000000007)+1)*(power_func(2,count,1000000007))
            ans %= 1000000007
            count += 1
    n -= 1
print(ans%1000000007)

Buggy python submission (verdict: Time Limit Exceeded):
L = input()
ans = 0
n = len(L)
def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x
count = 0
for i in range(len(L)):
    if i == 0:
        ans += (pow(3,n-1) + 2) % 1000000007
        count += 1
    else:
        if L[i] == "1":
            ans += (pow(3,n-1)+1)%1000000007*(pow(2,count)%1000000007)
            count += 1
    n -= 1
print(ans%1000000007)


Fixed submission:
L = input()
ans = 0
n = len(L)
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

count = 0
for i in range(len(L)):
    if i == 0:
        ans += (power_func(3,n-1,1000000007) + 2)
        ans %= 1000000007
        count += 1
    else:
        if L[i] == "1":
            ans += (power_func(3,n-1,1000000007)+1)*(power_func(2,count,1000000007))
            ans %= 1000000007
            count += 1
    n -= 1
print(ans%1000000007)

Buggy python submission (verdict: Time Limit Exceeded):
L = input()
ans = 0
n = len(L)
count = 0
for i in range(len(L)):
    if i == 0:
        ans += (3**(n-1) + 2) % 1000000007
        count += 1
    else:
        if L[i] == "1":
            ans += ((3**(n-1)+1)%1000000007*(2**count%1000000007))
            count += 1
    n -= 1
print(ans%1000000007)


Fixed submission:
L = input()
ans = 0
n = len(L)
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

count = 0
for i in range(len(L)):
    if i == 0:
        ans += (power_func(3,n-1,1000000007) + 2)
        ans %= 1000000007
        count += 1
    else:
        if L[i] == "1":
            ans += (power_func(3,n-1,1000000007)+1)*(power_func(2,count,1000000007))
            ans %= 1000000007
            count += 1
    n -= 1
print(ans%1000000007)
Buggy python submission (verdict: Time Limit Exceeded):

import bisect
import sys

N, Q = map(int, input().split())
kouzi = []
for _ in range(N):
    S, T, X = map(int, input().split())
    kouzi.append([X, S, T-1])
kouzi.sort(reverse = True)

human = [int(input()) for _ in range(Q)]
ans = [-1]*(Q+1)


N0 = 2**(Q-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 2**31-1)

def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]
t = 0
for task in kouzi:
    t += 1
    x = task[0]
    l = bisect.bisect_left(human, task[1]-x)
    r = bisect.bisect_right(human, task[2]-x)
    if l == r:
        continue
    update(l, r, (t, x))

for i in range(Q):
    q = query(i)
    if q == 2147483647:
        print(-1)
    else:
        print(q)


Fixed submission:
import bisect
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
kouzi = []
for _ in range(N):
    S, T, X = map(int, input().split())
    kouzi.append([X, S, T-1])
kouzi.sort(reverse = True)

human = [int(input()) for _ in range(Q)]
ans = [-1]*(Q+1)


N0 = 2**(Q-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 2**31-1)

def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]
t = 0
for task in kouzi:
    t += 1
    x = task[0]
    l = bisect.bisect_left(human, task[1]-x)
    r = bisect.bisect_right(human, task[2]-x)
    if l == r:
        continue
    update(l, r, (t, x))

for i in range(Q):
    q = query(i)
    if q == 2147483647:
        print(-1)
    else:
        print(q)
Buggy python submission (verdict: Runtime Error):
S = input()
if 1 <= S[:1] <= 12 and 1 <= S[2:] <= 12:
  print("AMBIGUOUS")
elif 1 <= S[:1] <= 12:
  print("MMYY")
elif 1 <= S[2:] <= 12:
  print("YYMM")
else:
  print("NA")

Fixed submission:
S = input()
if 1 <= int(S[:2]) <= 12 and 1 <= int(S[2:]) <= 12:
  print("AMBIGUOUS")
elif 1 <= int(S[:2]) <= 12:
  print("MMYY")
elif 1 <= int(S[2:]) <= 12:
  print("YYMM")
else:
  print("NA")
Buggy python submission (verdict: Runtime Error):
from math import gcd
N = int(input())
a = list(map(int, input().split()))

if N > 2:
    a.sort()
    diff = []
    for i in range(N-1):
        diff.append(a[i+1]-a[i])
    index = diff.index(min(diff))
    diff_ = diff[:]
    if index > 0:
        plus = diff[index-1] + diff[index]
        diff_[index-1] = plus
        diff_[index] = plus
    GCD = diff_[0]

    for i in range(N-1):
        GCD = gcd(diff_[i], GCD)

    if index < N-1:
        plus = diff[index] + diff[index+1]
        diff[index] = plus
        diff[index+1] = plus
    GCD2 = diff[0]
    for i in range(N-1):
        GCD2 = gcd(diff[i], GCD2)
    print(max(GCD, GCD2))
else:
    print(max(a))


Fixed submission:
from fractions import gcd
N = int(input())
a = list(map(int, input().split()))
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0+1)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        if data[2*k+1] == INF:
            data[k] = data[2*k+2]
        elif data[2*k+2] == INF:
            data[k] = data[2*k+1]
        else:
            data[k] = gcd(data[2*k+1], data[2*k+2])

for i in range(N):
    update(i, a[i])

ans = 0
for i in range(N):
    update(i, INF)
    ans = max(ans, data[0])
    update(i, a[i])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
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 = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])

AB.sort(reverse = True)
AB = AB[:K+1]
ABC = []
for i in range(len(AB)):
    for j in range(Z):
        ABC.append(AB[i]+C[j])
ABC.sort(reverse = True)
for i in range(K):
    print(ABC[i])


Fixed submission:
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 = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])

AB.sort(reverse = True)
AB = AB[:K+1]
ABC = []
for i in range(len(AB)):
    for j in range(Z):
        ABC.append(AB[i]+C[j])
ABC.sort(reverse = True)
for i in range(K):
    print(ABC[i])
Buggy python submission (verdict: Runtime Error):
S = input()
atcg = ['A', 'C', 'T', 'G']
ans = 0
count = 0
for i in range(S):
  if S[i] in atcg:
    count += 1
    ans = max(count, ans)
  else:
    count = 0
print(ans)

Fixed submission:
S = input()
atcg = ['A', 'C', 'T', 'G']
ans = 0
count = 0
for i in range(len(S)):
  if S[i] in atcg:
    count += 1
    ans = max(count, ans)
  else:
    count = 0
print(ans)
Buggy python submission (verdict: Runtime Error):
n, q = map(int, input().split())
s = input()
ac = [0]
for i in range(len(s)):
  if s[i] == 'A' and s[i+1] == 'C':
    ac.append(ac[i]+1)
  else:
    ac.append(ac[i])
for i in range(q):
  l, r = map(int, input().split())
  print(ac[r-1]-ac[l-1])
  


Fixed submission:
n, q = map(int, input().split())
s = input()
ac = [0]
for i in range(len(s)-1):
  if s[i] == 'A' and s[i+1] == 'C':
    ac.append(ac[i]+1)
  else:
    ac.append(ac[i])
for i in range(q):
  l, r = map(int, input().split())
  print(ac[r-1]-ac[l-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
c = [-1] + [int(input()) for i in range(n)]

count = [0]*(n+2)
dp = [0]*(n+1)
dp[0] = 1
mod = 10**9+7
#dp[i]: i番目までの場合の数
for i in range(n):
    dp[i+1] = dp[i]
    if c[i+1] != c[i]:
        dp[i+1] += count[c[i+1]]
        dp[i+1] %= mod
    count[c[i+1]] += dp[i]
    count[c[i+1]] %= mod

print(dp[n])


Fixed submission:
n = int(input())
c = [-1] + [int(input()) for i in range(n)]

count = [0]*(200005)
dp = [0]*(n+1)
dp[0] = 1
mod = 10**9+7
#dp[i]: i番目までの場合の数
for i in range(n):
    dp[i+1] = dp[i]
    if c[i+1] != c[i]:
        dp[i+1] += count[c[i+1]]
        dp[i+1] %= mod
        count[c[i+1]] += dp[i]
        count[c[i+1]] %= mod

print(dp[n]%mod)
Buggy python submission (verdict: Runtime Error):
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
ans = 0
for i in range(N):
  a = list(map(int, input().split()))
  point = c
  for i in range(m):
    point += a[i]*b[i]
  if point > 0:
    ans += 1
print(ans)

Fixed submission:
n, m, c = map(int, input().split())
b = list(map(int, input().split()))
ans = 0
for i in range(n):
  a = list(map(int, input().split()))
  point = c
  for i in range(m):
    point += a[i]*b[i]
  if point > 0:
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
ans = 0
for i in range(N):
  a, b = input().split()
  if b == 'JPY':
    ans += int(a)
  else:
    ans += int(a)*380000
print(ans)

Fixed submission:
N = int(input())
ans = 0.0
for i in range(N):
  a, b = input().split()
  if b == 'JPY':
    ans += float(a)
  else:
    ans += float(a)*380000
print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
ans = 0
for i in range(N):
  a, b = input().split()
  if b = 'JPY':
    ans += int(a)
  else:
    ans += int(a)*380000
print(ans)

Fixed submission:
N = int(input())
ans = 0.0
for i in range(N):
  a, b = input().split()
  if b == 'JPY':
    ans += float(a)
  else:
    ans += float(a)*380000
print(ans)
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

#white = ".", black = "#"
def search(x, y, color):
    global ans
    if color == ".":
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "#" and not dp[x+m][y]:
                    dp[x+m][y] = True
                    color = "#"
                    search(x+m, y, color)
        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "#" and not dp[x][y+n]:
                    dp[x][y+n] = True
                    color = "#"
                    search(x, y+n, color)

    else:
        for m in [1, -1]:
            if 0 <= x+m <= H-1:
                if S[x+m][y] == "." and not dp[x+m][y]:
                    ans += 1
                    dp[x+m][y] = True
                    color = "."
                    search(x+m, y, color)

        for n in [1, -1]:
            if 0 <= y+n <= W-1:
                if S[x][y+n] == "." and not dp[x][y+n]:
                    ans += 1
                    dp[x][y+n] = True
                    color = "."
                    search(x, y+n, color)


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            dp = [[False] * W for a in range(H)]
            dp[i][j] = True
            search(i, j, "#")

print(ans)


Fixed submission:
N = int(input())
H = int(input())
W = int(input())
print((N - H + 1)*(N - W + 1))
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
dp = [[0 for i in range(W + 1)] for j in range(N+1)]

for j in range(N):
    w, v = map(int, input().split())
    for k in range(W + 1):
        if k >= w:
            dp[j+1][k] = max(dp[j][k-w] + v, dp[j][k])
        else:
            dp[j+1][k] = dp[j][k]
ans = 0
for i in range(W + 1):
    ans = max(ans, dp[N][i])
print(dp[N][W])


Fixed submission:
N, W = map(int, input().split())
dp = [[0 for i in range(W + 1)] for j in range(N+1)]

for j in range(N):
    w, v = map(int, input().split())
    for k in range(W + 1):
        if k >= w:
            dp[j+1][k] = max(dp[j][k-w] + v, dp[j][k])
        else:
            dp[j+1][k] = dp[j][k]

print(dp[N][W])
Buggy python submission (verdict: Runtime Error):
N, P = map(int, input().split())
ans = 0
if N == 1:
    print(P)
else:
    for i in range(1, int(P**(1/N)+5)):
        if P % i**N == 0:
            ans = i
    print(ans)


Fixed submission:
N, P = map(int, input().split())
ans = 0
if N == 1:
    print(P)
elif N >= P or N > 50:
    print(1)

else:
    for i in range(1, int(P**(1/N)+2)):
        if P % i**N == 0:
            ans = i
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int, input().split())
ans = 0
if N == 1:
    print(P)
else:
    for i in range(1, int(P**(1/N)+5)):
        if P % i**N == 0:
            ans = i
    print(ans)


Fixed submission:
N, P = map(int, input().split())
ans = 0
if N == 1:
    print(P)
elif N >= P or N > 50:
    print(1)

else:
    for i in range(1, int(P**(1/N)+2)):
        if P % i**N == 0:
            ans = i
    print(ans)