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


S = input()
T = input()

if set(T) - set(S):
    print(-1)
    exit()

dic = defaultdict(list)
leng_dic = defaultdict(int)

for pos, s in enumerate(S):
    dic[s].append(pos)
    leng_dic[s] += 1

length = len(S)
now = -1
count = 0
for t in T:
    if dic[t][-1] < now:
        now = -1
        count += 1
    idx = bisect.bisect_left(dic[t], now+1)
    now = dic[t][idx]

ans = count*length + now + 1
print(ans)

Fixed submission:
from collections import defaultdict
import bisect


S = input()
T = input()

if set(T) - set(S):
    print(-1)
    exit()

dic = defaultdict(list)
leng_dic = defaultdict(int)

for pos, s in enumerate(S):
    dic[s].append(pos)
    leng_dic[s] += 1

length = len(S)
now = -1
count = 0
for t in T:
    if dic[t][-1] < now+1:
        now = -1
        count += 1
    idx = bisect.bisect_left(dic[t], now+1)
    now = dic[t][idx]

ans = count*length + now + 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict
input = sys.stdin.readline

n, m = map(int, input().split())
dic = defaultdict(list)
total = 0
candidates = []

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

for day in range(1, m+1):
    if day in dic:
        candidates += dic[day]

    if candidates:
        fee = max(candidates)
        total += fee
        candidates.remove(fee)

print(total)

Fixed submission:
import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline

n, m = map(int, input().split())
dic = defaultdict(list)
total = 0
candidates = []
heapq.heapify(candidates)

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

for day in range(1, m+1):
    if day in dic:
        for x in dic[day]:
            heapq.heappush(candidates, -x)

    if candidates:
        total -= heapq.heappop(candidates)

print(total)

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


input = sys.stdin.readline
n, m = map(int, input().split())
dic = defaultdict(list)
total = 0
candidates = []

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

for day in range(1, m+1):
    if day in dic:
        candidates += dic[day]

    if candidates:
        fee = max(candidates)
        total += fee
        candidates.remove(fee)

print(total)


Fixed submission:
import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline

n, m = map(int, input().split())
dic = defaultdict(list)
total = 0
candidates = []
heapq.heapify(candidates)

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

for day in range(1, m+1):
    if day in dic:
        for x in dic[day]:
            heapq.heappush(candidates, -x)

    if candidates:
        total -= heapq.heappop(candidates)

print(total)

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

n, m = map(int, input().split())
dic = {}
fee = 0

for i in range(n):
    a, b = map(int, input().split())
    if a not in dic:
        dic[a] = [b]
    else:
        dic[a].append(b)

for i in range(1, m+1):
    keys = [x for x in range(1, i+1)]
    temp_max_list = []
    for key in keys:
        if key not in dic or dic[key] == []:
            temp_max_list.append(-1)
        else:
            temp_max_list.append(max(dic[key]))
    if max(temp_max_list) == -1:
        continue
    fee += max(temp_max_list)
    select = temp_max_list.index(max(temp_max_list)) + 1
    dic[select].remove(max(temp_max_list))

print(fee)


Fixed submission:
import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline

n, m = map(int, input().split())
dic = defaultdict(list)
total = 0
candidates = []
heapq.heapify(candidates)

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

for day in range(1, m+1):
    if day in dic:
        for x in dic[day]:
            heapq.heappush(candidates, -x)

    if candidates:
        total -= heapq.heappop(candidates)

print(total)
Buggy python submission (verdict: Runtime Error):
import  numpy as np


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int64)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    subcum = np.cumsum(mods)
    idx = subcum[n-1] // div
    count = subcum[-1-idx]
    if count <= k:
        print(count)
        exit()

Fixed submission:
import  numpy as np


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=int)

total = sum(A)
candidates = divisors(total)


for div in candidates:
    mods = A % div
    mods.sort()
    add = div - mods

    addcum = np.cumsum(add)
    subcum = np.cumsum(mods)
    for i in range(n):
        addcount = addcum[n-1] - addcum[i]
        subcount = subcum[i]
        if addcount == subcount and addcount <= k:
            print(div)
            exit()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict


n, k = map(int, input().split())
children = defaultdict(list)
children[1].append(0)
for i in range(n-1):
  parent, child = map(int, input().split())
  children[parent].append(child)
  children[child].append(parent)
  
def cal(x, k):
  patt = k-2
  if x == 1:
    patt += 1
  res = 1
  child = len(children[x])-1
  for i in range(child):
    res *= patt
    patt -= 1
  
  return res

ans = k
for i in range(1, n+1):
  res = cal(i, k)
  ans *= res
  ans %= 1000000007

print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
mod = 10**9 + 7


def perm(n, k):
    if k == 0:
        return 1
    return n * perm(n-1, k-1) % mod


n, k = map(int, input().split())
child = [0] * n

for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    child[a] += 1
    child[b] += 1

ans = k
for i in range(n):
    if i == 0:
        color = k - 1
        num = child[i]
    else:
        color = k - 2
        num = child[i] - 1
    ans = ans * perm(color, num) % mod

print(ans)

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


n, k = map(int, input().split())
children = defaultdict(list)
children[1].append(0)
for i in range(n-1):
  parent, child = map(int, input().split())
  children[parent].append(child)
  children[child].append(parent)
  
def cal(x, k):
  patt = k-2
  if x == 1:
    patt += 1
  res = 1
  child = len(children[x])-1
  for i in range(child):
    res *= patt
    patt -= 1
  
  return res

ans = k
for i in range(1, n+1):
  res = cal(i, k)
  ans *= res
  ans %= 1000000007

print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
mod = 10**9 + 7


def perm(n, k):
    if k == 0:
        return 1
    return n * perm(n-1, k-1) % mod


n, k = map(int, input().split())
child = [0] * n

for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    child[a] += 1
    child[b] += 1

ans = k
for i in range(n):
    if i == 0:
        color = k - 1
        num = child[i]
    else:
        color = k - 2
        num = child[i] - 1
    ans = ans * perm(color, num) % mod

print(ans)
Buggy python submission (verdict: Runtime Error):
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


N, k = map(int, input().split())
for i in range(1, k+1):
    t = N-k+1
    count = cmb(t, i) * cmb(k-1, i-1) % (10**9 + 7)
    print(count)


Fixed submission:
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


N, k = map(int, input().split())
if N == k:
    print(1)
    for i in range(N-1):
        print(0)
    exit()

for i in range(1, k+1):
    t = N-k+1
    if i > t:
        print(0)
        continue
    count = cmb(t, i) * cmb(k-1, i-1) % (10**9 + 7)
    print(count)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10**9 + 7

DP = [[0] * n for _ in range(m)]

t0 = T[0]
count = 0
for i in range(n):
    if S[i] == t0:
        count += 1
    DP[0][i] = count

s0 = S[0]
count = 0
for j in range(m):
    if T[j] == s0:
        count += 1
    DP[j][0] = count

for j in range(1, m):
    for i in range(1, n):
        total = DP[j-1][i] + DP[j][i-1] - DP[j-1][i-1]
        if T[j] == S[i]:
            total += DP[j-1][i-1] + 1
        total %= mod
        DP[j][i] = total

ans = DP[m-1][n-1] + 1
print(ans)


Fixed submission:
n, m = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = 10**9 + 7

DP = [[0] * n for _ in range(m)]

t0 = T[0]
count = 0
for i in range(n):
    if S[i] == t0:
        count += 1
    DP[0][i] = count

s0 = S[0]
count = 0
for j in range(m):
    if T[j] == s0:
        count += 1
    DP[j][0] = count

for j in range(1, m):
    for i in range(1, n):
        total = DP[j-1][i] + DP[j][i-1] - DP[j-1][i-1]
        if T[j] == S[i]:
            total += DP[j-1][i-1] + 1
        total %= mod
        DP[j][i] = total

ans = DP[m-1][n-1] + 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
field = [input() for i in range(H)]
verti_lamp = [[0]*W for i in range(H)]
horiz_lamp = [[0]*W for i in range(H)]


def verti_search(y, x):
    count = 0
    down = 1
    while y+down <= H-1 and field[y+down][x] =='.':
        count += 1
        down += 1
    y += down
    return count, y


def horiz_search(y, x):
    count = 0
    right = 1
    while x+right <= W-1 and field[y][x+right] =='.':
        count += 1
        right += 1
    x += right
    return count, x


for y in range(H):
    x = 0
    while x <= W-1:
        if field[y][x] == '#':
            x += 1
            continue
        else:
            horiz, nx = horiz_search(y, x)
            for t in range(x, nx):
                horiz_lamp[y][t] = horiz
            x = nx

for x in range(W):
    y = 0
    while y <= H-1:
        if field[y][x] == '#':
            y += 1
            continue
        else:
            verti, ny = verti_search(y, x)
            for t in range(y, ny):
                verti_lamp[t][x] = verti
            y = ny

ans = 0
for y in range(H):
    for x in range(W):
        candidate = verti_lamp[y][x] + horiz_lamp[y][x] + 1
        ans = max(ans, candidate)

print(ans)


Fixed submission:
H, W = map(int, input().split())
field = [input() for i in range(H)]
verti_lamp = [[0]*W for i in range(H)]
horiz_lamp = [[0]*W for i in range(H)]


def verti_search(y, x):
    count = 0
    down = 1
    while y+down <= H-1 and field[y+down][x] =='.':
        count += 1
        down += 1
    y += down
    return count, y


def horiz_search(y, x):
    count = 0
    right = 1
    while x+right <= W-1 and field[y][x+right] =='.':
        count += 1
        right += 1
    x += right
    return count, x


for y in range(H):
    x = 0
    while x <= W-1:
        if field[y][x] == '#':
            x += 1
            continue
        else:
            horiz, nx = horiz_search(y, x)
            for t in range(x, nx):
                horiz_lamp[y][t] = horiz
            x = nx

for x in range(W):
    y = 0
    while y <= H-1:
        if field[y][x] == '#':
            y += 1
            continue
        else:
            verti, ny = verti_search(y, x)
            for t in range(y, ny):
                verti_lamp[t][x] = verti
            y = ny

ans = 0
for y in range(H):
    for x in range(W):
        candidate = verti_lamp[y][x] + horiz_lamp[y][x] + 1
        ans = max(ans, candidate)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
L = input()
mod = 10**9 + 7

x = len(L)
L = int(L, 2)
ans = 0
count = 0
for i in range(x-1, -1, -1):
    if (L >> i) & 1:
        ans += ((3**i) * (2**count)) % mod
        ans %= mod
        count += 1
    else:
        continue

ans += 2**count % mod
ans %= mod
print(ans)

Fixed submission:
L = input()
mod = 10**9 + 7

x = len(L)
L = int(L, 2)
DP1 = [0] * (x+1)  # sure under L
DP2 = [0] * (x+1)  # possible under L
DP1[1] = 1
DP2[1] = 2
for i in range(2, x+1):
    if (L >> (x-i)) & 1:
        DP1[i] = (DP1[i-1] * 3 + DP2[i-1]) % mod
        DP2[i] = DP2[i-1] * 2 % mod

    else:
        DP1[i] = DP1[i-1] * 3 % mod
        DP2[i] = DP2[i-1]
ans = (DP1[x] + DP2[x]) % mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
L = input()
mod = 10**9 + 7

x = len(L)
ans = 0
count = 0
for i in range(x):
    if L[i] == '1':
        ans += (3**(x-i-1)) * (2**count)
        ans %= mod
        count += 1
    else:
        continue

ans += 2**count % mod
ans %= mod
print(ans)

Fixed submission:
L = input()
mod = 10**9 + 7

x = len(L)
L = int(L, 2)
DP1 = [0] * (x+1)  # sure under L
DP2 = [0] * (x+1)  # possible under L
DP1[1] = 1
DP2[1] = 2
for i in range(2, x+1):
    if (L >> (x-i)) & 1:
        DP1[i] = (DP1[i-1] * 3 + DP2[i-1]) % mod
        DP2[i] = DP2[i-1] * 2 % mod

    else:
        DP1[i] = DP1[i-1] * 3 % mod
        DP2[i] = DP2[i-1]
ans = (DP1[x] + DP2[x]) % mod
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque

n, k = map(int, input().split())
V = list(map(int, input().split()))

ans = 0
for t in range(k//2 + 1):
    hand = deque(V[:k-t])
    rest = deque(V[k-t:])
    cur_sum = sum(hand)

    for j in range(k-t+1):
        put_back = 0
        rev_hand = sorted(hand)

        for i in range(t):
            jewel = rev_hand[i]
            if jewel < 0:
                put_back -= jewel
            else:
                break

        candidate = cur_sum + put_back
        ans = max(candidate, ans)

        to_rest = hand.pop()
        to_hand = rest.pop()
        hand.appendleft(to_hand)
        rest.appendleft(to_rest)
        cur_sum += to_hand - to_rest

print(ans)

Fixed submission:
from collections import deque

n, k = map(int, input().split())
V = list(map(int, input().split()))

ans = 0
for t in range(k//2 + 1):
    hand = deque(V[:k-t])
    rest = deque(V[k-t:])
    cur_sum = sum(hand)

    for j in range(k-t+1):
        put_back = 0
        rev_hand = sorted(hand)

        for i in range(t):
            jewel = rev_hand[i]
            if jewel < 0:
                put_back -= jewel
            else:
                break

        candidate = cur_sum + put_back
        ans = max(candidate, ans)

        to_rest = hand.pop()
        rest.appendleft(to_rest)
        to_hand = rest.pop()
        hand.appendleft(to_hand)

        cur_sum += to_hand - to_rest

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
S = [None]*m

for i in range(m):
    l, r = map(int, input().split())
    S[i] = set(range(l, r+1))

ans = S[0]
for i in range(1, m):
    ans = ans & S[i]

print(len(ans))


Fixed submission:
n, m = map(int, input().split())
S = [None]*m
L = 0
R = n

for i in range(m):
    l, r = map(int, input().split())
    L = max(l, L)
    R = min(r, R)

ans = R-L+1
if ans < 0:
    ans = 0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict
from collections import deque
input = sys.stdin.readline

new_cards = defaultdict(int)
n, m = map(int, input().split())
A = deque(sorted(list(map(int, input().split()))))

for i in range(m):
    b, c = map(int, input().split())
    new_cards[c] += b

for card, count in sorted(new_cards.items(), reverse=True):
    for i in range(count):
        if A[0] < card:
            A.append(card)
            A.popleft()

print(sum(A))


Fixed submission:
import sys
from collections import defaultdict
from collections import deque
input = sys.stdin.readline

new_cards = defaultdict(int)
n, m = map(int, input().split())
A = deque(sorted(list(map(int, input().split()))))

for i in range(m):
    b, c = map(int, input().split())
    new_cards[c] += b

for card, count in sorted(new_cards.items(), reverse=True):
    for i in range(count):
        if A[0] < card:
            A.append(card)
            A.popleft()
        else:
            print(sum(A))
            exit()

print(sum(A))

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

new_cards = defaultdict(int)
n, m = map(int, input().split())
A = deque(sorted(list(map(int, input().split()))))

for i in range(m):
    b, c = map(int, input().split())
    new_cards[c] += b

for card in sorted(new_cards.keys(), reverse=True):
    count = new_cards[card]
    for i in range(count):
        if A[0] < card:
            A.append(card)
            A.popleft()

print(sum(A))


Fixed submission:
import sys
from collections import defaultdict
from collections import deque
input = sys.stdin.readline

new_cards = defaultdict(int)
n, m = map(int, input().split())
A = deque(sorted(list(map(int, input().split()))))

for i in range(m):
    b, c = map(int, input().split())
    new_cards[c] += b

for card, count in sorted(new_cards.items(), reverse=True):
    for i in range(count):
        if A[0] < card:
            A.append(card)
            A.popleft()
        else:
            print(sum(A))
            exit()

print(sum(A))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

n = int(input())
seen = [-1]*(n+1)
path = defaultdict(dict)

for _ in range(n-1):
    u, v, w = map(int, input().split())
    path[u][v] = w
    path[v][u] = w


def dfs(seen, pos, color):
    if seen[pos] != -1:
        return
    else:
        seen[pos] = color
        change_color = 1 - color
        for nx in path[pos].keys():
            check = path[pos][nx]
            if check % 2 == 1:
                dfs(seen, nx, change_color)
            dfs(seen, nx, color)


dfs(seen, 1, 0)
for i in range(1, n+1):
    print(seen[i])


Fixed submission:
n, k = map(int, input().split())
S = list(input())
S[k-1] = S[k-1].lower()

print(''.join(S))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

n = int(input())
seen = [-1]*(n+1)
path = defaultdict(dict)

for _ in range(n-1):
    u, v, w = map(int, input().split())
    path[u][v] = w
    path[v][u] = w


def dfs(seen, pos, color):
    if seen[pos] != -1:
        return
    else:
        seen[pos] = color
        for nx in path[pos].keys():
            check = path[pos][nx]
            if check % 2 == 1:
                color = 1 - color
            dfs(seen, nx, color)


dfs(seen, 1, 0)
for i in range(1, n+1):
    print(seen[i])

Fixed submission:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

n = int(input())
seen = [-1]*(n+1)
path = defaultdict(dict)

for _ in range(n-1):
    u, v, w = map(int, input().split())
    path[u][v] = w
    path[v][u] = w


def dfs(seen, pos, color):
    if seen[pos] != -1:
        return
    else:
        seen[pos] = color
        change_color = 1 - color
        for nx in path[pos].keys():
            check = path[pos][nx]
            if check % 2 == 1:
                dfs(seen, nx, change_color)
            dfs(seen, nx, color)


dfs(seen, 1, 0)
for i in range(1, n+1):
    print(seen[i])

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

n = int(input())
seen = []
path = defaultdict(dict)

for _ in range(n-1):
    u, v, w = map(int, input().split())
    path[u][v] = w
    path[v][u] = w


def dfs(seen, pos, color):
    if seen[pos] == color:
        return
    elif seen[pos] == 1 - color:
        return False
    else:
        seen[pos] = color
        for nx in path[pos].keys():
            if path[pos][nx] % 2 == 1:
                color = 1 - color
            dfs(seen, nx, color)


for start in range(1, n + 1):
    seen = [-1] * (n+1)
    if dfs(seen, start, 0) is None:
        break

for i in range(1, n+1):
    print(seen[i])


Fixed submission:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

n = int(input())
seen = [-1]*(n+1)
path = defaultdict(dict)

for _ in range(n-1):
    u, v, w = map(int, input().split())
    path[u][v] = w
    path[v][u] = w


def dfs(seen, pos, color):
    if seen[pos] != -1:
        return
    else:
        seen[pos] = color
        change_color = 1 - color
        for nx in path[pos].keys():
            check = path[pos][nx]
            if check % 2 == 1:
                dfs(seen, nx, change_color)
            dfs(seen, nx, color)


dfs(seen, 1, 0)
for i in range(1, n+1):
    print(seen[i])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
field = []
todo = deque([])

for y in range(h):
    text = input()
    field.append(text)
    for x in range(w):
        if text[x] == '#':
            todo.append([y, x])

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]

seen = [[None] * w for _ in range(h)]

for y, x in todo:
    seen[y][x] = 0

while todo:
    y, x = todo.popleft()

    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]

        if ny < 0 or h <= ny or nx < 0 or w <= nx:
            continue
        elif seen[ny][nx] is not None:
            continue
        else:
            seen[ny][nx] = seen[y][x] + 1
            todo.append([ny, nx])

    if not todo:
        print(seen[y][x])


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

h, w = map(int, input().split())
field = []
todo = deque([])

for y in range(h):
    text = input()
    field.append(text)
    for x in range(w):
        if text[x] == '#':
            todo.append([y, x])

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]

seen = [[None] * w for _ in range(h)]

for y, x in todo:
    seen[y][x] = 0

while todo:
    y, x = todo.popleft()

    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]

        if ny < 0 or h <= ny or nx < 0 or w <= nx:
            continue
        elif seen[ny][nx] is not None:
            continue
        else:
            seen[ny][nx] = seen[y][x] + 1
            todo.append([ny, nx])

    if not todo:
        print(seen[y][x])