Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):

S = input()
Q = int(input())
Front_flag = 1

for i in range(Q):
    Query = tuple(input().split())
    if len(Query) == 1:
        Front_flag = 1 - Front_flag
    else:
        a, b, c = Query
        if (Front_flag + int(b)) % 2 == 1:
            S += c
        else:
            S = c + S
if Front_flag:
    print(S)
else:
    print(S[::-1])


Fixed submission:
from collections import deque
S = input()
que = deque()
que.append(S)
Q = int(input())
Front_flag = 1

for i in range(Q):
    Query = tuple(input().split())
    if len(Query) == 1:
        Front_flag = 1 - Front_flag
    else:
        a, b, c = Query
        if (Front_flag + int(b)) % 2 == 1:
            que.append(c)
        else:
            que.appendleft(c)

ans = ''.join(que)
if Front_flag:
    print(ans)
else:
    print(ans[::-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
S = sys.stdin.readline().strip()
Q = int(sys.stdin.readline().strip())

for i in range(Q):
    Query = sys.stdin.readline()
    if len(Query) == 2:
        S = S[::-1]
    else:
        a, b, c = Query.split()
        if b == '1':
            S = c + S
        else:
            S += c
print(S)

Fixed submission:
from collections import deque
S = input()
que = deque()
que.append(S)
Q = int(input())
Front_flag = 1

for i in range(Q):
    Query = tuple(input().split())
    if len(Query) == 1:
        Front_flag = 1 - Front_flag
    else:
        a, b, c = Query
        if (Front_flag + int(b)) % 2 == 1:
            que.append(c)
        else:
            que.appendleft(c)

ans = ''.join(que)
if Front_flag:
    print(ans)
else:
    print(ans[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque, Counter

N, M, K = map(int, input().split())
Friend = [[]for i in range(N)]
Block = [[] for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Friend[a].append(b)
    Friend[b].append(a)

for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Block[c].append(d)
    Block[d].append(c)
Group = [0] * N
Q = deque()
for i in range(1, N):
    if 0 not in Group:
        break
    else:
        z = Group.index(0)
        Group[z] = i
        Q.append(z)
        while len(Q) > 0:
            now = Q.popleft()
            for j in Friend[now]:
                if Group[j] != 0:
                    continue
                else:
                    Group[j] = i
                    Q.append(j)
G_ = Counter(Group)
for i in range(N):
    ans = G_[Group[i]] - 1
    for j in Friend[i]:
        if Group[i] == Group[j]:
            ans -= 1
    for j in Block[i]:
        if Group[i] == Group[j]:
            ans -= 1
    print(ans, end=' ')


Fixed submission:
# Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True


def same(x, y):
    return find(x) == find(y)


def size(x):
    return -par[find(x)]


N, M, K = map(int, input().split())
Friend = [[] for _ in range(N)]

par = [-1] * N
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)
    Friend[a].append(b)
    Friend[b].append(a)

Block = [[] for _ in range(N)]
for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Block[c].append(d)
    Block[d].append(c)

Ans = []
for i in range(N):
    ans = size(i) - 1
    ans -= len(Friend[i])
    for b in Block[i]:
        if same(i, b):
            ans -= 1
    Ans.append(str(ans))

print(' '.join(Ans))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split())
flag = True
for a in A:
    if a % 2 == 0:
        if a % 3 == 0 or a % 5 == 0:
        continue
    flag = False

if flag:
    print('APPROVED')
else:
    print('DENIED')




Fixed submission:
N = int(input())
A = list(map(int, input().split()))
flag = True
for a in A:
    if a % 2 == 0:
        if a % 3 == 0 or a % 5 == 0:
            continue
        else:
            flag = False

if flag:
    print('APPROVED')
else:
    print('DENIED')
Buggy python submission (verdict: Runtime Error):
n = len(input())
print('x' + n)

Fixed submission:
n = len(input())
print('x' * n)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
p = list(map(int, input().split()))

ans = 0
for i in range(N - K + 1):
    a = 0
    for j in range(K):
        a += (p[i+j] + 1) / 2
    ans = max(ans,a)

print(ans)

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

ans = 0
for i in range(K):
    ans += p[i]
    tt = ans
for i in range(K,N):
    tt = tt+p[i]-p[i-K]
    ans = max(ans, tt)
print((ans + K)/2)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from copy import deepcopy
H, W = map(int, input().split())
maze = [[]for i in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        maze[i].append(S[j])

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
ans = 0
Q = deque()

for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                if (sx == gx) and (sy == gy):
                    continue
                if (maze[sy][sx] == '#') or (maze[gy][gx] == '#'):
                    continue
                mazenow = deepcopy(maze)
                Q.clear()
                Q.append((sy, sx))
                mazenow[sy][sx] = 0
                flag = True
                while (len(Q) >= 0) and flag:
                    y, x = Q.popleft()
                    for i in range(4):
                        ny = y + dy[i]
                        nx = x + dx[i]
                        if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W):
                            continue
                        elif (ny == gy) and (nx == gx):
                            ans = max(ans, mazenow[y][x] + 1)
                            flag = False
                            break
                        elif mazenow[ny][nx] == '.':
                            mazenow[ny][nx] = mazenow[y][x] + 1
                            Q.append((ny, nx))

print(ans)





Fixed submission:
from collections import deque
from copy import deepcopy
H, W = map(int, input().split())
maze = [[]for i in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        maze[i].append(S[j])

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
ans = 0
Q = deque()

for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '#':
            continue
        mazenow = deepcopy(maze)
        Q.clear()
        Q.append((sy, sx))
        mazenow[sy][sx] = 0
        flag = True
        max_maze_now = 0
        while len(Q) > 0:
            y, x = Q.popleft()
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W):
                    continue
                elif mazenow[ny][nx] == '.':
                    mazenow[ny][nx] = mazenow[y][x] + 1
                    max_maze_now = max(max_maze_now, mazenow[ny][nx])
                    Q.append((ny, nx))
        ans = max(max_maze_now, ans)

print(ans)
Buggy python submission (verdict: Runtime Error):
import math
A, B = map(int, input().split())


def lcm(x, y):
    return x * y // math.gcd(x, y)


print(lcm(A, B))


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


def lcm(x, y):
    return x * y // fractions.gcd(x, y)


print(lcm(A, B))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = 0
mod = 10**9 + 7
for i in range(N-1):
    for j in range(i+1, N):
        ans += (A[i] ^ A[j])
        ans %= mod
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
K = [0] * 60
ans = 0
mod = 7 + 10**9
for i in A:
    for j in range(60):
        if (i >> j) & 1 == 1:
            K[j] += 1

for i, j in enumerate(K):
    ans += (2**i) * j * (N - j)
    ans %= mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = 0
mod = 10**9 + 7
for i in range(N-1):
    for j in range(i+1, N):
        ans += (A[i] ^ A[j])
        ans %= mod
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
K = [0] * 60
ans = 0
mod = 7 + 10**9
for i in A:
    for j in range(60):
        if (i >> j) & 1 == 1:
            K[j] += 1

for i, j in enumerate(K):
    ans += (2**i) * j * (N - j)
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
end = A[-1] * F[0] + 1
start = -1


def decision(n):
    k = K
    for a, f in zip(A, F):
        while a * f > n:
            a -= 1
            k -= 1
            if k < 0:
                return False
    return True

def calc():
    e = end
    s = start
    while e - s > 1:
        mid = (e + s)//2
        if decision(mid):
            e = mid
        else:
            s = mid
    return e


print(calc())




Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)
end = A[-1] * F[0] + 1
start = -1


def decision(n):
    k = K
    for a, f in zip(A, F):
        if a * f > n:
            k -= a - n // f
        if k < 0:
            return False
    return True

def calc():
    e = end
    s = start
    while e - s > 1:
        mid = (e + s)//2
        if decision(mid):
            e = mid
        else:
            s = mid
    return e


print(calc())
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())
print(max(0, A - 2 * B)

Fixed submission:
A, B = map(int, input().split())
print(max(0, A - 2 * B))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N = int(input())
L = np.array(list(map(int, input().split())))

L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ans += np.count_nonzero((L[j] < L) & (L < L[i] + L[j]))

print(ans)





Fixed submission:
import bisect

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

L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        index = bisect.bisect_right(L, L[i] + L[j]-1)
        ans += index - j - 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N = int(input())
L = np.array(list(map(int, input().split())))

L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if (L[j] - L[i] < L[k]) & (L[k] < L[j] + L[i]):
                ans += 1
            elif L[j] + L[i] < L[k]:
                break

print(ans)


Fixed submission:
import bisect

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

L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        index = bisect.bisect_right(L, L[i] + L[j]-1)
        ans += index - j - 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
from collections import defaultdict
A, B = map(int, input().split())
C = fractions.gcd(A, B)
D = set([1])
c = C
for i in range(2, C+1):
    while c % i == 0:
        D.add(i)
        c //= i

print(len(D))


Fixed submission:
import fractions
from collections import defaultdict
A, B = map(int, input().split())
C = fractions.gcd(A, B)
c = C

if c == 1:
    print(1)
    exit()


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


print(len(factorization(c))+1)

Buggy python submission (verdict: Runtime Error):
import fractions
from collections import defaultdict
A, B = map(int, input().split())
C = fractions.gcd(A, B)
D = set([1])
c = C
for i in range(2, C1):
    while c % i == 0:
        D.add(i)
        c //= i

print(len(D))


Fixed submission:
import fractions
from collections import defaultdict
A, B = map(int, input().split())
C = fractions.gcd(A, B)
c = C

if c == 1:
    print(1)
    exit()


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


print(len(factorization(c))+1)

Buggy python submission (verdict: Runtime Error):
import math
from collections import defaultdict
A, B = map(int, input().split())
C = math.gcd(A, B)
D = set([1])
c = C
for i in range(2, C//2+1):
    while c % i == 0:
        D.add(i)
        c //= i

print(len(D))


Fixed submission:
import fractions
from collections import defaultdict
A, B = map(int, input().split())
C = fractions.gcd(A, B)
c = C

if c == 1:
    print(1)
    exit()


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


print(len(factorization(c))+1)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
Cost = []
Key = []
for i in range(M):
    a, b = map(int, input().split())
    Cost.append(a)
    C_ = list(map(int, input().split()))
    C = 0
    for c in C_:
        C += (1 << (c - 1))
    Key.append(C)
ans = float('inf')
for i in range(1 << M):
    a = 0
    X = 0
    for j in range(M):
        if (i >> j) & 1 == 1:
            a += Cost[j]
            X |= Key[j]
    if X == 2 ** N - 1:
        ans = min(ans, a)

if ans == float('inf'):
    ans = -1
print(ans)




Fixed submission:
N, M = map(int, input().split())
Cost = []
Key = []
for i in range(M):
    a, b = map(int, input().split())
    Cost.append(a)
    C_ = list(map(int, input().split()))
    C = 0
    for c in C_:
        C |= (1 << (c - 1))
    Key.append(C)
DP = [float('inf')] * (1 << N)
DP[0] = 0

for cost, key in zip(Cost, Key):
    D = DP[:]
    for i, d in enumerate(DP):
        if d == float('inf'):
            continue
        D[i|key] = min(D[i|key], d + cost)
    DP = D

if DP[-1] == float('inf'):
    print(-1)
else:
    print(DP[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ans = 0

for i in range(N):
    ans += i
print(ans)

Fixed submission:
N = int(input())
print((N)*(N-1) //2)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

S = input()
S2 = S + S
T = input()
SC = Counter(S)
TC = Counter(T)

N = len(S)
ans = 0
now = 0

for t in TC.keys():
    if t not in SC:
        print(-1)
        exit()

for t in T:
    i = S2[now: now + N].find(t)
    ans += i + 1
    now += i + 1
    now %= N

print(ans)

Fixed submission:
from collections import Counter
import bisect


S = input()
S = S + S
T = input()
SC = Counter(S)
TC = Counter(T)
A = [[] for _ in range(150)]

for t in TC.keys():
    if t not in SC:
        print(-1)
        exit()

for i, s in enumerate(S):
    A[ord(s)].append(i)

N = len(S) // 2
ans = 0
now = -1

for t in T:
    At = A[ord(t)]
    x = bisect.bisect_left(At, now)
    now = At[x]
    if now + 1 >= N:
        ans += 1
    now += 1
    now %= N

print(ans * N + now)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N = int(input())
S = [[]for _ in range(10)]
for _ in range(N):
    s = input()
    S[len(s)-1].append(Counter(s))

ans = 0
for _ in range(10):
    for i in range(len(S[_])):
        for j in range(i+1, len(S[_])):
            if S[_][i] == S[_][j]:
                ans += 1
print(ans)

Fixed submission:
from collections import defaultdict

N = int(input())
S = defaultdict(int)
ans = 0
for _ in range(N):
    s = input()
    sl = []
    for n in s:
        sl.append(n)
    sl.sort()
    s = ''.join(sl)
    S[s] += 1

for value in S.values():
    ans += value * (value-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = tuple(map(int, input().split()))
 
ans = 0
for i in range(N):
    for j in range(i+1, N+1):
        if sum(A[i:j]) >= K:
            ans += N - j + 1
            break
 
print(ans)

Fixed submission:
X, A = map(int, input().split())
if X < A:
    print(0)
else:
    print(10)
Buggy python submission (verdict: Runtime Error):
from collections import Counter

N = int(input())
M = [tuple(map(int, input().split())) for _ in range(N)]
Map = []
for i in range(N):
    x1, y1 = M[i]
    for j in range(i + 1, N):
        x2, y2 = M[j]
        Map.append((x2 - x1, y2 - y1))
MapC = Counter(Map)
print(N - MapC.most_common(1)[0][1])





Fixed submission:
from collections import Counter


N = int(input())
M = [tuple(map(int, input().split())) for _ in range(N)]
Map = []
if N == 1:
    print(1)
    exit()
for i in range(N):
    x1, y1 = M[i]
    for j in range(N):
        if i == j:
            continue
        x2, y2 = M[j]
        Map.append((x2 - x1, y2 - y1))
MapC = Counter(Map)
print(N - MapC.most_common(1)[0][1])
Buggy python submission (verdict: Runtime Error):
from collections import deque

N, M = map(int, input().split())
Broken = deque()
for _ in range(M):
    broken = int(input())
    Broken.append(broken)

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

nex = Broken.popleft()

for i in range(1, N+1):
    if i == nex:
        if len(Broken) >0:
            nex = Broken.popleft()
        continue
    DP[i] = DP[i-1] + DP[i-2]
    DP[i] %= 10**9 + 7
print(DP[N])



Fixed submission:
N, M = map(int, input().split())
Broken = set([])
for _ in range(M):
    broken = int(input())
    Broken.add(broken)

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

for i in range(1, N+1):
    if i in Broken:
        continue
    DP[i] = DP[i-1] + DP[i-2]
    DP[i] %= 10**9 + 7
print(DP[N])

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

N, M = map(int, input().split())
Broken = deque()
for _ in range(M):
    broken = int(input())
    Broken.append(broken)

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

nex = Broken.popleft()

for i in range(1, N+1):
    if i == nex:
        if len(Broken) >0:
            nex = Broken.popleft()
        continue
    DP[i] = DP[i-1] + DP[i-2]
    DP[i] %= 10**9 + 7
print(DP[N])



Fixed submission:
N, M = map(int, input().split())
Broken = set([])
for _ in range(M):
    broken = int(input())
    Broken.add(broken)

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

for i in range(1, N+1):
    if i in Broken:
        continue
    DP[i] = DP[i-1] + DP[i-2]
    DP[i] %= 10**9 + 7
print(DP[N])

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
Broken = []
for _ in range(M):
    broken = int(input())
    Broken.append(broken)

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

for i in range(1, N+1):
    if i in Broken:
        continue
    DP[i] = DP[i-1] + DP[i-2]
    DP[i] %= 10**9 + 7
print(DP[N])



Fixed submission:
N, M = map(int, input().split())
Broken = set([])
for _ in range(M):
    broken = int(input())
    Broken.add(broken)

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

for i in range(1, N+1):
    if i in Broken:
        continue
    DP[i] = DP[i-1] + DP[i-2]
    DP[i] %= 10**9 + 7
print(DP[N])

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
Broken = []
for _ in range(M):
    broken = int(input())
    Broken.append(broken)

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

for i in range(1, N+1):
    if i in Broken:
        continue
    DP[i] = DP[i-1] + DP[i-2]
    DP[i] %= 10**9 + 7
print(DP[N])



Fixed submission:
N, M = map(int, input().split())
Broken = set([])
for _ in range(M):
    broken = int(input())
    Broken.add(broken)

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

for i in range(1, N+1):
    if i in Broken:
        continue
    DP[i] = DP[i-1] + DP[i-2]
    DP[i] %= 10**9 + 7
print(DP[N])
Buggy python submission (verdict: Runtime Error):
# include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<tuple<string, int, int>> Book(N, tuple<string, int, int>());
  
  for (int i = 0; i < N; i++) {
    string s;
    int a;
    cin >> s >> a;
    Book.at(i) = make_tuple(s, 100-a, i);
  }
  
  sort(Book.begin(), Book.end());
  
  for (int i = 0; i < N; i++) {
    cout << get<2>(Book.at(i)) + 1<< endl;
  }
}


Fixed submission:
N = int(input())
Book = [0] * N
for i in range(N):
    s,q = input().split()
    p = int(q)
    Book[i] = (s, 100-p, i)

Book.sort()

for i in range(N):
    print(Book[i][2]+1)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
Alist = list(map(int, input().split()))
BClist = []
for i in range(M):
    B, C = map(int, input().split())
    BClist.append([B, C])
Alist.sort()
BClist.sort(reverse= True, key=lambda x: x[1])

num = 0
flag = True
for i in range(M):
    if not flag:
        break
    for j in range(BClist[i][0]):
        if num > len(Alist):
            flag = False
            break
        elif BClist[i][1] > Alist[num]:
            Alist[num] = BClist[i][1]
            num += 1
        elif BClist[i][1] <= Alist[num]:
            flag = False
            break

print(sum(Alist))

Fixed submission:
N, M = map(int, input().split())
Alist = list(map(int, input().split()))
BClist = []
for i in range(M):
    B, C = map(int, input().split())
    BClist.append([B, C])
Alist.sort()
BClist.sort(reverse=True, key=lambda x: x[1])

num = 0
flag = True
for i in range(M):
    if not flag:
        break
    for j in range(BClist[i][0]):
        if num >= len(Alist):
            flag = False
            break
        elif BClist[i][1] > Alist[num]:
            Alist[num] = BClist[i][1]
            num += 1
        elif BClist[i][1] <= Alist[num]:
            flag = False
            break

print(sum(Alist))