Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
gcd = m//n
while n*gcd != m:
  gcd = M//n
  n = 1 + (M-1)//gcd
print(gcd)

Fixed submission:
from itertools import product
from collections import Counter
from functools import reduce
import operator
num_product = lambda it: reduce(operator.mul,it,1)

# 素因数分解
def prime_factors(n):
  i = 2
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      yield i
  if n > 1:
    yield n



N,M = map(int,input().split())
P = tuple(tuple(p**i for i in range(d+1)) for p,d in Counter(prime_factors(M)).items())
def it():
  for nums in product(*P):
    t = num_product(nums)
    yield t
print(max(t for t in it() if t*N <= M))

Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
gcd = m//n
while n*gcd != m:
  n = 1 + (M-1)//gcd
  gcd = M//n
print(gcd)

Fixed submission:
from itertools import product
from collections import Counter
from functools import reduce
import operator
num_product = lambda it: reduce(operator.mul,it,1)

# 素因数分解
def prime_factors(n):
  i = 2
  while i * i <= n:
    if n % i:
      i += 1
    else:
      n //= i
      yield i
  if n > 1:
    yield n



N,M = map(int,input().split())
P = tuple(tuple(p**i for i in range(d+1)) for p,d in Counter(prime_factors(M)).items())
def it():
  for nums in product(*P):
    t = num_product(nums)
    yield t
print(max(t for t in it() if t*N <= M))
Buggy python submission (verdict: Runtime Error):
from itertools import tee
N = int(input())
w0, w1 = tee((int(input()) for _ in range(N)), 2)
next(w1)
for a,b in zip(w0,w1):
  if a[-1] != b[0]:
    print('No')
    break
else:
  print('Yes')

Fixed submission:
from itertools import tee
N = int(input())
w0, w1 = tee((input() for _ in range(N)), 2)

words = {next(w1)}
flag = 'Yes'
for a,b in zip(w0,w1):
  if a[-1] != b[0] or b in words:
    flag = 'No'
  words.add(b)

print(flag)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7
S = input()
res = 0
dpn = 1
dp0 = 0 # a
dp1 = 0 # ab

for c in S:
    if c == 'A':
        dp0 += dpn
    elif c == 'B':
        dp1 += dp0
    elif c == 'C':
        res += dp1
    else:
        dp0,dp1,res = dp0*3+dpn,dp1*3+dp0,res*3+dp1
        dpn *= 3

    dp1 %= MOD
    res %= MOD
print(res)


Fixed submission:
MOD = 10**9 + 7
S = input()
res = 0
dpn = 1
dp0 = 0 # a
dp1 = 0 # ab

for c in S:
    if c == 'A':
        dp0 += dpn
    elif c == 'B':
        dp1 += dp0
    elif c == 'C':
        res += dp1
    else:
        dp0,dp1,res = dp0*3+dpn,dp1*3+dp0,res*3+dp1
        dpn *= 3
    dpn %= MOD
    dp0 %= MOD
    dp1 %= MOD
    res %= MOD
print(res)
Buggy python submission (verdict: Runtime Error):
MOD = 998244353

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

A,B = sorted((A,B))

if (A+B)*N < K:
  print(0)
  exit()

# tabulate combinations



# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


memo = [0]*(N+1)
memo[0] = memo[N] = 1
for k in range(1,N//2+1):
  v = memo[k-1]*(N-k+1)*modinv(k,MOD)
  v %= MOD
  memo[k] = memo[N-k] = v

cnt = 0

for b in range((max(0,K-N*A)-1)//B+1, (K-1)//B+1):
  a = (K-b*B)//A
  if a*A+b*B == K:
    cnt += memo[a]*memo[b]
    cnt %= MOD

print(cnt)

Fixed submission:
MOD = 998244353

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

A,B = sorted((A,B))

if (A+B)*N < K:
  print(0)
  exit()

# tabulate combinations



# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


memo = [0]*(N+1)
memo[0] = memo[N] = 1
for k in range(1,N//2+1):
  v = memo[k-1]*(N-k+1)*modinv(k,MOD)
  v %= MOD
  memo[k] = memo[N-k] = v

cnt = 0

for b in range(N+1):
  a = (K-b*B)//A
  if 0 <= a <= N and a*A+b*B == K:
    cnt += memo[a]*memo[b]
    cnt %= MOD

print(cnt)
Buggy python submission (verdict: Runtime Error):
N = int(input())
L,R = [None]*N,[None]*N
for i in range(N):
  L[i],R[i] = map(int,input().split())
L.sort(reverse=True)
R.sort()

def it():
  for l,r in zip(L,R):
    if r < l
      yield 2*(l-r)
    else:
      return

print(sum(it()))

Fixed submission:
N = int(input())

intervals = list(tuple(map(int,input().split())) for _ in range(N))

L = sorted(((l,i) for i,(l,r) in enumerate(intervals)))
R = sorted(((r,i) for i,(l,r) in enumerate(intervals)), reverse=True)

def helper(L,R,turn):
  used = [False]*(N+1)
  used[N] = True

  x = 0
  cost = 0
  while True:
    A = [L,None,R][turn+1]

    i = N
    while used[i]:
      y,i = A.pop()

    if turn*(y-x) < 0:
      cost += abs(x-y)
      x = y
    else:
      break
    turn *= -1
  cost += abs(x)
  return cost

print(max(helper(L.copy(), R.copy(), t) for t in [-1,1]))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
import sys
N = int(input())

grid = sys.stdin.read().split('\n')


res = 0
for d in range(N):
  for x,y in combinations(range(N), 2):
    if grid[(x+d)%N][y] != grid[(y+d)%N][x]:
      break
  else:
    res += 1
print(res*N)

Fixed submission:
from itertools import combinations
N = int(input())
grid = tuple(tuple(input()) for _ in range(N))

res = 0
for d in range(N):
  for x,y in combinations(range(N), 2):
    if grid[(x+d)%N][y] != grid[(y+d)%N][x]:
      break
  else:
    res += 1
print(res*N)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())

from collections import defaultdict
E = defaultdict(list)

for _ in range(M):
  l,r,d = map(int,input().split())
  E[l-1].append((r-1,d))
  E[r-1].append((l-1,-d))

unvisited = set(range(N))
locations = [None]*N
while unvisited:
  s = next(iter(unvisited))
  locations[s] = 0
  stack = [s]

  while stack:
    v = stack.pop()
    unvisited.discard(v)
    p = locations[v]

    for u,d in E[v]:
      if locations[u] is None:
        locations[u] = p+d
        stack.append(u)
      elif locations[u] != p+d:
        print('No')
        exit()

print('Yes')


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

from collections import defaultdict
E = [list() for _ in range(N)]

for _ in range(M):
  l,r,d = map(int,input().split())
  E[l-1].append((r-1,d))
  E[r-1].append((l-1,-d))

locations = [None]*N

for s in range(N):
  if locations[s] is None:
    locations[s] = 0
    stack = [s]

    while stack:
      v = stack.pop()
      p = locations[v]

      for u,d in E[v]:
        if locations[u] is None:
          locations[u] = p+d
          stack.append(u)
        elif locations[u] != p+d:
          print('No')
          exit()


print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
if __debug__:
  i = 0
  while True:
    i *= 2

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

print(2**M*(1900*M+100*(N-M)))

Fixed submission:

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

print(2**M*(1900*M+100*(N-M)))
Buggy python submission (verdict: Time Limit Exceeded):
# どちらか必ずa_Nのカードを持つ
import sys
from functools import lru_cache

sys.setrecursionlimit(4000)

N,Z,W = map(int,input().split())
A = list(map(int,input().split()))
A.reverse()

# turn: true->X, false->Y
BOTTOM = A[0]

@lru_cache(maxsize=2000000)
def rec_X(i,y):
  return max(abs(BOTTOM-y),max((rec_Y(j,A[j]) for j in range(1,i)), default=0))

@lru_cache(maxsize=2000000)
def rec_Y(i,x):
  return min(abs(BOTTOM-x),min((rec_X(j,A[j]) for j in range(1,i)), default=float('inf')))

print(rec_X(N,W))

Fixed submission:
# どちらか必ずa_Nのカードを持つ

N,Z,W = map(int,input().split())
A = list(map(int,input().split()))
A.reverse()
A.append(W)

BOTTOM = A[0]

M = float('inf')
m = 0

for a in A[1:]:
  x = abs(BOTTOM-a)
  t = max(x,m)
  s = min(x,M)
  M = min(M,t)
  m = max(m,s)

print(t)

Buggy python submission (verdict: Time Limit Exceeded):
# どちらか必ずa_Nのカードを持つ
import sys
from functools import lru_cache

sys.setrecursionlimit(4000)

N,Z,W = map(int,input().split())
A = list(map(int,input().split()))
A.reverse()

# turn: true->X, false->Y

@lru_cache(maxsize=4000000)
def rec(i,x,y,turn):
  if i == 0:
    return abs(x-y)
  if turn:
    return max(rec(j,A[j],y,False) for j in range(i))
  else:
    return min(rec(j,x,A[j],True) for j in range(i))

print(rec(N,Z,W,True))

Fixed submission:
# どちらか必ずa_Nのカードを持つ

N,Z,W = map(int,input().split())
A = list(map(int,input().split()))
A.reverse()
A.append(W)

BOTTOM = A[0]

M = float('inf')
m = 0

for a in A[1:]:
  x = abs(BOTTOM-a)
  t = max(x,m)
  s = min(x,M)
  M = min(M,t)
  m = max(m,s)

print(t)
Buggy python submission (verdict: Runtime Error):
from itertools import chain,repeat
K,N = map(int,input().split())

def dec(seq):
  if seq[-1] == 1:
    seq.pop()
  else:
    seq[-1] -= 1
    if len(seq) < N:
      seq += list(repeat(K,N-len(seq)))
  return seq

if K % 2 == 0:
  print(' '.join(chain((K-1,),repeat(K,N-1))))
else:
  seq = list(repeat(K//2+1,N))
  d = (N-1)//2
  for _ in range(d+1):
    seq = dec(seq)
  print(' '.join(map(str, seq)))


Fixed submission:
from itertools import chain,repeat
K,N = map(int,input().split())

def solve():

  if K % 2 == 0:
    return ' '.join(map(str, chain((K//2,),repeat(K,N-1))))
  else:
    seq = [K//2+1]*N
    d = N//2
    for _ in range(d):
      if seq[-1] == 1:
        seq.pop()
      else:
        seq[-1] -= 1
        seq.extend(repeat(K,N-len(seq)))
    return ' '.join(map(str, seq))

def naive():
  from itertools import product
  s = sorted(chain.from_iterable(product(range(1,K+1),repeat=i) for i in range(1,N+1)))
  return ' '.join(map(str, s[(len(s)-1)//2]))

print(solve())
# print(naive())

Buggy python submission (verdict: Runtime Error):
from itertools import chain,repeat
K,N = map(int,input().split())

def dec(seq):
  if seq[-1] == 1:
    seq.pop()
  else:
    seq[-1] -= 1
    if len(seq) < N:
      seq += list(repeat(K,N-len(seq)))
  return seq

if K % 2 == 0:
  print(' '.join(chain((K-1,),repeat(K,N-1))))
else:
  seq = list(repeat(K//2+1,N))
  d = (N-1)//2
  for _ in range(d):
    seq = dec(seq)
  print(' '.join(map(str, seq)))


Fixed submission:
from itertools import chain,repeat
K,N = map(int,input().split())

def solve():

  if K % 2 == 0:
    return ' '.join(map(str, chain((K//2,),repeat(K,N-1))))
  else:
    seq = [K//2+1]*N
    d = N//2
    for _ in range(d):
      if seq[-1] == 1:
        seq.pop()
      else:
        seq[-1] -= 1
        seq.extend(repeat(K,N-len(seq)))
    return ' '.join(map(str, seq))

def naive():
  from itertools import product
  s = sorted(chain.from_iterable(product(range(1,K+1),repeat=i) for i in range(1,N+1)))
  return ' '.join(map(str, s[(len(s)-1)//2]))

print(solve())
# print(naive())
Buggy python submission (verdict: Runtime Error):
print(‘Yes’ if ‘AC’ in input() else ‘No’)

Fixed submission:
print('Yes' if 'AC' in input() else 'No')
Buggy python submission (verdict: Time Limit Exceeded):
s = tuple(map(lambda c: ord(c)-ord('a'),input()))

from collections import defaultdict

dp = defaultdict(lambda: len(s))
dp[0] = 0


def it(x):
  for i in range(26):
    yield x ^ (1 << i)

v = 0
for c in s:
  v ^= 1 << c
  dp[v] = min(dp[v],min(dp[i] for i in it(v))+1)

print(dp[v] + (v == 0))

Fixed submission:
from itertools import accumulate
from operator import xor

s = tuple(map(lambda c: 1 << (ord(c)-ord('a')),input()))
L = len(s)
dp = dict()
dp[0] = 0

for v in accumulate(s, xor):
  dp[v] = min(dp.get(v,L), min(dp.get(v ^ (1 << i), L) for i in range(26))+1)

print(dp[v] + (v == 0))
Buggy python submission (verdict: Runtime Error):
a,b,c = map(int,input().split())

L = [[0] for _ in range(a)] + [[1] for _ in range(b)] + [[2] for _ in range(c)]
while len(L) > 1:
  L[0] += L.pop()
  L.sort()
print(''.join(('a','b','c')[i] for i in L[0]))

Fixed submission:
print(input()[:-8])
Buggy python submission (verdict: Time Limit Exceeded):

import fractions as fr
from itertools import count

N = int(input())

for a in count(1):
  if (a*N)%(3*a-1) == 0:
    h = N
    n = a*N
    w = (a*N)//(3*a-1)
    print(h,n,w)
    break

Fixed submission:

import fractions as fr
from itertools import count,product
from math import ceil

N = int(input())

if N%2 == 0:
  print(N,N,N//2)
  exit()

for h in range(1,3501):
  if 4*h > N:
    a = N*h//(4*h-N)+1
    b = 3501
  else:
    a = 1
    b = N*h//(4*h-N)+1
  for n in range(a,b):
    if (N*h*n)%(4*h*n-N*h-N*n) == 0:
      print(h,n,(N*h*n)//(4*h*n-N*h-N*n))
      exit()
Buggy python submission (verdict: Runtime Error):
h,w,d = map(int,input().split())
d //= 2
c1 = ('R','Y')
c2 = ('G','B')

l1 = []
i = 0
m = 0
while i < w:
  l1.append(c1[m])
  i+=1
  if i%d == 0:
    m = 1-m

l2 = []
i = 0
m = 0
while i < w:
  l2.append(c2[m])
  i+=1
  if i%d == 0:
    m = 1-m

c1 = ''.join(l1)
c2 = ''.join(l2)

for i in range(h):
  if i%(2*d) < d:
    print(c1)
  else:
    print(c2)

Fixed submission:
h,w,d = map(int,input().split())
c = ('R','Y','G','B')

from itertools import product
for i in range(h):
  line = []
  for j in range(w):
    x = (i-j)%(2*d) >= d
    y = (i+j)%(2*d) >= d
    line.append(c[2*x+y])
  print(''.join(line))
Buggy python submission (verdict: Runtime Error):
a,b,c,d,e,f = map(int,input().split())


from itertools import product
water = set()

for i,j in product(range(f//(a*100)+2),range(f//(100*b)+2)):
  n = a*i+b*j
  if n <= f:
    water.add(n)

water = sorted(water)

salt = set()

for i,j in product(range(f//c+2),range(f//d+2)):
  n = c*i+d*j
  if n <= f:
    salt.add(n)

from bisect import bisect_left

bs,bw = 0,1
salt = sorted(salt)
for s in salt:
  w = s/e
  i = bisect_left(water,w)
  w = water[i]
  if 100*w + s > f:
    break
  if bs*w < bw*s:
    bs,bw = s,w

print(bs+100*bw,bs)


Fixed submission:
a,b,c,d,e,f = map(int,input().split())


from itertools import product
water = set()

for i,j in product(range(f//(a*100)+2),range(f//(100*b)+2)):
  n = a*i+b*j
  if n <= f:
    water.add(n)

water = sorted(water)

salt = set()

for i,j in product(range(f//c+2),range(f//d+2)):
  n = c*i+d*j
  if n <= f:
    salt.add(n)

salt = sorted(salt)

from bisect import bisect_left



bs,bw = 0,min(a,b)
for s in salt:
  w = s/e
  i = bisect_left(water,w)
  if i >= len(water):
    break
  w = water[i]
  if 100*w + s > f:
    break
  if bs*w < bw*s:
    bs,bw = s,w

print(bs+100*bw,bs)

Buggy python submission (verdict: Runtime Error):
a,b,c,d,e,f = map(int,input().split())


from itertools import product
water = set()

for i,j in product(range(f//(a*100)+1),range(f//(100*b)+1)):
  n = a*i+b*j
  if n <= f:
    water.add(n)

water = sorted(water)

salt = set()

for i,j in product(range(f//c+1),range(f//d+1)):
  n = c*i+d*j
  if n <= f:
    salt.add(n)

from bisect import bisect_left

bs,bw = 0,1
salt = sorted(salt)
for s in salt:
  w = s/e
  i = bisect_left(water,w)
  w = water[i]
  if 100*w + s > f:
    break
  if bs*w < bw*s:
    bs,bw = s,w

print(bs+100*bw,bs)


Fixed submission:
a,b,c,d,e,f = map(int,input().split())


from itertools import product
water = set()

for i,j in product(range(f//(a*100)+2),range(f//(100*b)+2)):
  n = a*i+b*j
  if n <= f:
    water.add(n)

water = sorted(water)

salt = set()

for i,j in product(range(f//c+2),range(f//d+2)):
  n = c*i+d*j
  if n <= f:
    salt.add(n)

salt = sorted(salt)

from bisect import bisect_left



bs,bw = 0,min(a,b)
for s in salt:
  w = s/e
  i = bisect_left(water,w)
  if i >= len(water):
    break
  w = water[i]
  if 100*w + s > f:
    break
  if bs*w < bw*s:
    bs,bw = s,w

print(bs+100*bw,bs)
Buggy python submission (verdict: Runtime Error):
import os 
a,b = os.read(0,100).split(b' ')
a = int(a.decode())
b = int(b.decode())
print(max(a-b,0))
os.write(1,' '.join(str(a),str(b)).encode())

Fixed submission:
import os 
a,b = os.read(0,100).split(b' ')
a = int(a.decode())
b = int(b.decode())
print(max(a-b,0))
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = set()
q = [0,0]
import heaps as hq
for a in map(int, input().split()):
  if a > q[0]:
    if a in s:
      del s[a]
      hq.heapreplace(q, a)
    else:
      s.add(a)

print(q[0]*q[1])

Fixed submission:
n = int(input())
s = set()
q = [0,0]
import heapq as hq
for a in map(int, input().split()):
  if a > q[0]:
    try:
      s.remove(a)
      hq.heapreplace(q, a)
    except:
      s.add(a)

print(q[0]*q[1])
Buggy python submission (verdict: Time Limit Exceeded):

ord_a = ord('a')

S = list(map(lambda c: ord(c)-ord_a,input()))
L = 26

memo = []

f = [0]*L
cnt = 0

for i,s in zip(reversed(range(len(S))),reversed(S)):

  cnt += (f[s] == 0)
  f[s] += 1
  if cnt == L:
    memo.append((i,f))
    f = [0]*L
    cnt = 0

memo.append((0,f))
result = []

for i,f in reversed(memo):
  if result:
    c = result[-1]
    for s in S[i:]:
      f[s] -= 1
      if s == c:
        break

  result.append(f.index(0))


print(''.join(map(lambda x: chr(x+ord_a), result)))

Fixed submission:

ord_a = ord('a')
L = 26

S = list(map(lambda c: ord(c)-ord_a,input()))


memo = []

f = [0]*L
cnt = 0


for i,s in zip(reversed(range(len(S))),reversed(S)):

  cnt += (f[s] == 0)
  f[s] += 1
  if cnt == L:
    memo.append((i,f))
    f = [0]*L
    cnt = 0


result = [f.index(0)]

for i,f in reversed(memo):
  c = result[-1]
  for j in range(i,len(S)):
    s = S[j]
    f[s] -= 1
    if s == c:
      break

  result.append(f.index(0))

print(''.join(map(lambda x: chr(x+ord_a), result)))
Buggy python submission (verdict: Time Limit Exceeded):
# 結局は木+1辺
from collections import defaultdict
from itertools import count

N = int(input())
P = list(map(lambda x:int(x)-1,input().split()))
D = [0]*N
for p in P:
  D[p] += 1

rE = defaultdict(list)
for i,p in enumerate(P):
  rE[p] += [i]

S = [p for p in range(N) if D[p] == 0]
L = [None]*N

while S:
  n = S.pop()
  prev = set(L[a] for a in rE[n])
  if prev:
    for i in count():
      if i not in prev:
        L[n] = i
  else:
    L[n] = 0
  
  m = P[n]
  D[m] -= 1
  if D[m] == 0:
    S.append(m)

# cycle check
try:
  start = D.index(1)
except ValueError:
  print('POSSIBLE')
  exit()

def helper(n):
  s = set(L[a] for a in rE[n] if L[a] is not None)
  rlt = []
  for i in count():
    if i not in s:
      rlt.append(i)
      if len(rlt) >= 2:
        return rlt

s1,s2 = helper(start)
G = []
n = P[start]
while n != start:
  G.append(helper(n))
  n = P[n]


del N,P,D,rE,S,L


# 可能な初期値をそれぞれシミュレート
# 1
n = s1
for g in G:
  if g[0] == n:
    n = g[1]
  else:
    n = g[0]
if n != s1:
  print('POSSIBLE')
  exit()

# 2
n = s2
for g in G:
  if g[0] == n:
    n = g[1]
  else:
    n = g[0]
if n == s1:
  print('POSSIBLE')
  exit()

print('IMPOSSIBLE')

Fixed submission:
# 結局は木+1辺
from collections import defaultdict
import heapq as hq

N = int(input())
P = list(map(lambda x:int(x)-1,input().split()))
D = [0]*N
for p in P:
  D[p] += 1

child_L = defaultdict(list)

S = [p for p in range(N) if D[p] == 0]
L = [None]*N

while S:
  n = S.pop()

  q = child_L[n]
  del child_L[n]

  hq.heapify(q)
  i = 0
  while q:
    t = hq.heappop(q)
    if i < t:
      break
    else:
      i += (i==t)
  
  L[n] = i
  m = P[n]
  child_L[m].append(i)
  D[m] -= 1
  if D[m] == 0:
    S.append(m)

# cycle check
try:
  start = D.index(1)
except ValueError:
  print('POSSIBLE')
  exit()

def helper(n):
  q = child_L[n]
  del child_L[n]
  
  hq.heapify(q)
  i = 0
  while q:
    t = hq.heappop(q)
    if i < t:
      break
    else:
      i += (i==t)

  j = i+1
  while q:
    t = hq.heappop(q)
    if j < t:
      break
    else:
      j += (j==t)

  return (i,j)


s1,s2 = helper(start)
G = []
n = P[start]
while n != start:
  G.append(helper(n))
  n = P[n]


del N,P,D,child_L,S,L


# 可能な初期値をそれぞれシミュレート
# 1
n = s1
for g in G:
  if g[0] == n:
    n = g[1]
  else:
    n = g[0]
if n != s1:
  print('POSSIBLE')
  exit()

# 2
n = s2
for g in G:
  if g[0] == n:
    n = g[1]
  else:
    n = g[0]
if n == s1:
  print('POSSIBLE')
  exit()

print('IMPOSSIBLE')
Buggy python submission (verdict: Runtime Error):
from math import gcd

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

if K > max(A):
  print('IMPOSSIBLE')
  exit()

d = A[0]
for a in A:
  d = gcd(d,a)

if K % d == 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Fixed submission:
from fractions import gcd

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

if K > max(A):
  print('IMPOSSIBLE')
  exit()

d = A[0]
for a in A:
  d = gcd(d,a)

if K % d == 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
Buggy python submission (verdict: Runtime Error):
class BinaryIndexedTree:
  def __init__(self, size):
    self.data = [0] * (size+1)
    self.size = size
  
  def add(self, i, w):
    while i <= self.size:
      self.data[i] += w
      i += i & -i

  def sum(self, i):
    result = 0
    while i > 0:
      result += self.data[i]
      i -= i & -i
    return result

from itertools import accumulate,repeat

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

B = [0] + [sa-sk for sa,sk in zip(accumulate(int(input())), accumulate(repeat(K, N)))]

lookup = dict(((b,i+1) for i,b in enumerate(sorted(B))))

result = 0
bit = BinaryIndexedTree(N+1)

for b in B:
  c = lookup[b]
  result += bit.sum(c)
  bit.add(c,1)

print(result)

Fixed submission:
class BinaryIndexedTree:
  def __init__(self, size):
    self.data = [0] * (size+1)
    self.size = size
  
  def add(self, i, w):
    while i <= self.size:
      self.data[i] += w
      i += i & -i

  def sum(self, i):
    result = 0
    while i > 0:
      result += self.data[i]
      i -= i & -i
    return result

from bisect import bisect

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

A = [int(input()) for i in range(N)]

t = 0
B = [t]
for a in A:
  t += a - K
  B.append(t)

temp = sorted(B)
C = [bisect(temp, b) for b in B]

result = 0
bit = BinaryIndexedTree(N+1)

for c in C:
  result += bit.sum(c)
  bit.add(c,1)

print(result)
Buggy python submission (verdict: Runtime Error):
from heapq import *
from collections import Counter

N = int(input())

A = list(map(int, input().split()))
A_indexed = [(a, i) for i, a in enumerate(A)]

def scores():
  # initial N:2N
  selected_left = A[:N] # min heap
  heapify(selected_left)
  l_score = sum(selected_left)

  temp = sorted(A[N:])
  selected_right = Counter(temp[:N])
  unselected_right_counter = Counter(temp[N:])
  unselected_right = list(unselected_right_counter.keys()) # min heap
  heapify(unselected_right)


  r_score = sum(selected_right)

  yield l_score-r_score

  for i,a in enumerate(A[N:2*N]):
    # left 使うものを減らす, right 使うものを増やす
    l_score -= heappushpop(selected_left, a)
    l_score += a
      
    if selected_right[a] > 0:
      r_score -= a
      selected_right[a] -= 1

      x = unselected_right[0]
      while unselected_right_counter[x] == 0:
        del unselected_right_counter[x]
        x = heappop(unselected_right)

      unselected_right_counter[x] -= 1
      selected_right[x] += 1
      r_score += x
    else:
      del selected_right[a]
      unselected_right_counter[a] -= 1

    yield l_score-r_score

print(max(scores()))

Fixed submission:
from heapq import *

N = int(input())

A = list(map(int, input().split()))
A_indexed = [(a, i) for i, a in enumerate(A)]

def scores():
  # initial N:2N
  selected_left = A[:N] # min heap
  heapify(selected_left)
  l_score = sum(selected_left)

  temp = sorted(A_indexed[N:])
  selected_right_set = set(temp[:N])
  unselected_right = temp[N:] # min heap
  del temp
  r_score = sum(map(lambda x: x[0], selected_right_set))

  yield l_score,r_score

  for i in range(N, 2*N):
    a = A[i]
    # left 使うものを減らす, right 使うものを増やす
    if selected_left[0] < a:
      l_score -= heapreplace(selected_left, a)
      l_score += a
      
    if (a,i) in selected_right_set:
      r_score -= a
      selected_right_set.remove((a,i))

      n_element = heappop(unselected_right)
      while n_element[1] <= i:
        n_element = heappop(unselected_right)
      selected_right_set.add(n_element)
      r_score += n_element[0]

    yield l_score,r_score

# print(list(scores()))
print(max(map(lambda x: x[0]-x[1],scores())))