Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    coeff = 1
    while True:
        if TA[n][0] * coeff >= t_votes and TA[n][1] * coeff >= a_votes:
            break
        coeff += 1
    t_votes = coeff * TA[n][0]
    a_votes = coeff * TA[n][1]

print(t_votes + a_votes)

Fixed submission:
N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    t_ratio = TA[n][0]
    a_ratio = TA[n][1]
    # coeff = 1
    # while TA[n][0] * coeff < t_votes or TA[n][1] * coeff < a_votes:
    #     coeff += 1
    # ↓
    coeff = max((t_ratio + t_votes - 1) // t_ratio,
                (a_ratio + a_votes - 1) // a_ratio)

    t_votes = coeff * t_ratio
    a_votes = coeff * a_ratio

print(t_votes + a_votes)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    coeff = 1
    while True:
        if TA[n][0] * coeff >= t_votes and TA[n][1] * coeff >= a_votes:
            break
        coeff += 1
    t_votes = coeff * TA[n][0]
    a_votes = coeff * TA[n][1]

print(t_votes + a_votes)

Fixed submission:
N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    t_ratio = TA[n][0]
    a_ratio = TA[n][1]
    # coeff = 1
    # while TA[n][0] * coeff < t_votes or TA[n][1] * coeff < a_votes:
    #     coeff += 1
    # ↓
    coeff = max((t_ratio + t_votes - 1) // t_ratio,
                (a_ratio + a_votes - 1) // a_ratio)

    t_votes = coeff * t_ratio
    a_votes = coeff * a_ratio

print(t_votes + a_votes)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    coeff = 1
    while TA[n][0] * coeff < t_votes or TA[n][1] * coeff < a_votes:
        coeff += 1
    t_votes = coeff * TA[n][0]
    a_votes = coeff * TA[n][1]

print(t_votes + a_votes)


Fixed submission:
N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    t_ratio = TA[n][0]
    a_ratio = TA[n][1]
    # coeff = 1
    # while TA[n][0] * coeff < t_votes or TA[n][1] * coeff < a_votes:
    #     coeff += 1
    # ↓
    coeff = max((t_ratio + t_votes - 1) // t_ratio,
                (a_ratio + a_votes - 1) // a_ratio)

    t_votes = coeff * t_ratio
    a_votes = coeff * a_ratio

print(t_votes + a_votes)
Buggy python submission (verdict: Runtime Error):
N, A = map(int, input().split())
x = list(map(int, input().split()))

total = sum(x)

# dp[i][j][k] := i枚目までからj枚取って、合計をkにする通り数
dp = [[[0] * (total+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1


for i in range(N+1):
    for j in range(N+1):
        for k in range(total+1):
            if i >= 1 and x[i-1] > k:
                dp[i][j][k] = dp[i-1][j][k]
            elif i >= 1 and j >= 1 and x[i-1] <= k:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k - x[i-1]]

ans = 0
for j in range(1, N+1):
     # N枚(カード総数)の中から1枚以上取った時の、j枚取って合計がj*Aの所 の合計
    ans += dp[N][j][j*A]
print(ans)

Fixed submission:
N, A = map(int, input().split())
x = list(map(int, input().split()))

max_of_a = N * A

# dp[i][j][k] := i枚目までからj枚取って、合計をkにする通り数
dp = [[[0] * (max_of_a + 1) for _ in range(N+1)]for _ in range(N+1)]
dp[0][0][0] = 1


for i in range(N+1):
    for j in range(N+1):
        for k in range(max_of_a + 1):
            if i >= 1 and x[i-1] > k:
                dp[i][j][k] = dp[i-1][j][k]
            elif i >= 1 and j >= 1 and x[i-1] <= k:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k - x[i-1]]

ans = 0
for j in range(1, N+1):
    # N枚(カード総数)の中から1枚以上取った時の、j枚取って合計がj*Aの所 の合計
    ans += dp[N][j][j*A]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations, starmap

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

coefficient = 1  # Aの係数
result = 0
while coefficient <= N:
    for r in range(1, N+1):
        multiple_of_a = coefficient * A
        combis_sums = map(sum, combinations(x_list, r))
        for combi_sum in combis_sums:
            if combi_sum == multiple_of_a:
                result += 1
        coefficient += 1

print(result)

Fixed submission:
N, A = map(int, input().split())
x = list(map(int, input().split()))

max_of_a = N * A

# dp[i][j][k] := i枚目までからj枚取って、合計をkにする通り数
dp = [[[0] * (max_of_a + 1) for _ in range(N+1)]for _ in range(N+1)]
dp[0][0][0] = 1


for i in range(N+1):
    for j in range(N+1):
        for k in range(max_of_a + 1):
            if i >= 1 and x[i-1] > k:
                dp[i][j][k] = dp[i-1][j][k]
            elif i >= 1 and j >= 1 and x[i-1] <= k:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k - x[i-1]]

ans = 0
for j in range(1, N+1):
    # N枚(カード総数)の中から1枚以上取った時の、j枚取って合計がj*Aの所 の合計
    ans += dp[N][j][j*A]
print(ans)
Buggy python submission (verdict: Runtime Error):
from statistics import mean

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

target = round(mean(a))
cost = 0
for num in a:
    cost += (num - target)**2

print(cost)


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


def mean(numbers):
    return sum(a) / N


target = round(mean(a))
cost = 0
for num in a:
    cost += (num - target)**2

print(cost)
Buggy python submission (verdict: Runtime Error):
ef main():
    HAIKU = [5, 7, 5]
    v = list(map(int, input().split()))
    return equal_list(v, HAIKU)


def equal_list(lst1, lst2):
    lst = lst1.copy()
    for element in lst2:
        try:
            lst.remove(element)
        except ValueError:
            break
    else:
        if not lst:
            return "YES"
    return "NO"


if __name__ == "__main__":
    print(main())


Fixed submission:
def equal_list(lst1, lst2):
    lst = lst1.copy()
    for element in lst2:
        try:
            lst.remove(element)
        except ValueError:
            break
    else:
        if not lst:
            return "YES"
    return "NO"


HAIKU = [5, 7, 5]
v = list(map(int, input().split()))
print(equal_list(v, HAIKU))
Buggy python submission (verdict: Time Limit Exceeded):
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


if __name__ == '__main__':
    N = int(input())
    prime = prime_factorize(N)
    res = N - 1
    for i in range(2**(len(prime)-1)):
        a = 1
        b = 1
        for j in range(len(prime)):
            if i & (1 << j):
                a *= prime[j]
            else:
                b *= prime[j]
        res = min(res, a+b-2)
    print(res)



Fixed submission:

if __name__ == '__main__':
    N = int(input())
    res = 1
    for i in range(2, int(N**.5)+1):
        if N % i == 0:
            res = i
    print(res + N//res - 2)

Buggy python submission (verdict: Time Limit Exceeded):
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


if __name__ == '__main__':
    N = int(input())
    prime = prime_factorize(N)
    res = N - 1
    for i in range(2**(len(prime)-1)):
        a = 1
        b = 1
        for j in range(len(prime)):
            if i & (1 << j):
                a *= prime[j]
            else:
                b *= prime[j]
        res = min(res, a+b-2)
    print(res)



Fixed submission:

if __name__ == '__main__':
    N = int(input())
    res = 1
    for i in range(2, int(N**.5)+1):
        if N % i == 0:
            res = i
    print(res + N//res - 2)

Buggy python submission (verdict: Time Limit Exceeded):
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


if __name__ == '__main__':
    N = int(input())
    prime = prime_factorize(N)
    res = N - 1
    for i in range(2**len(prime)):
        a = 1
        b = 1
        for j in range(len(prime)):
            if i & (1 << j):
                a *= prime[j]
            else:
                b *= prime[j]
        res = min(res, a+b-2)
    print(res)



Fixed submission:

if __name__ == '__main__':
    N = int(input())
    res = 1
    for i in range(2, int(N**.5)+1):
        if N % i == 0:
            res = i
    print(res + N//res - 2)
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def coprime(a, b):
    return gcd(a, b) == 1


if __name__ == '__main__':
    A, B = map(int, input().split())
    A = min(A, B)
    B = max(A, B)
    ans = set()
    for i in range(1, A+1):
        if A % i == 0 and B % i == 0:
            flag = True
            for a in ans:
                if gcd(i, a) != 1:
                    flag = False
                    break
            if flag:
                ans.add(i)
    print(len(ans))

Fixed submission:
from fractions import gcd

if __name__ == '__main__':
    n = gcd(*map(int, input().split()))
    a = i = 1
    while i * i < n:
        i += 1
        a += n % i < 1
        while n % i < 1:
            n /= i
    print(a + (n > 1))
Buggy python submission (verdict: Runtime Error):
if __name__ == '__main__':
    N, K = map(int, input())
    S = input()
    ans = 0
    for i in range(N-1):
        if S[i] == S[i+1]:
            ans += 1
    ans = min(N-1, ans+K*2)
    print(ans)


Fixed submission:
import sys

if __name__ == '__main__':
    N, K = map(int, sys.stdin.readline().split())
    S = input()
    ans = 0
    for i in range(N-1):
        if S[i] == S[i+1]:
            ans += 1
    ans = min(N-1, ans+K*2)
    print(ans)
Buggy python submission (verdict: Runtime Error):
def search(can):
    day = 0
    while True:
        # matchの候補をリスト化
        match = []
        for i in range(N):
            if can[can[i]] == i:
                match.append((i, can[i]))

        if len(match) == 0:
            return -1

        # 可能なmatchの組み合わせで試していく
        for i in range(1 << len(match)):
            player = [0] * N
            flag = True
            for j in range(len(match)):
                if i >> j & 1 == 1:
                    if player[i] or player[i]:
                        flag = False
                        break
                    player[i] = player[j] = 1
                if flag:
                    # matchを行う
                    for i, p in enumerate(player):
                        if p:
                            consumed[i] += 1
                            if consumed[i] != N:
                                can[i] = A[i][consumed[i]]
                    day += 1

        if sum(consumed) == N * (N-1):
            return day


if __name__ == '__main__':
    N = int(input())
    A = [[int(x)-1 for x in input().split()] for _ in range(N)]

    # 初期化
    can = dict()
    consumed = [0] * N
    for i in range(N):
        can[i] = A[i][0]

    print(search(can))
    print()



Fixed submission:
from collections import deque

if __name__ == '__main__':
    N = int(input())
    matches = [[int(x) - 1 for x in input().split()] for _ in range(N)]
    q = deque(range(N))
    days = [0] * N
    pairs = [-1] * N
    while q:
        a = q.popleft()
        match = matches[a]
        if not match:
            continue
        b = match.pop(0)
        if pairs[b] == a:
            days[a] = days[b] = max(days[a], days[b]) + 1
            q.append(a)
            q.append(b)
        else:
            pairs[a] = b
    print(max(days) if not any(matches) else -1)
Buggy python submission (verdict: Runtime Error):
import bisect
from collections import deque

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = deque(sorted(A, reverse=True))
#A.sort(reverse=True)

for i in range(M):
    a = A.popleft()
    a /= 2
    index = bisect.bisect_left(A, a)
    A.insert(index-1, a)

ans = 0
for a in A:
    ans += a//1
print(int(ans))

Fixed submission:
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
heapq.heapify(A)

for i in range(M):
    a = heapq.heappop(A)
    a /= 2
    heapq.heappush(A, a)

ans = 0
for a in A:
    ans += - a//1
print(int(ans))

Buggy python submission (verdict: Runtime Error):
import bisect
from collections import deque
import math

N, M = map(int, input().split())
_A = list(map(int, input().split()))
A = deque(sorted(_A, reverse=True))
#A  = sorted(_A, reverse=True)

for i in range(M):
    a = A.popleft()
    a /= 2
    index = bisect.bisect_left(A, a)
    A.insert(index-1, a)

ans = 0
for a in A:
    ans += math.floor(a)
print(int(ans))

Fixed submission:
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
heapq.heapify(A)

for i in range(M):
    a = heapq.heappop(A)
    a /= 2
    heapq.heappush(A, a)

ans = 0
for a in A:
    ans += - a//1
print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
arr = [None]*N
visited = [False]*N
UVW = []
for i in range(N-1):
    u, v, w = map(int, input().split())
    if i==0:
        arr[u-1] = 0
        visited[u-1] = True
    if visited[u-1]:
        arr[v-1] = arr[u-1] + w
        visited[v-1] = True
    elif visited[v-1]:
        arr[u-1] = arr[v-1] + w
        visited[u-1] = True
    else:
        UVW.append([u,v,w])

while len(UVW)>0:
    u,v,w = UVW.pop(0)
    if visited[u-1]:
        arr[v-1] = arr[u-1] + w
        visited[v-1] = True
    elif visited[v-1]:
        arr[u-1] = arr[v-1] + w
        visited[u-1] = True
    else:
        UVW.append([u,v,w])
    

for a in arr:
    if a%2==0:
        print(0)
    else:
        print(1)

Fixed submission:
N = int(input())

q = []
visited = [0] * N
ans = [0] * N
A = [[] for _ in range(N)]  # tree
W = [[] for _ in range(N)]  # weight

for i in range(N-1):
    u,v,w = map(int, input().split())
    u -= 1
    v -= 1
    A[u].append(v)
    A[v].append(u)
    W[u].append(w)
    W[v].append(w)

q.append(0)  # start
for _ in range(N):
    u = q.pop(0)
    visited[u] = 1
    k = 0
    for v in A[u]:
        if visited[v]==0:
            q.append(v)
            ans[v] = ans[u] + W[u][k]
        k += 1

for a in ans:
    print(a%2)

Buggy python submission (verdict: Runtime Error):
N = int(input())
arr = [None]*N
visited = [False]*N
for i in range(N-1):
    u, v, w = map(int, input().split())
    if i==0:
        arr[u-1] = 0
        arr[v-1] = w
    else:
        if visited[u-1]:
            arr[v-1] = arr[u-1] + w
        else:
            arr[u-1] = arr[v-1] + w
    visited[u-1] = True
    visited[v-1] = True

for a in arr:
    if a%2==0:
        print(0)
    else:
        print(1)

Fixed submission:
N = int(input())

q = []
visited = [0] * N
ans = [0] * N
A = [[] for _ in range(N)]  # tree
W = [[] for _ in range(N)]  # weight

for i in range(N-1):
    u,v,w = map(int, input().split())
    u -= 1
    v -= 1
    A[u].append(v)
    A[v].append(u)
    W[u].append(w)
    W[v].append(w)

q.append(0)  # start
for _ in range(N):
    u = q.pop(0)
    visited[u] = 1
    k = 0
    for v in A[u]:
        if visited[v]==0:
            q.append(v)
            ans[v] = ans[u] + W[u][k]
        k += 1

for a in ans:
    print(a%2)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

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

def gcd_of_arr(arr):
    cd = arr[0]
    for i in range(1,len(arr)):
        if cd==1:
            return cd
        cd = gcd(arr[i], cd)
    return cd

ans = 0
for i in range(N):
    tmp = gcd_of_arr(A[0:i] + A[i+1:N])
    ans = max(ans, tmp)

print(ans)


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

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

L, R = [0]*(N+1), [0]*(N+1)
for i in range(1,N+1):
    L[i] = gcd(L[i-1], A[i-1])
    R[N-i] = gcd(R[N+1-i], A[N-i])

ans = 0
for i in range(N):
    ans = max(ans, gcd(L[i], R[i+1]))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

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

def gcd_of_arr(arr):
    cd = arr[0]
    for i in range(1,len(arr)):
        if cd==1:
            return cd
        cd = gcd(arr[i], cd)
    return cd

B = [0]*N
for i in range(N):
    tmp = A[0:i] + A[i+1:N]
    B[i] = gcd_of_arr(tmp)

print(max(B))


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

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

L, R = [0]*(N+1), [0]*(N+1)
for i in range(1,N+1):
    L[i] = gcd(L[i-1], A[i-1])
    R[N-i] = gcd(R[N+1-i], A[N-i])

ans = 0
for i in range(N):
    ans = max(ans, gcd(L[i], R[i+1]))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N = int(input())
S = input()

A = np.zeros(N+1)
for i,s in enumerate(S):
    if s=='.':
        A[-i-1:] += 1
    else:
        A[:N-i] += 1

print(int(np.min(A)))

Fixed submission:
N = int(input())
S = input()

A = [None]*(N+1)
A[0] = 0
cnt = 0
for i,s in enumerate(S[::-1]):
    if s=='.':
        A[i+1] = A[i]+1
    else:
        A[i+1] = A[i]-1
        cnt += 1
print(min(A)+cnt)
Buggy python submission (verdict: Runtime Error):
x, y, z, N = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

Q = [[0,0,0]]
i,j,k = Q[0]
P = [A[i]+B[j]+C[k]]

def next(P,Q, cnt):
    if len(P)<0 or cnt==N:
        return
    p = P.pop(0)
    print(p)
    i,j,k = Q.pop(0)
    if i+1<x:
        P.append(A[i+1] + B[j] + C[k])
        Q.append([i+1,j,k])
    if j+1<y:
        P.append(A[i] + B[j+1] + C[k])
        Q.append([i,j+1,k])
    if k+1<z:
        P.append(A[i] + B[j] + C[k+1])
        Q.append([i,j,k+1])
    ids = sorted(range(len(P)), key=lambda k:P[k], reverse=True)
    tmp = [Q[id] for id in ids]
    Q = tmp
    P.sort(reverse=True)
    next(P, Q, cnt+1)
        

next(P, Q, 0)

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()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

ans_list = []
for x,a in enumerate(A):
    for y,b in enumerate(B):
        if (x+1)*(y+1)>K:
                break
        for z,c in enumerate(C):
            if (x+1)*(y+1)*(z+1)>K:
                break
            ans_list.append(a+b+c)

ans_list.sort(reverse=True)

for ans in ans_list[:K]:
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
black1 = ["AGC", "GAC", "ACG"]
black2 = ["AAGC", "ACGC", "AGGC", "ATGC",
        "AGAC", "AGCC", "AGGC", "AGTC"]

def func(S):
    if S[-3:] in black1:
        return 0
    if S[-4:] in black2:
        return 0
    else:
        if len(S)-3==N:
            return 1
        return func(S+"A") + func(S+"C") + func(S+"G") + func(S+"T")


print(func("___"))

Fixed submission:
N = int(input())
black1 = ["AGC", "GAC", "ACG"]
black2 = ["AAGC", "ACGC", "AGGC", "ATGC",
        "AGAC", "AGCC", "AGGC", "AGTC"]
memo = [{} for _ in range(N+1)]

def func(cur, S):
    if S[-3:] in black1:
        return 0
    if S[-4:] in black2:
        return 0
    if S[-3:] in memo[cur]:
        return memo[cur][S[-3:]]
    else:
        if cur==N:
            return 1
        ret = 0
        for s in "ACGT":
            ret = ret + func(cur+1, S+s)
        memo[cur][S[-3:]] = ret
        return ret


print(func(0, "____")%(10**9+7))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
black1 = ["AGC", "GAC", "ACG"]
black2 = ["AAGC", "ACGC", "AGGC", "ATGC",
        "AGAC", "AGCC", "AGGC", "AGTC"]

def func(S):
    if S[-3:] in black1:
        return 0
    if S[-4:] in black2:
        return 0
    else:
        if len(S)-3==N:
            return 1
        return func(S+"A") + func(S+"C") + func(S+"G") + func(S+"T")


print(func("___"))

Fixed submission:
N = int(input())
black1 = ["AGC", "GAC", "ACG"]
black2 = ["AAGC", "ACGC", "AGGC", "ATGC",
        "AGAC", "AGCC", "AGGC", "AGTC"]
memo = [{} for _ in range(N+1)]

def func(cur, S):
    if S[-3:] in black1:
        return 0
    if S[-4:] in black2:
        return 0
    if S[-3:] in memo[cur]:
        return memo[cur][S[-3:]]
    else:
        if cur==N:
            return 1
        ret = 0
        for s in "ACGT":
            ret = ret + func(cur+1, S+s)
        memo[cur][S[-3:]] = ret
        return ret


print(func(0, "____")%(10**9+7))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
black_list= [
    "GACA", "GACC", "GACG", "GACT",
    "ACGA", "ACGC", "ACGG", "ACGT",
    "AGAC", "AGCC", "AGGC", "AGTC",
    "AGCA", "AGCG", "AGCT",
    "AAGC", "ATGC",
    "CAGC", "GAGC", "TAGC",
    "CGAC", "GGAC", "TGAC",
    "AACG", "CACG", "TACG"
]

def func(S):
    if N==3:
        return 61
    if S[-4:] in black_list:
        return 0
    else:
        if len(S)-4==N:
            return 1
        return func(S+"A") + func(S+"C") + func(S+"G") + func(S+"T")


print(func("____"))

Fixed submission:
N = int(input())
black1 = ["AGC", "GAC", "ACG"]
black2 = ["AAGC", "ACGC", "AGGC", "ATGC",
        "AGAC", "AGCC", "AGGC", "AGTC"]
memo = [{} for _ in range(N+1)]

def func(cur, S):
    if S[-3:] in black1:
        return 0
    if S[-4:] in black2:
        return 0
    if S[-3:] in memo[cur]:
        return memo[cur][S[-3:]]
    else:
        if cur==N:
            return 1
        ret = 0
        for s in "ACGT":
            ret = ret + func(cur+1, S+s)
        memo[cur][S[-3:]] = ret
        return ret


print(func(0, "____")%(10**9+7))
Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())
foods = [0]*M
for i in range(N):
    tmp = list(map(int, input().split()))
    for f in tmp[1:]:
        foods[f-1] += 1

cnt = 0
for i in range(1,N+1):
    if foods[i-1]==N:
        cnt += 1
print(cnt)


Fixed submission:
N,M = map(int, input().split())
foods = [0]*M
for i in range(N):
    tmp = list(map(int, input().split()))
    for f in tmp[1:]:
        foods[f-1] += 1
cnt = 0
for i in range(1,M+1):
    if foods[i-1]==N:
        cnt += 1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split()))
MAX = 10**9
dp = [MAX]*N
dp[0] = 0
for i in range(0,N):
    for j in range(1,K+1):
        if i+j>=N:
            break
        tmp = dp[i] + abs(H[i+j]-H[i])
        dp[i+j] = min(dp[i+j], tmp)
print(dp[-1])

Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split()))
MAX = 10**9
dp = [MAX]*N
dp[0] = 0
for i in range(0,N):
    for j in range(1,K+1):
        if i+j>=N:
            break
        tmp = dp[i] + abs(H[i+j]-H[i])
        dp[i+j] = min(dp[i+j], tmp)
print(dp[-1])