Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

counter = Counter(A)
ans = 0
for num, count in counter.items():
    ans += num * count

for i in range(Q):
    if B[i] in counter:
        ans += counter[B[i]] * C[i] - counter[B[i]] * B[i]
        counter[C[i]] = counter[C[i]] + counter.pop([B[i]])
    print(ans)


Fixed submission:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

counter = Counter(A)
ans = 0
for num, count in counter.items():
    ans += num * count

for i in range(Q):
    if B[i] in counter:
        ans += counter[B[i]] * C[i] - counter[B[i]] * B[i]
        counter[C[i]] = counter[C[i]] + counter.pop(B[i])
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

counter = Counter(A)

for i in range(Q):
    if B[i] in counter:
        counter[C[i]] = counter[C[i]] + counter.pop(B[i])
    ans = 0
    for num, count in counter.items():
        ans += num * count
    print(ans)


Fixed submission:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

counter = Counter(A)
ans = 0
for num, count in counter.items():
    ans += num * count

for i in range(Q):
    if B[i] in counter:
        ans += counter[B[i]] * C[i] - counter[B[i]] * B[i]
        counter[C[i]] = counter[C[i]] + counter.pop(B[i])
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

ans = 1
for a in A:
    ans *= a

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)


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

ans = 1

min_A = min(A)
A = sorted(A, reverse=True)

if min_A == 0:
    print(0)
    exit()

for a in A:
    ans *= a
    if ans > 10 ** 18:
        break

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)
Buggy python submission (verdict: Runtime Error):
A, B = input().split()
A = int(A // 100)
B = int(float(B) * 100)
AB = A * B
print(AB)


Fixed submission:
A, B = input().split()
A = int(A)
B = int(B.replace(".", ""))

print(A * B // 100)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

A = [None] * N
B = [None] * N

for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b

medians = []

if N % 2 == 0:
    a_median = (A[N // 2 - 1] + A[N // 2]) // 2
    b_median = (B[N // 2 - 1] + B[N // 2]) // 2
    i = a_median
    while i <= b_median:
        medians.append(i)
        i += 0.5
else:
    a_median = A[(N + 1) // 2 - 1]
    b_median = B[(N + 1) // 2 - 1]
    for i in range(a_median, b_median + 1):
        medians.append(i)

print(len(medians))


Fixed submission:
from statistics import median

n = int(input())
a = [None] * n
b = [None] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

if n % 2 == 1:
    print(abs(median(b) - median(a)) + 1)
else:
    print(int(abs(median(b) - median(a)) * 2) + 1)
Buggy python submission (verdict: Runtime Error):
import queue

N, M = map(int, input().split())

graph = [[] for i in range(N)]

for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    graph[A].append(B)
    graph[B].append(A)

dist = [-1 for i in range(N)]
que = queue.Queue()

dist[0] = 0
que.put(0)


while not que.empty():
    v = que.get()
    for nv in graph[v]:
        if dist[nv] != -1:
            continue

        dist[nv] = dist[v] + 1
        que.push(nv)


print("Yes")
for i in range(1, N):
    print(v[i] + 1)


Fixed submission:
import queue

N, M = map(int, input().split())

graph = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    graph[A].append(B)
    graph[B].append(A)

# 各部屋に設定する番号を記録する
v = [-1 for i in range(N)]  # 全頂点を「未訪問」に初期化
v[0] = 0  # スタート地点を0にする
# queueを作成し部屋1（インデックスは0）を入れる
q = queue.Queue()
q.put(0)

while not q.empty():
    # queueの先頭（今いる部屋の番号）を取り出す
    x = q.get()
    # 今いる部屋と繋がっている部屋を順に探索する
    for y in graph[x]:
        # -1 でない場合は探索済みなのでスキップする
        if v[y] != -1:
            continue
        # あとで探索するためにqueueに入れておく
        q.put(y)
        v[y] = x

print("Yes")
for i in range(1, N):
    print(v[i] + 1)
Buggy python submission (verdict: Runtime Error):
def solve(A, B, C, K):
    num = K

    if K <= A:
        return 1 * A

    num -= A
    ans = 1 * A

    if num <= B:
        return ans

    num -= B

    if num < 0:
        return ans

    return ans - num


A, B, C, K = map(int, input().split())
print(solve1(A, B, C, K))



Fixed submission:
A, B, C, K = map(int, input().split())

if K <= A:
    print(K)
elif K <= A + B:
    print(A)
else:
    print(A - (K - (A + B)))
Buggy python submission (verdict: Runtime Error):
import math
import sys
input = sys.stdin.readline

A, B, N = map(int, input().split())
x = min(B-1, N)
print(A*x/B - A*(X/B))


Fixed submission:
import math
import sys
input = sys.stdin.readline

A, B, N = map(int, input().split())
x = min(B-1, N)
print(math.floor(A*x/B) - A*math.floor(x/B))

Buggy python submission (verdict: Time Limit Exceeded):
import math
import sys
input = sys.stdin.readline

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

ans = 0

for i in range(N + 1):
    t = math.floor(A * i / B) - A * math.floor(i / B)
    ans = max(ans, t)

print(ans)


Fixed submission:
import math
import sys
input = sys.stdin.readline

A, B, N = map(int, input().split())
x = min(B-1, N)
print(math.floor(A*x/B) - A*math.floor(x/B))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            a = [i, j, k]
            l = 0
            for s in S:
                if l < 3  and a[l] == int(s):
                    l += 1
            if l == 3:
                ans += 1

print(ans)


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

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            a = [i, j, k]
            l = 0
            for s in S:
                if l < 3  and a[l] == int(s):
                    l += 1
            if l == 3:
                ans += 1

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

while M > 0:
    maxv = max(A)
    max_index = A.index(maxv)
    A[max_index] = A[max_index] // 2
    M -= 1

print(sum(A))


Fixed submission:
import heapq


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

A = [a * -1 for a in A]

heapq.heapify(A)
for _ in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, (-a // 2) * (-1))

print(-sum(A))
Buggy python submission (verdict: Runtime Error):
from typing import List


N = int(input())

L: List[int] = [None] * (N + 1)
L[0] = 2
L[1] = 1

for i in range(2, N + 1):
    L[i] = L[i - 1] + L[i - 2]

print(L[N])


Fixed submission:
N = int(input())

L = [None] * (N + 1)
L[0] = 2
L[1] = 1

for i in range(2, N + 1):
    L[i] = L[i - 1] + L[i - 2]

print(L[N])
Buggy python submission (verdict: Runtime Error):
from typing import Optional
import sys


def dfs(i: int, s: str, val: int, formula: str) -> Optional[str]:
    if (i == len(s) - 1):
        if val == 7:
            print(formula + "=7")
            sys.exit()
            return formula
        else:
            return None

    dfs(i + 1, s, val + int(s[i + 1]), formula + "+" + s[i + 1])
    dfs(i + 1, s, val - int(s[i + 1]), formula + "-" + s[i + 1])
    return None


s = input()
ans = dfs(0, s, int(s[0]), s[0])


Fixed submission:
import sys


def dfs(i, s, val, formula):
    if (i == len(s) - 1):
        if val == 7:
            print(formula + "=7")
            sys.exit()
            return formula
        else:
            return None

    dfs(i + 1, s, val + int(s[i + 1]), formula + "+" + s[i + 1])
    dfs(i + 1, s, val - int(s[i + 1]), formula + "-" + s[i + 1])
    return None


s = input()
ans = dfs(0, s, int(s[0]), s[0])
Buggy python submission (verdict: Runtime Error):
import numpy as np

W, H, N = map(int, input().split())

area = np.ones((W, H))

for _ in range(N):
    x, y, a = map(int, input().split())

    if a == 1:
        area[:x, :] = 0
    elif a == 2:
        area[x:, :] = 0
    elif a == 3:
        area[:, :y] = 0
    elif a == 4:
        area[:, y:] = 0

print(int(np.sum(area)))


Fixed submission:
import numpy as np

W, H, N = map(int, input().split())

area = np.ones((W, H))

for _ in range(N):
    x, y, a = map(int, input().split())

    if a == 1:
        area[:x, :] = 0
    elif a == 2:
        area[x:, :] = 0
    elif a == 3:
        area[:, :y] = 0
    elif a == 4:
        area[:, y:] = 0

print(int(np.sum(area)))
Buggy python submission (verdict: Runtime Error):
import sys
class City:
  def __init__(self, index, pref, time):
    self.index = index
    self.pref = pref
    self.time = time
    self.sort_res = None
  def get_id(self):
    str1 = "0"*(6-len(str(self.pref)))+str(self.pref)
    str2 = "0"*(6-len(str(self.sort_res)))+str(self.sort_res)
    return str1 + str2
if __name__ == '__main__':
  nm = list(sys.stdin,readline().split(" "))
  N = int(nm[0])
  M = int(nm[1])
  prefs = [[]] * N
  cities = []
  for i in range(M):
    info = list(sys.stdin,readline().split(" "))
    newcity = City(i,int(info[0]),int(info[1]))
    prefs[int(info[0])].append(newcity)
  for i in range(N):
    prefs[i].sort(key = lambda x: x.time)
  	for j in range(len(prefs[i])):
      prefs[i][j].sort_res = j+1
  for i in prefs:
    for j in i:
      cities.append(i)
  cities.sort(key = lambda x:x.index)
  for i in cities:
    print(i.get_id())
  
      
   
  

Fixed submission:
import sys


class City:
    def __init__(self, ind, pref, time):
        self.ind = ind
        self.pref = pref
        self.time = time
        self.sort_res = None

    def get_id(self):
        str1 = "0" * (6 - len(str(self.pref))) + str(self.pref)
        str2 = "0" * (6 - len(str(self.sort_res))) + str(self.sort_res)
        return str1 + str2
    def __str__(self):
    	return str(self.ind)
if __name__ == '__main__':
    nm = list(sys.stdin.readline().split(" "))
    N = int(nm[0])
    M = int(nm[1])
    prefs = [[] for x in range(N)]
    cities = []
    for i in range(M):
        info = sys.stdin.readline().rstrip().split(" ")
        newcity = City(i, int(info[0]), int(info[1]))
        prefs[int(info[0])-1].append(newcity)
    for i in range(N):
        prefs[i].sort(key=lambda x: x.time)
        for j in range(len(prefs[i])):
            prefs[i][j].sort_res = j + 1
    for i in prefs:
        for j in i:
            cities.append(j)
    cities.sort(key=lambda y: y.ind)
    for i in cities:
        print(i.get_id())
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
s = 1
x = 0
y = 0
for i in range(n):
    s *= a[i]
    if a[i] == 0:
        y += 1
    if s > 1000000000000000000:
        x += 1

if y != 0:
    print(0)
else:
    if x != 0:
        print(-1)
    else:
        print(s)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
s = 1
x = 0
y = 0
for i in range(n):
    s *= a[i]
    if a[i] == 0:
        y += 1
    if s > 1000000000000000000:
        s = 0
        x += 1

if y != 0:
    print(0)
else:
    if x != 0:
        print(-1)
    else:
        print(s)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
s = 1
x = 0
y = 0
for i in range(n):
    s *= a[i]
    if a[i] == 0:
        y += 1
    if s > 1000000000000000000:
        x += 1

if y != 0:
    print(0)
else:
    if x != 0:
        print(-1)
    else:
        print(s)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
s = 1
x = 0
y = 0
for i in range(n):
    s *= a[i]
    if a[i] == 0:
        y += 1
    if s > 1000000000000000000:
        s = 0
        x += 1

if y != 0:
    print(0)
else:
    if x != 0:
        print(-1)
    else:
        print(s)
Buggy python submission (verdict: Runtime Error):
import sympy
import math
n = int(input())
s = 0
l  = sympy.factorint(n)
l2 = list(dict.values(l))
for i in range(len(l2)):
    s += int((math.sqrt(1 + 9 * l2[i])-1)/2)

print(s)


Fixed submission:
import math
import collections

n = int(input())
s = 0
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

m = 0
l = collections.Counter(prime_factorize(n))
l2 = list(dict.values(l))
#for i in range(len(l2)):
#    s += int((math.sqrt(1 + 9 * l2[i])-1)/2)
for i in range(len(l2)):
    for j in range(n):
        if l2[i] >= j*(j+1)/2:
            m = j
        else:
            break


    s += m


print(s)

Buggy python submission (verdict: Runtime Error):
import sympy
import math
n = int(input())
s = 0
l  = sympy.factorint(n)
l2 = list(dict.values(l))
for i in range(len(l2)):
    s += int((math.sqrt(1 + 9 * l2[i])-1)/2)

print(s)


Fixed submission:
import math
import collections

n = int(input())
s = 0
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

m = 0
l = collections.Counter(prime_factorize(n))
l2 = list(dict.values(l))
#for i in range(len(l2)):
#    s += int((math.sqrt(1 + 9 * l2[i])-1)/2)
for i in range(len(l2)):
    for j in range(n):
        if l2[i] >= j*(j+1)/2:
            m = j
        else:
            break


    s += m


print(s)
Buggy python submission (verdict: Runtime Error):
import math

N = int(input())
A = N
S = []
for i in range(N):
    S += [input()]
for j in range (1, N):
    for k in range(j):
        if S[k] == S[j]:
            A -= 1
            break
print(A)


Fixed submission:
S, W = map(int, input().split())

if S > W:
    print('safe')
else:
    print('unsafe')
Buggy python submission (verdict: Runtime Error):
3
apple
orange
apple

Fixed submission:
N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = N
S = [input() for _ in range(N)]
for i in range(N):
    for k in range(i):
        if S[k] == S[i]:
            A -= 1
            break
print(A)


Fixed submission:
N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = N
S = []
for i in range(N):
    S += [input()]
    for k in range(i):
        if S[k] == S[i]:
            A -= 1
            break
print(A)


Fixed submission:
N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))

Buggy python submission (verdict: Time Limit Exceeded):
import math

N = int(input())
A = N
S = []
for i in range(N):
    S += [input()]
    for k in range(i):
        if S[k] == S[i]:
            A -= 1
            break
print(A)


Fixed submission:
N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))

Buggy python submission (verdict: Time Limit Exceeded):
import math

N = int(input())
A = N
S = []
for i in range(N):
    S += [input()]
for j in range (1, N):
    for k in range(j):
        if S[k] == S[j]:
            A -= 1
            break
print(A)


Fixed submission:
N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))

Buggy python submission (verdict: Time Limit Exceeded):
import math

N = int(input())
A = N
S = []
for i in range(N):
    S += [input()]
for j in range (1, N):
    for k in range(j):
        if S[k] == S[j]:
            A -= 1
            break
print(A)


Fixed submission:
N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))
Buggy python submission (verdict: Runtime Error):
S = input()
X = 0
for i in range(3):
    if A [i] == 7:
        X += 1
if X == 0:
    print('No')
else:
    print('Yes')


Fixed submission:
import math
N = int(input())
if N%10 == 7:
  print("Yes")
elif (N-N%10)%100 == 70:
  print("Yes")
elif N-N%100 == 700:
  print("Yes")
else:
  print("No")

Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
if N%10 == 7:
  print(Yes)
elif (N-N%10)%100 == 70:
  print(Yes)
elif N/100 == 7:
  print(Yes)
else:
  print(No)

Fixed submission:
import math
N = int(input())
if N%10 == 7:
  print("Yes")
elif (N-N%10)%100 == 70:
  print("Yes")
elif N-N%100 == 700:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Time Limit Exceeded):
import math
K = int(input())
S = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for l in range(1,K+1):
      S = S + math.gcd(l, math.gcd(j,i))

print(S)


Fixed submission:
import math
K = int(input())
S = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for l in range(1,K+1):
      S = S + math.gcd(l, math.gcd(j,i))

print(S)
Buggy python submission (verdict: Runtime Error):
A, B, C = input().split()  
print(C A B)                   

Fixed submission:
A, B, C = input().split()
print(C, A ,B)
Buggy python submission (verdict: Runtime Error):
S = input()
N = len(S)
P = 0
for i in range (N-1//2):
    if S[i] == S[N-1-i]:
        for k in range(N-1//2):
            if S[k] == S[((N-1)//2)-k] and S[((N+1)//2)+k] == S[N-1-k]:
                P = P
            else:
                P += 1
        else:
            P += 1

if P == 0:
    print('Yes')
else:
    print('No')


Fixed submission:
S = input()
N = len(S)
P = 0
for i in range ((N-1)//2):
    if S[i] == S[N-1-i]:
        for k in range((N-1)//2):
            if S[k] == S[((N-3)//2)-k] and S[((N+1)//2)+k] == S[N-1-k]:
                P = P
            else:
                P += 1
    else:
        P += 1

if P == 0:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
import math
N,K = map(int,input().split())

for i in range(int(math.log2(N)+1)):
    if N >= pow(K,i) and N < pow(K,i+1):
        print(i+1)
        exit()


Fixed submission:
import math
N,K = map(int,input().split())

for i in range(int(math.log2(N)+1)):
    if N >= pow(K,i) and N < pow(K,i+1):
        print(i+1)
        exit()
Buggy python submission (verdict: Runtime Error):
s,t = map(input().split())
a,b = map(int,input().split())
u = input()

if u == s:
  print((a-1),b)
else:
  print(a,(b-1))

Fixed submission:
s,t = input().split()
a,b = map(int,input().split())
u = input()

if u == s:
  print((a-1),b)
else:
  print(a,(b-1))
Buggy python submission (verdict: Runtime Error):
N , M = map(int,input().split())
p = [''] * M
S = [''] * M
A = [0] * N
W = [0] * N
for i in range(M):
    p[i],S[i] = map(str,input().split())
    p[i] = int(p[i])
    if A[p[i]-1] == 0:
        if S[i] == 'WA':
            W[p[i]-1] += 1
        else:
            A[p[i]-1] += 1

for j in range(N):
    if A[j] == 0:
        W[j] =0
 print(sum(A),sum(W))


Fixed submission:
N , M = map(int,input().split())
p = [''] * M
S = [''] * M
A = [0] * N
W = [0] * N
for i in range(M):
    p[i],S[i] = map(str,input().split())
    p[i] = int(p[i])
    if A[p[i]-1] == 0:
        if S[i] == 'WA':
            W[p[i]-1] += 1
        else:
            A[p[i]-1] += 1

for j in range(N):
    if A[j] == 0:
        W[j] =0
print(sum(A),sum(W))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
L = [0] * M
R = [0] * M
min = 1
max = N
X = 0
for i in range(M):
    L[i], R[i] = map(int, input().split())
    if L[i] > min:
        min = L[i]
    if R[i] < max:
        max = R[i]
    if R[i] < min or L[i] > max:
        X +=1


if X = 0:
    print(max-min+1)
else:
    print(0)


Fixed submission:
N, M = map(int, input().split())
L = [0] * M
R = [0] * M
min = 1
max = N
X = 0
for i in range(M):
    L[i], R[i] = map(int, input().split())
    if L[i] > min:
        min = L[i]
    if R[i] < max:
        max = R[i]
    if R[i] < min or L[i] > max:
        X +=1


if X == 0:
    print(max-min+1)
else:
    print(0)
Buggy python submission (verdict: Runtime Error):
from functools import lru_cache
MOD = 1000000007

def valid(s):
    f = 0
    if len(s) == 4:
        f = 1
        if (s[0] == 'A' and s[2:] == 'GC') or (s[0:2] == 'AG' and s[3] == 'C'):
            return 0
    return s[f:] != 'AGC' and s[f:] != 'ACG' and s[f:] != 'GAC'
    

@lru_cache(maxsize=None)
def dfs(n, s):
    if not valid(s):
        return 0

    if n == N:
        return 1

    f = len(s) == 4
    a = dfs(n+1, s[f:] + 'A')
    b = dfs(n+1, s[f:] + 'C')
    c = dfs(n+1, s[f:] + 'G')
    d = dfs(n+1, s[f:] + 'T')
    return (a + b + c + d) % MOD
    

N = int(input())
ans = dfs(0, '')
print(ans)


Fixed submission:
ans = {}
ans['A'] = 'T'
ans['T'] = 'A'
ans['C'] = 'G'
ans['G'] = 'C'


s = input()
print(ans[s])
Buggy python submission (verdict: Runtime Error):
from functools import lru_cache
MOD = 1000_000_007

def valid(s):
    f = 0
    if len(s) == 4:
        f = 1
        if (s[0] == 'A' and s[2:] == 'GC') or (s[0:2] == 'AG' and s[3] == 'C'):
            return 0
    return s[f:] != 'AGC' and s[f:] != 'ACG' and s[f:] != 'GAC'
    

@lru_cache(maxsize=None)
def dfs(n, s):
    if not valid(s):
        return 0

    if n == N:
        return 1

    f = len(s) == 4
    a = dfs(n+1, s[f:] + 'A')
    b = dfs(n+1, s[f:] + 'C')
    c = dfs(n+1, s[f:] + 'G')
    d = dfs(n+1, s[f:] + 'T')
    return (a + b + c + d) % MOD
    

N = int(input())
ans = dfs(0, '')
print(ans)


Fixed submission:
from functools import lru_cache
MOD = 1000000007

def valid(s):
    f = 0
    if len(s) == 4:
        f = 1
        if (s[0] == 'A' and s[2:] == 'GC') or (s[0:2] == 'AG' and s[3] == 'C'):
            return 0
    return s[f:] != 'AGC' and s[f:] != 'ACG' and s[f:] != 'GAC'
    

@lru_cache(maxsize=None)
def dfs(n, s):
    if not valid(s):
        return 0

    if n == N:
        return 1

    f = len(s) == 4
    a = dfs(n+1, s[f:] + 'A')
    b = dfs(n+1, s[f:] + 'C')
    c = dfs(n+1, s[f:] + 'G')
    d = dfs(n+1, s[f:] + 'T')
    return (a + b + c + d) % MOD
    

N = int(input())
ans = dfs(0, '')
print(ans)
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())

def calc(x): #[0, x]
    if x == 0: return 0
    res = 0
    x += 1
    for i in range(64):
        length = 2**i
        cycle = 2**(i+1)
        num = (x // cycle) * length
        if (x % cycle) > length: num += x % cycle - length
        if num%2: res += 2**i
    return res

def calc2(x):
    res = 0
    for i in range(x+1): res ^= i
    return res

for i in range(100):
    a, b = calc(i), calc2(i)
    assert a == b ,f'i={i}, a={a}, b={b}'

ans = calc(B) ^ calc(A-1)
print(ans)


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

def calc(x): #[0, x]
    if x == 0: return 0
    res = 0
    x += 1
    for i in range(64):
        length = 2**i
        cycle = 2**(i+1)
        num = (x // cycle) * length
        if (x % cycle) > length: num += x % cycle - length
        if num%2: res += 2**i
    return res
'''
def calc2(x):
    res = 0
    for i in range(x+1): res ^= i
    return res

for i in range(100):
    a, b = calc(i), calc2(i)
    assert a == b ,f'i={i}, a={a}, b={b}'
'''

ans = calc(B) ^ calc(A-1)
print(ans)