Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define e1 first
#define e2 second
#define nextline putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
const int INF = 1e7;
const ll MOD = 1e9 + 7;
const double pi = 3.141592653589793;

int main()
{
    int n;
    cin>>n;
    ll ans = 1ll;

    bool flag = true;
    REP(i,n) {
        ll nans = ans;
        ll a;
        cin>>a;
        nans *= a;

        if (nans > (ll)1e18 || nans < ans) {
            flag = false;
        }
        ans = nans;
    }
    cout<<(flag || ans == 0 ? ans : -1)<<endl;

    return 0;
}


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

n = int(input())
a = list(map(int, input().split()))
ans = 1
flag = True

for ta in a:
    ans *= ta
    if (ans > 10 ** 18):
        flag = False
        ans = 1

if (flag or ans == 0):
    print(ans)
else:
    print(-1)

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

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

for ta in a:
    ans *= ta

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


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

n = int(input())
a = list(map(int, input().split()))
ans = 1
flag = True

for ta in a:
    ans *= ta
    if (ans > 10 ** 18):
        flag = False
        ans = 1

if (flag or ans == 0):
    print(ans)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
 from sys import stdin
input = stdin.readline


a, b = map(str, input().split())
a = int(a)
b = int((float(b) + 0.001) * 100)
ans = int(a * b // 100)
print(ans)


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


a, b = map(str, input().split())
a = int(a)
b = int((float(b) + 0.001) * 100)
ans = int(a * b // 100)
print(ans)

Buggy python submission (verdict: Runtime Error):
from sys import stdin
input = stdin.readline

a, b = map(str, input().split())
a = int(a)
b = int(float(b + 0.001) * 100)
ans = int(a * b // 100)
print(ans)


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


a, b = map(str, input().split())
a = int(a)
b = int((float(b) + 0.001) * 100)
ans = int(a * b // 100)
print(ans)
Buggy python submission (verdict: Runtime Error):
from sys import stdin
input = stdin.readline

from collections import deque

X = int(input())
s = {}
q = deque()

q.append([1, 0])
while True:
	ab = q.popleft()
	tmp = ab[0] ** 5 - ab[1] ** 5
	if (tmp == X):
		print(ab[0], ab[1])
		quit()
	elif (tmp > X):
		q.append([ab[0] - 1, ab[1]])
		q.append([ab[0], ab[1] - 1])
	else:
		q.append([ab[0] + 1, ab[1]])
		q.append([ab[0], ab[1] - 1])


Fixed submission:
#from sys import stdin
#input = stdin.readline

s = input()

if s == 'ABC':
	print('ARC')
else:
	print('ABC')
Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline

from collections import deque

X = int(input())
s = {}
q = deque()

q.append([1, 0])
while True:
	ab = q.popleft()
	tmp = ab[0] ** 5 - ab[1] ** 5
	if (tmp == X):
		print(ab[0], ab[1])
		quit()
	elif (tmp > X):
		q.append([ab[0] - 1, ab[1]])
		q.append([ab[0], ab[1] - 1])
	else:
		q.append([ab[0] + 1, ab[1]])
		q.append([ab[0], ab[1] - 1])


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

from collections import deque

X = int(input())
s = {}
q = deque()
q.append((1, 0))
done = {(1, 0)}

while True:
	ab = q.popleft()
	tx = ab[0] ** 5 - ab[1] ** 5
	#print(ab)
	if (tx == X):
		print(ab[0], ab[1])
		quit()
	elif (tx > X):
		if ((ab[0] - 1, ab[1]) not in done):
			q.append((ab[0] - 1, ab[1]))
			done.add((ab[0] - 1, ab[1]))
		if (ab[1] > 0 or (ab[0], ab[1] + 1) not in done):
			q.append((ab[0], ab[1] + 1))
			done.add((ab[0], ab[1] + 1))
		if (ab[1] <= 0 or (ab[0], ab[1] - 1) not in done):
			q.append((ab[0], ab[1] - 1))
			done.add((ab[0], ab[1] - 1))
	else:
		if ((ab[0] + 1, ab[1]) not in done):
			q.append((ab[0] + 1, ab[1]))
			done.add((ab[0] + 1, ab[1]))
		if (ab[1] <= 0 or (ab[0], ab[1] - 1) not in done):
			q.append((ab[0], ab[1] - 1))
			done.add((ab[0], ab[1] - 1))
Buggy python submission (verdict: Runtime Error):
K = int(input())
A, B = map(int, input().split())

if ((A // K != B // K) || A % K == 0 || B % K == 0):
	print('OK')
else:
	print('NG')


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

if ((A // K != B // K) or A % K == 0 or B % K == 0):
	print('OK')
else:
	print('NG')
Buggy python submission (verdict: Runtime Error):
import math
r = input()
print(2 * math.pi * r)
quit()


Fixed submission:
import math
r = int(input())
print(2 * math.pi * r)
quit()

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

r = input()

print(2 * math.pi * r)


Fixed submission:
import math
r = int(input())
print(2 * math.pi * r)
quit()
Buggy python submission (verdict: Time Limit Exceeded):
import math
k = int(input())
ans = 0

for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += math.gcd(a, math.gcd(b, c))

print(ans)

Fixed submission:
import math
k = int(input())
ans = 0
ab = {}

for a in range(1,k+1):
  for b in range(1,k+1):
    tmp = math.gcd(a, b)
    if tmp not in ab:
      ab[tmp] = 1
    else:
      ab[tmp] += 1

for c in range(1,k+1):
  for d in ab.keys():
    ans += math.gcd(c, d) * ab[d]

print(ans)
Buggy python submission (verdict: Runtime Error):
s = sort(input())
if s[0] == 'a' and s[1] == 'b' and s[2] == 'c':
	print('Yes')
else:
	print('No')

Fixed submission:
s = sorted(input())
if s[0] == 'a' and s[1] == 'b' and s[2] == 'c':
	print('Yes')
else:
	print('No')
Buggy python submission (verdict: Runtime Error):
N = int(input())
Di1 = []
Di2 = []
nmDi = 0
if N >= 3 and N <= 100:
   for x in range(N):
      Di1.append(int(input()))
      Di2.append(int(input()))
   for x in range(N):
      if Di1[x] == Di2[x]:
         nmDi += 1
         if nmDi == 3:
            break
      elif Di1[x] != Di2[x] and nmDi > 0:
         nmDi = 0
   if nmDi >= 3:
      print("Yes")
   else:
      print("No")
else:
   print ("No")

Fixed submission:
N = int(input())
Di = 0
Di1 = []
Di2 = []
nmDi = 0
if N >= 3 and N <= 100:
   for x in range(N):
      Di = input()
      Di1.append(Di[0])
      Di2.append(Di[-1])
   for x in range(N):
      if Di1[x] == Di2[x]:
         nmDi += 1
         if nmDi == 3:
            break
      elif Di1[x] != Di2[x] and nmDi > 0:
         nmDi = 0
   if nmDi >= 3:
      print("Yes")
   else:
      print("No")
else:
   print ("No")

Buggy python submission (verdict: Runtime Error):
N = int(input())
Di1 = []
Di2 = []
nmDi = 0
if N >= 3 and N <= 100:
   for x in range(N):
      Di1.append(int(input()))
      Di2.append(int(input()))
   for x in range(N):
      if Di1[x] == Di2[x]:
         nmDi += 1
         if nmDi == 3:
            break
      elif Di1[x] != Di2[x] and nmDi > 0:
         nmDi = 0
   if nmDi >= 3:
      print("Yes")
   else:
      print("No")

Fixed submission:
N = int(input())
Di = 0
Di1 = []
Di2 = []
nmDi = 0
if N >= 3 and N <= 100:
   for x in range(N):
      Di = input()
      Di1.append(Di[0])
      Di2.append(Di[-1])
   for x in range(N):
      if Di1[x] == Di2[x]:
         nmDi += 1
         if nmDi == 3:
            break
      elif Di1[x] != Di2[x] and nmDi > 0:
         nmDi = 0
   if nmDi >= 3:
      print("Yes")
   else:
      print("No")
else:
   print ("No")

Buggy python submission (verdict: Runtime Error):
N = int(input())
Di1 = []
Di2 = []
nmDi = 0
if N >= 3 and N <= 100:
   for x in range(N):
      Di1.append(int(input()))
      Di2.append(int(input()))
for x in range(N):
   if Di1[x] == Di2[x]:
      nmDi += 1
      if nmDi == 3:
         break
   elif Di1[x] != Di2[x] and nmDi > 0:
      nmDi = 0
if nmDi >= 3:
   print("Yes")
else:
   print("No")

Fixed submission:
N = int(input())
Di = 0
Di1 = []
Di2 = []
nmDi = 0
if N >= 3 and N <= 100:
   for x in range(N):
      Di = input()
      Di1.append(Di[0])
      Di2.append(Di[-1])
   for x in range(N):
      if Di1[x] == Di2[x]:
         nmDi += 1
         if nmDi == 3:
            break
      elif Di1[x] != Di2[x] and nmDi > 0:
         nmDi = 0
   if nmDi >= 3:
      print("Yes")
   else:
      print("No")
else:
   print ("No")
Buggy python submission (verdict: Time Limit Exceeded):

N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
MOD = 998244353

dp = [0] * (N + 1)
dp[1] = 1

for i in range(1, N):
    for l, r in X:
        for k in range(l, r + 1):
            if i + k > N:
                break
            dp[i + k] += dp[i]
            dp[i + k] %= MOD

print(dp[-1])


Fixed submission:

N, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]
MOD = 998244353

dp = [0] * N
sdp = [0] * (N + 1)
dp[0] = 1
sdp[1] = 1

for i in range(1, N):
    for l, r in X:
        dp[i] += sdp[max(0, i - l + 1)] - sdp[max(0, i - r)]
        dp[i] %= MOD
    sdp[i + 1] = sdp[i] + dp[i]
    sdp[i + 1] %= MOD

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):

from collections import defaultdict

H, W, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

ctr_h = defaultdict(list)
ctr_w = defaultdict(list)

for h, w in X:
    ctr_h[h].append((h, w))
    ctr_w[w].append((h, w))

val_h = sorted(ctr_h.items(), key=lambda x: -len(x[1]))
val_w = sorted(ctr_w.items(), key=lambda x: -len(x[1]))

max_h = len(val_h[0][1])
max_w = len(val_w[0][1])

res = 0
for h, pairs_h in val_h:
    if len(pairs_h) < max_h:
        break

    for w, pairs_w in val_w:
        if len(pairs_w) < max_w:
            break

        cand = set()
        for point in pairs_h:
            cand.add(point)

        for point in pairs_w:
            cand.add(point)

        res = max(res, len(cand))

print(res)


Fixed submission:

import sys
from collections import defaultdict

H, W, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

ctr_h = defaultdict(int)
ctr_w = defaultdict(int)
appeared = set()

for h, w in X:
    ctr_h[h] += 1
    ctr_w[w] += 1
    appeared.add(h * W + w)

val_h = sorted(ctr_h.items(), key=lambda x: -x[1])
val_w = sorted(ctr_w.items(), key=lambda x: -x[1])

max_h = val_h[0][1]
max_w = val_w[0][1]

val_h = [i for i, v in val_h if v == max_h]
val_w = [i for i, v in val_w if v == max_w]

if len(val_h) * len(val_w) > M:
    print(max_h + max_w)
    sys.exit(0)

for h in val_h:
    for w in val_w:
        if h * W + w not in appeared:
            print(max_h + max_w)
            sys.exit(0)
else:
    print(max_h + max_w - 1)
Buggy python submission (verdict: Runtime Error):
K = int(input())
S = input()

MAX = 10 ** 6 + 100
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

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

N = len(S)
ans = 0
for i in range(K + 1):
    tmp = (pow(25, K - i, MOD) * pow(26, i, MOD)) % MOD
    ans += comb(N + K - i - 1, N - 1) * tmp
    ans %= MOD
print(ans)


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

MAX = 2 * 10 ** 6 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

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

N = len(S)
ans = 0
for i in range(K + 1):
    tmp = (pow(25, K - i, MOD) * pow(26, i, MOD)) % MOD
    ans += comb(N + K - i - 1, N - 1) * tmp
    ans %= MOD
print(ans)

Buggy python submission (verdict: Runtime Error):
K = int(input())
S = input()

MAX = 10 ** 6 + 100
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

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

N = len(S)
ans = 0
for i in range(K + 1):
    tmp = (pow(25, K - i, MOD) * pow(26, i, MOD)) % MOD
    ans += comb(N + K - i - 1, N - 1) * tmp
    ans %= MOD
print(ans)


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

MAX = 2 * 10 ** 6 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

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

N = len(S)
ans = 0
for i in range(K + 1):
    tmp = (pow(25, K - i, MOD) * pow(26, i, MOD)) % MOD
    ans += comb(N + K - i - 1, N - 1) * tmp
    ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):

N, K = map(int, input().split())
X = list(map(int, input().split()))

x = X[:]
for _ in range(K):
    if all(v == N for v in x):
        break

    new = [0] * N
    for i in range(N):
        for j in range(max(0, i - x[i]), min(N, i + x[i] + 1)):
            new[j] += 1
    x = new[:]

print(*x)


Fixed submission:
N, K, *A = map(int, open(0).read().split())

x = A[:]

for _ in range(min(50, K)):
    y = [0] * (N + 1)
    for i in range(N):
        y[max(0, i - x[i])] += 1
        y[min(N, i + x[i] + 1)] -= 1
        
    for i in range(N):
        y[i + 1] += y[i]
        
    x = y[:]
        
    
print(*x[:-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K, *A = map(int, open(0).read().split())

x = A[:]

for _ in range(K):
    y = [0] * (N + 1)
    for i in range(N):
        y[max(0, i - x[i])] += 1
        y[min(N, i + x[i] + 1)] -= 1
        
    for i in range(N):
        y[i + 1] += y[i]
        
    x = y[:]
        
    
print(*x[:-1])


Fixed submission:
N, K, *A = map(int, open(0).read().split())

x = A[:]

for _ in range(min(50, K)):
    y = [0] * (N + 1)
    for i in range(N):
        y[max(0, i - x[i])] += 1
        y[min(N, i + x[i] + 1)] -= 1
        
    for i in range(N):
        y[i + 1] += y[i]
        
    x = y[:]
        
    
print(*x[:-1])
Buggy python submission (verdict: Runtime Error):
N, *A = map(int, open(0).read().split())

cnt = [[0, 0] for _ in range(N + 1)]
cnt[-1] = [A[-1], A[-1]]
exists = True
for i in reversed(range(N)):
    if i > 45:
        cnt[i] = [cnt[i + 1][0] + A[i][0]] * 2
    else:
        nex_min = cnt[i + 1][0] // 2 + cnt[i + 1][0] % 2
        nex_max = cnt[i + 1][1] // 2 + cnt[i + 1][1] % 2
        lim = pow(2, i)
        if lim < nex_min + A[i]:
            exists = False
            break
        
        cnt[i][0] = min(lim, nex_min + A[i])
        cnt[i][1] = min(lim, cnt[i + 1][1] + A[i])

if exists:
    print(sum(v for _, v in cnt))
else:
    print(-1)




Fixed submission:
N, *A = map(int, open(0).read().split())

cnt = [0] * (N + 1)
cnt[0] = 1
for i in range(N):
    cnt[i + 1] = (cnt[i] - A[i]) * 2

ans = 0
cur = 0
for i in reversed(range(N + 1)):
    cur += A[i]
    ans += min(cnt[i], cur)
        
if all(cnt[i] >= A[i] for i in range(N + 1)):
    print(ans)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from math import gcd

N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]

d = {}
for a, b in X:
    if a == b == 0:
        pass
    elif a == 0:
        if b > 0:
            b = 1
        else:
            b = -1
    elif b == 0:
        if a > 0:
            a = 1
        else:
            a = -1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if a * b >= 0:
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

mod = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p]
    else:
        a, b = d[p]
        ans *= pow(2, a, mod) + pow(2, b, mod) - 1
        
print(ans + zero - 1)


Fixed submission:
from collections import defaultdict
from math import gcd

N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]

d = {}
for a, b in X:
    if a == b == 0:
        pass
    elif a == 0:
        if b > 0:
            b = 1
        else:
            b = -1
    elif b == 0:
        if a > 0:
            a = 1
        else:
            a = -1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if (a > 0 and b >= 0) or (a < 0 and b <= 0):
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

mod = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p][1]
    else:
        a, b = d[p]
        ans *= pow(2, a, mod) + pow(2, b, mod) - 1
        ans %= mod
        
print((ans + zero - 1) % mod)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect

N = int(input())
A = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
dp[0] = -INF
ans = [0] * N

def dfs(u, p=-1):
    # Update dp
    i = bisect(dp, A[u])
    old = dp[i]
    dp[i] = A[u]

    # Calc ans
    ans[u] = i
    if p != -1:
        ans[u] = max(ans[u], ans[p])

    # Go to next
    for v in graph[u]:
        if v == p:
            continue
        dfs(v, u)

    # Restore
    dp[i] = old

dfs(0)
print(*ans)


Fixed submission:
from bisect import bisect_left
from collections import deque

N = int(input())
A = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N

# DFS
q = deque([(0, 0)])  # (current, parent)
while q:
    u, p = q.pop()

    # Roll back
    if p is None:
        i, x = rb[u].pop()
        dp[i] = x
        continue

    # Update dp
    i = bisect_left(dp, A[u])
    rb[u].append((i, dp[i]))
    dp[i] = A[u]

    # Calc ans
    ans[u] = max(i, ans[p])

    # Go to next
    q.append((u, None))
    for v in graph[u]:
        if v == p:
            continue
        q.append((v, u))

print(*ans)

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

N = int(input())
A = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

INF = 10 ** 9 + 7
dp = [INF] * N
dp[0] = -INF
ans = [0] * N

def dfs(u, p=-1):
    # Update dp
    i = bisect(dp, A[u])
    old = dp[i]
    dp[i] = A[u]

    # Calc ans
    ans[u] = i
    if p != -1:
        ans[u] = max(ans[u], ans[p])

    # Go to next
    for v in graph[u]:
        if v == p:
            continue
        dfs(v, u)

    # Restore
    dp[i] = old

dfs(0)
print(*ans)


Fixed submission:
from bisect import bisect_left
from collections import deque

N = int(input())
A = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

INF = 10 ** 9 + 7
dp = [INF] * (N + 1)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N

# DFS
q = deque([(0, 0)])  # (current, parent)
while q:
    u, p = q.pop()

    # Roll back
    if p is None:
        i, x = rb[u].pop()
        dp[i] = x
        continue

    # Update dp
    i = bisect_left(dp, A[u])
    rb[u].append((i, dp[i]))
    dp[i] = A[u]

    # Calc ans
    ans[u] = max(i, ans[p])

    # Go to next
    q.append((u, None))
    for v in graph[u]:
        if v == p:
            continue
        q.append((v, u))

print(*ans)
Buggy python submission (verdict: Runtime Error):

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

MOD = 10 ** 9 + 7
ans = 0
ctr = [0] * (N + 1)

for x in reversed(range(1, N + 1)):
    ctr[x] = pow(K // x, N, MOD)
    for y in range(2 * x, N + 1, x):
        ctr[x] -= ctr[y]

ans = 0
for n in range(1, K + 1):
    ans += n * ctr[n]
    ans %= MOD

print(ans)


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

def func(n):
    r = n
    for i in range(2, n + 1):
        if i ** 2 > n:
            break

        if n % i == 0:
            r -= r // i
            while n % i == 0:
                n //= i
        
    if n > 1:
        r -= r // n
    return r


MOD = 10 ** 9 + 7
ans = 0
for i in range(1, K + 1):
    ans += func(i) * pow(K // i, N, MOD)
print(ans % MOD)
Buggy python submission (verdict: Runtime Error):

X, Y, A, B, C = map(int, input().split())
P = sorted(map(int, input().split()))
Q = sorted(map(int, input().split()))
R = sorted(map(int, input().split()))

ans = 0
for _ in range(X):
    if P[-1] > R[-1]:
        ans += P.pop()
    else:
        ans += R.pop()

for _ in range(Y):
    if Q[-1] > R[-1]:
        ans += Q.pop()
    else:
        ans += R.pop()

print(ans)


Fixed submission:
X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

z = sorted(p)[-X:] + sorted(q)[-Y:] + r
print(sum(sorted(z)[-(X+Y):]))
Buggy python submission (verdict: Runtime Error):
ans = (H * W)
if ans % 2 == 1:
    print(ans // 2 + 1)
else:
    print(ans // 2)

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

ans = H * W
if H == 1 or W == 1:
    print(1)
elif ans % 2 == 1:
    print(ans // 2 + 1)
else:
    print(ans // 2)