Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())

inv = False
for _ in range(q):
    com, *query = input().split()
    if com == "1":
        if not inv:
            inv = True
        else:
            inv = False
    else:
        f, c = query
        if not inv:
            if f == "1":
                s = c + s
            else:
                s = s + c
        else:
            if f == "1":
                s = s + c
            else:
                s = c + s


print(s if not inv else s[::-1])

Fixed submission:
from collections import deque

s = deque(input())
q = int(input())

inv = False
for _ in range(q):
    com, *query = input().split()
    if com == "1":
        if not inv:
            inv = True
        else:
            inv = False
    else:
        f, c = query
        if not inv:
            if f == "1":
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if f == "1":
                s.append(c)
            else:
                s.appendleft(c)


s = "".join(s)
print(s if not inv else s[::-1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())
for _ in range(q):
    com, *query = input().split()

    if com == "1":
        s = s[::-1]
    else:
        f, c = query
        if f == "1":
            s = c + s
        else:
            s = s + c

print(s)


Fixed submission:
from collections import deque

s = deque(input())
q = int(input())

inv = False
for _ in range(q):
    com, *query = input().split()
    if com == "1":
        if not inv:
            inv = True
        else:
            inv = False
    else:
        f, c = query
        if not inv:
            if f == "1":
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if f == "1":
                s.append(c)
            else:
                s.appendleft(c)


s = "".join(s)
print(s if not inv else s[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

n, p = map(int, input().split())
s = input()

if p in (2, 5):
    if p == 2:
        ok_list = [i for i in range(10)][::2]
    else:
        ok_list = [0, 5]
    ans = 0
    for i in range(n):
        if int(s[i]) in ok_list:
            ans += i+1
    print(ans)
else:
    dd = defaultdict(int)
    dd[0] = 1
    prev = 0

    for i in range(n-1, -1, -1):
        d = int(s[i]) * (10**(n-i) % p)
        prev = (prev + d) % p
        dd[prev] += 1

    print(sum(v*(v-1)//2 for v in dd.values()))

Fixed submission:
from collections import defaultdict

n, p = map(int, input().split())
s = input()

if p in (2, 5):
    if p == 2:
        ok_list = [i for i in range(10)][::2]
    else:
        ok_list = [0, 5]
    ans = 0
    for i in range(n):
        if int(s[i]) in ok_list:
            ans += i+1
    print(ans)
else:
    dd = defaultdict(int)
    dd[0] = 1
    prev = 0

    for i in range(n-1, -1, -1):
        d = int(s[i]) * pow(10, n-i, p)
        prev = (prev + d) % p
        dd[prev] += 1

    print(sum(v*(v-1)//2 for v in dd.values()))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
 
n, p = map(int, input().split())
s = input()
 
if p in (2, 5):
    if p == 2:
        ok_list = [i for i in range(10)][::2]
    else:
        ok_list = [0, 5]
    ans = 0
    for i in range(n):
        if int(s[i]) in ok_list:
            ans += i+1
    print(ans)
else:
    dd = defaultdict(int)
    dd[0] = 1
    for i in range(n):
        dd[int(s[i:]) % p] += 1
 
    ans = sum(v*(v-1)//2 for v in dd.values())
    print(ans)

Fixed submission:
from collections import defaultdict

n, p = map(int, input().split())
s = input()

if p in (2, 5):
    if p == 2:
        ok_list = [i for i in range(10)][::2]
    else:
        ok_list = [0, 5]
    ans = 0
    for i in range(n):
        if int(s[i]) in ok_list:
            ans += i+1
    print(ans)
else:
    dd = defaultdict(int)
    dd[0] = 1
    prev = 0

    for i in range(n-1, -1, -1):
        d = int(s[i]) * pow(10, n-i, p)
        prev = (prev + d) % p
        dd[prev] += 1

    print(sum(v*(v-1)//2 for v in dd.values()))

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

ans = 0
for i in range(n):
    for j in range(i+1, n+1):
        ans += (int(s[i:j]) % p == 0) + 0
print(ans)


Fixed submission:
from collections import defaultdict

n, p = map(int, input().split())
s = input()

if p in (2, 5):
    if p == 2:
        ok_list = [i for i in range(10)][::2]
    else:
        ok_list = [0, 5]
    ans = 0
    for i in range(n):
        if int(s[i]) in ok_list:
            ans += i+1
    print(ans)
else:
    dd = defaultdict(int)
    dd[0] = 1
    prev = 0

    for i in range(n-1, -1, -1):
        d = int(s[i]) * pow(10, n-i, p)
        prev = (prev + d) % p
        dd[prev] += 1

    print(sum(v*(v-1)//2 for v in dd.values()))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
table = {x: 2**i for i, x in enumerate(map(chr, range(97, 123)))}

SEG_LEN = n
SEG = [0]*(SEG_LEN*2)


def update(i, x):
    i += SEG_LEN
    SEG[i] = table[x]
    while i > 0:
        i //= 2
        SEG[i] = SEG[i*2] | SEG[i*2+1]


def find(left, right):
    left += SEG_LEN
    right += SEG_LEN
    ans = 0
    while left < right:
        if left % 2 == 1:
            ans = SEG[left] | ans
            left += 1
        left //= 2
        if right % 2 == 1:
            ans = SEG[right-1] | ans
            right -= 1
        right //= 2
    return format(ans, 'b').count('1')


for i, c in enumerate(s):
    update(i, c)

q = int(input())
for _ in range(q):
    com, *query = input().split()
    if com == '1':
        idx, x = query
        update(int(idx)-1, x)
    else:
        L, R = map(int, query)
        print(find(L-1, R))


Fixed submission:
n = int(input())
s = input()
table = {x: 2**i for i, x in enumerate(map(chr, range(97, 123)))}

SEG_LEN = n
SEG = [0]*(SEG_LEN*2)


def update(i, x):
    i += SEG_LEN
    SEG[i] = table[x]
    while i > 0:
        i //= 2
        SEG[i] = SEG[i*2] | SEG[i*2+1]


def find(left, right):
    left += SEG_LEN
    right += SEG_LEN
    ans = 0
    while left < right:
        if left % 2 == 1:
            ans = SEG[left] | ans
            left += 1
        left //= 2
        if right % 2 == 1:
            ans = SEG[right-1] | ans
            right -= 1
        right //= 2
    return format(ans, 'b').count('1')


for i, c in enumerate(s):
    update(i, c)

q = int(input())
for _ in range(q):
    com, *query = input().split()
    if com == '1':
        idx, x = query
        update(int(idx)-1, x)
    else:
        L, R = map(int, query)
        print(find(L-1, R))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = list(input())
q = int(input())


for _ in range(q):
    cmd, x, y = input().split()
    if cmd == '1':
        s[int(x)-1] = y
    else:
        print(len(set(s[int(x)-1:int(y)])))

Fixed submission:
n = int(input())
s = input()
table = {x: 2**i for i, x in enumerate(map(chr, range(97, 123)))}

SEG_LEN = n
SEG = [0]*(SEG_LEN*2)


def update(i, x):
    i += SEG_LEN
    SEG[i] = table[x]
    while i > 0:
        i //= 2
        SEG[i] = SEG[i*2] | SEG[i*2+1]


def find(left, right):
    left += SEG_LEN
    right += SEG_LEN
    ans = 0
    while left < right:
        if left % 2 == 1:
            ans = SEG[left] | ans
            left += 1
        left //= 2
        if right % 2 == 1:
            ans = SEG[right-1] | ans
            right -= 1
        right //= 2
    return format(ans, 'b').count('1')


for i, c in enumerate(s):
    update(i, c)

q = int(input())
for _ in range(q):
    com, *query = input().split()
    if com == '1':
        idx, x = query
        update(int(idx)-1, x)
    else:
        L, R = map(int, query)
        print(find(L-1, R))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, a, b = map(int, input().split())
MOD = 10**9+7
MAX = 2*10**5
fac = [0]*MAX
finv = [0]*MAX
inv = [0]*MAX


def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i-1]*i % MOD
        inv[i] = MOD-inv[MOD % i]*(MOD//i) % MOD
        finv[i] = finv[i-1]*inv[i] % MOD


def COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD


COMinit()

memo = defaultdict(int)


def RECOM(n, k):
    if memo[(n, k)] != 0:
        return memo[(n, k)]
    if MAX < n:
        return n*RECOM(n-1, k-1)//k
    else:
        memo[(n, k)] = COM(n, k)
        return memo[(n, k)]

ans = pow(2, n, MOD)-RECOM(n, a)-RECOM(n, b)-1
print(ans)

Fixed submission:
n, a, b = map(int, input().split())
MOD = 10**9+7


def COM(n, r):
    X = Y = 1
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % MOD
    Y = pow(Y, MOD-2, MOD)
    while 0 < r:
        X = X*n % MOD
        n -= 1
        r -= 1
    return X*Y


ans = pow(2, n, MOD)-1 - COM(n, a)-COM(n, b)
ans %= MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, a, b = map(int, input().split())
MOD = 10**9+7
MAX = 2*10**5
fac = [0]*MAX
finv = [0]*MAX
inv = [0]*MAX


def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i-1]*i % MOD
        inv[i] = MOD-inv[MOD % i]*(MOD//i) % MOD
        finv[i] = finv[i-1]*inv[i] % MOD


def COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD


COMinit()

memo = defaultdict(int)


def RECOM(n, k):
    if memo[(n, k)] != 0:
        return memo[(n, k)]
    if MAX < n:
        return RECOM(n-1, k)+RECOM(n-1, k-1)
    else:
        memo[(n, k)] = COM(n, k)
        return memo[(n, k)]

ans = pow(2, n, MOD)-RECOM(n, a)-RECOM(n, b)-1
print(ans)

Fixed submission:
n, a, b = map(int, input().split())
MOD = 10**9+7


def COM(n, r):
    X = Y = 1
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % MOD
    Y = pow(Y, MOD-2, MOD)
    while 0 < r:
        X = X*n % MOD
        n -= 1
        r -= 1
    return X*Y


ans = pow(2, n, MOD)-1 - COM(n, a)-COM(n, b)
ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])

x, h = xh[0]
cnt = -(-h//a)
ans = cnt
bomb_list = [(x+2*d, cnt*a)]
effective_bomb_idx = 0
for x, h in xh[1:]:
    idx = effective_bomb_idx
    for bomb in bomb_list[idx:]:
        area, damage = bomb
        if x <= area:
            h -= damage
            if h <= 0:
                break
        else:
            effective_bomb_idx += 1

    if 0 < h:
        cnt = -(-h//a)
        bomb_list.append((x+2*d, cnt*a))
        ans += cnt

print(ans)

Fixed submission:
import sys
import bisect
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])
x_list = [x for x, h in xh]

damage = [0]*(n+1)
ans = 0
for i in range(n):
    x, h = xh[i]
    h -= damage[i]
    if h <= 0:
        damage[i+1] += damage[i]
        continue
    cnt = -(-h//a)
    ans += cnt
    damage[i] += cnt*a
    end_idx = bisect.bisect_right(x_list, x+2*d)
    damage[end_idx] -= cnt*a
    damage[i+1] += damage[i]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])

x, h = xh[0]
cnt = -(-h//a)
ans = cnt
bomb_list = [(x+2*d, cnt*a)]
effective_bomb_idx = 0
for x, h in xh[1:]:
    for bomb in bomb_list[effective_bomb_idx:]:
        area, damage = bomb
        if x <= area:
            h -= damage
        else:
            effective_bomb_idx += 1

    if 0 < h:
        cnt = -(-h//a)
        bomb_list.append((x+2*d, cnt*a))
        ans += cnt

print(ans)


Fixed submission:
import sys
import bisect
input = sys.stdin.readline
n, d, a = map(int, input().split())
xh = sorted([tuple(map(int, input().split()))for _ in range(n)])
x_list = [x for x, h in xh]

damage = [0]*(n+1)
ans = 0
for i in range(n):
    x, h = xh[i]
    h -= damage[i]
    if h <= 0:
        damage[i+1] += damage[i]
        continue
    cnt = -(-h//a)
    ans += cnt
    damage[i] += cnt*a
    end_idx = bisect.bisect_right(x_list, x+2*d)
    damage[end_idx] -= cnt*a
    damage[i+1] += damage[i]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
MOD = 10**9+7
n = int(input())
A = ['{:060b}'.format(a)[::-1] for a in map(int, input().split())]
A_d = []
for col in zip(*A):
    c = Counter(map(int, col))
    A_d.append(c[0]*c[1])

ans = 0
for d in range(60):
    ans = ans + A_d[d]*pow(2, d, MOD) % MOD
print(ans % MOD)


Fixed submission:
MOD = 10**9+7
n = int(input())
A = ['{:060b}'.format(a)[::-1] for a in map(int, input().split())]
A_d = []
for col in zip(*A):
    zero_cnt = col.count('0')
    A_d.append(zero_cnt*(n-zero_cnt))

ans = 0
for d in range(60):
    ans = ans + A_d[d]*pow(2, d, MOD) % MOD
print(ans % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
MOD = 10**9+7
n = int(input())
A = ['{:060b}'.format(a)[::-1] for a in map(int, input().split())]

A_d = []
for col in zip(*A):
    c = Counter(map(int, col))
    A_d.append(c[0]*c[1])

ans = 0
for d in range(60):
    ans = ans + A_d[d]*pow(2, d, MOD) % MOD
print(ans % MOD)



Fixed submission:
MOD = 10**9+7
n = int(input())
A = ['{:060b}'.format(a)[::-1] for a in map(int, input().split())]
A_d = []
for col in zip(*A):
    zero_cnt = col.count('0')
    A_d.append(zero_cnt*(n-zero_cnt))

ans = 0
for d in range(60):
    ans = ans + A_d[d]*pow(2, d, MOD) % MOD
print(ans % MOD)
Buggy python submission (verdict: Runtime Error):
MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))

colors = [0]*3
dp = [0]*n
for i in range(n):
    c = colors.count(A[i])
    dp[i] = c
    colors[colors.index(A[i])] += 1
ans = 1
for x in dp:
    ans = ans*x % MOD
print(ans % MOD)


Fixed submission:
MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))

colors = [0]*3
dp = [0]*n
for i in range(n):
    c = colors.count(A[i])
    dp[i] = c
    if c == 0:
        break
    colors[colors.index(A[i])] += 1

ans = 1
for x in dp:
    ans = ans*x % MOD
print(ans % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
n, W = map(int, input().split())
ab = [tuple(map(int, input().split()))for _ in range(n)]
ab.sort(reverse=True)

dp = [0]*W
for w, v in ab:
    for j in reversed(range(W)):
        if j-w < 0:
            break
        if dp[j] < dp[j-w]+v:
            dp[j] = dp[j-w]+v
    if dp[0] < v:
        dp[0] = v
print(max(dp))


Fixed submission:
n, W = map(int, input().split())
ab = [tuple(map(int, input().split()))for _ in range(n)]
ab.sort(reverse=True)

dp = [0]*W
for w, v in ab:
    for j in reversed(range(W)):
        if j-w < 0:
            break
        if dp[j] < dp[j-w]+v:
            dp[j] = dp[j-w]+v
    if dp[0] < v:
        dp[0] = v
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

n = int(input())
l_ls = sorted(map(int, input().split()))

ans = 0
for i, a in enumerate(l_ls):
    for j, b in enumerate(l_ls):
        if i >= j:
            continue

        ls = l_ls[:i] + l_ls[i+1:j] + l_ls[j+1:]

        left = bisect_left(ls, max(a-b, b-a)+1)
        right = bisect_left(ls, a+b)
        ans += right-left


print(ans//3)

Fixed submission:
from bisect import bisect_left

n = int(input())
l_ls = sorted(map(int, input().split()))

ans = 0

for i in range(n):
    for j in range(i+1, n):
        a, b = l_ls[i], l_ls[j]
        right = bisect_left(l_ls, a+b)
        ans += right-(j+1)

print(ans)

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

ans = 0
memo = []
for i, a in enumerate(l_ls):
    for j, b in enumerate(l_ls):
        if i == j:
            continue

        for k, c in enumerate(l_ls):
            if i == k or j == k:
                continue

            if sorted([a, b, c]) in memo:
                continue

            if a < b+c and b < c+a and c < a+b:
                ans += 1
                memo.append(sorted([a, b, c]))

print(ans)

Fixed submission:
from bisect import bisect_left

n = int(input())
l_ls = sorted(map(int, input().split()))

ans = 0

for i in range(n):
    for j in range(i+1, n):
        a, b = l_ls[i], l_ls[j]
        right = bisect_left(l_ls, a+b)
        ans += right-(j+1)

print(ans)

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

ans = 0
for i, a in enumerate(l_ls):
    for j, b in enumerate(l_ls):
        if i == j:
            continue
        for k, c in enumerate(l_ls):
            if i == k or j == k:
                continue

            if a < b+c and b < c+a and c < a+b:
                ans += 1
print(ans//6)

Fixed submission:
from bisect import bisect_left

n = int(input())
l_ls = sorted(map(int, input().split()))

ans = 0

for i in range(n):
    for j in range(i+1, n):
        a, b = l_ls[i], l_ls[j]
        right = bisect_left(l_ls, a+b)
        ans += right-(j+1)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]

border = q-k+1
for i in range(1, n+1):
    if a.count(i) >= border:
        print('Yes')
    else:
        print('No')


Fixed submission:
import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, k, q = map(int, input().split())
dd = defaultdict(int)
for _ in range(q):
    dd[int(input())] += 1

border = q-k+1
for i in range(1, n+1):
    if dd[i] >= border:
        print('Yes')
    else:
        print('No')
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n, m = map(int, input().split())
A = sorted(map(int, input().split()))

for _ in range(m):
    x = A.pop()
    x //= 2
    bisect.insort_right(A, x)
print(sum(A))

Fixed submission:
import sys
from math import floor
from heapq import heappush, heappop, heappushpop
input = sys.stdin.readline
sys.setrecursionlimit(10**7)


# 10**5
n, m = map(int, input().split())
# 10**9
a = sorted(map(lambda s: -int(s), input().split()))


for _ in range(m):
    x = heappop(a)
    heappush(a, x/2)

print(sum(map(lambda x: floor(-x), a)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

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

for i in reversed(range(n)):
    for j in reversed(range(n)):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1]+1


ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        x = min(dp[i][j], j-i)
        if ans < x:
            ans = x
print(ans)


Fixed submission:
n = int(input())
s = input()

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

for i in reversed(range(n)):
    for j in reversed(range(n)):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1]+1


ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        x = min(dp[i][j], j-i)
        if ans < x:
            ans = x
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
print(sum(x for x in range(n)))


Fixed submission:
n = int(input())
print(n*(n-1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7
s = input()
n = len(s)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    digit = n-1-i
    x = s[digit]
    X = []
    if x != '?':
        X.append(int(x)*pow(10, i, 13) % 13)
    else:
        for num in range(10):
            X.append(num*pow(10, i, 13) % 13)
    for j in range(13):
        for x in X:
            dp[i+1][(j+x) % 13] += dp[i][j]
            dp[i+1][(j+x) % 13] %= MOD

print(dp[-1][5])


Fixed submission:
MOD = 10**9+7
s = input()
n = len(s)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    digit = n-1-i
    x = s[digit]
    X = []
    if x != '?':
        X.append(int(x)*pow(10, i, 13) % 13)
    else:
        for num in range(10):
            X.append(num*pow(10, i, 13) % 13)
    for j in range(13):
        for x in X:
            dp[i+1][(j+x) % 13] += dp[i][j]
            dp[i+1][(j+x) % 13] %= MOD

print(dp[-1][5])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))
SUM = sum(A)
MIN = min(A)
start = A.index(MIN)

for odd in range(0, 10**9+1, 2):
    dp = [0]*n
    dp[start] = cnt = odd
    for i in range(start+1, n):
        dp[i] = 2*A[i-1]-dp[i-1]
        cnt += dp[i]
    else:
        for i in range(start):
            dp[i] = 2*A[i-1]-dp[i-1]
            cnt += dp[i]
    if cnt == SUM:
        break
print(*dp)


Fixed submission:
n = int(input())
A = list(map(int, input().split()))
SUM = sum(A)
MIN = min(A)
start = A.index(MIN)

dp = [0]*n
dp[start] = cnt = 0
for i in range(start+1, n):
    dp[i] = 2*A[i-1]-dp[i-1]
    cnt += dp[i]
else:
    for i in range(start):
        dp[i] = 2*A[i-1]-dp[i-1]
        cnt += dp[i]

odd = SUM-cnt
dp = [0]*n
dp[start] = cnt = odd
for i in range(start+1, n):
    dp[i] = 2*A[i-1]-dp[i-1]
    cnt += dp[i]
else:
    for i in range(start):
        dp[i] = 2*A[i-1]-dp[i-1]
        cnt += dp[i]

print(*dp)

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

for odd in range(0, 10**9+1, 2):
    dp = [0]*n
    dp[0] = odd
    cnt = dp[0]
    for i in range(1, n):
        dp[i] = 2*A[i-1]-dp[i-1]
        cnt += dp[i]
    if cnt == SUM:
        break
print(*dp)


Fixed submission:
n = int(input())
A = list(map(int, input().split()))
SUM = sum(A)
MIN = min(A)
start = A.index(MIN)

dp = [0]*n
dp[start] = cnt = 0
for i in range(start+1, n):
    dp[i] = 2*A[i-1]-dp[i-1]
    cnt += dp[i]
else:
    for i in range(start):
        dp[i] = 2*A[i-1]-dp[i-1]
        cnt += dp[i]

odd = SUM-cnt
dp = [0]*n
dp[start] = cnt = odd
for i in range(start+1, n):
    dp[i] = 2*A[i-1]-dp[i-1]
    cnt += dp[i]
else:
    for i in range(start):
        dp[i] = 2*A[i-1]-dp[i-1]
        cnt += dp[i]

print(*dp)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
MOD = 10**9+7
INF = 10**10
dp = [INF]*n

def dfs(v, parent, x):
    dp[v] = x
    if parent == -1:
        next_x = k-1
    else:
        next_x = k-2
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v, next_x)
        next_x -= 1


dfs(0, -1, k)
ans = 1
for x in dp:
    ans = ans*x % MOD
print(ans)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, k = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    edges[a].append(b)
    edges[b].append(a)
MOD = 10**9+7
INF = 10**10
dp = [INF]*n


def dfs(v, parent, x):
    dp[v] = x
    if parent == -1:
        next_x = k-1
    else:
        next_x = k-2
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v, next_x)
        next_x -= 1


dfs(0, -1, k)
ans = 1
for x in dp:
    ans = ans*x % MOD
print(ans)