Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n, m, x, y = map(int, input().split())
X = sorted(map(int, input().split()))
Y = sorted(map(int, input().split()))
for i in range(X[-1]:Y[0]):
  if x <= i < y:
    print("No War")
    exit()
print("War")

Fixed submission:
n, m, x, y = map(int, input().split())
X = sorted(list(map(int, input().split())))
Y = sorted(list(map(int, input().split())))
for i in range(X[-1], Y[0]):
  if x <= i < y:
    print("No War")
    exit()
print("War")
Buggy python submission (verdict: Time Limit Exceeded):
s, t = input(), input()
for i in range(len(s)):
  if s[i] != t[i]:
    a = s[i]
    b = t[i]
    s = s.translate(str.maketrans({a: b, b: a}))
  if s[:i+1] != t[:i+1]:
    print("No")
    exit()
print("Yes")

Fixed submission:
s, t = input(), input()
ls, lt = [ [s[0], {0}] ], [ [t[0], {0}] ]

for i in range(len(s)-1):
  if s[i] != s[i+1]:
    b = True
    for j in range(len(ls)):
      if s[i+1] in ls[j][0]:
        ls[j][1].add(i+1)
        b = False
    if b:
      ls.append( [s[i+1], {i+1}] )
      
for i in range(len(t)-1):
  if t[i] != t[i+1]:
    b = True
    for j in range(len(lt)):
      if t[i+1] in lt[j][0]:
        lt[j][1].add(i+1)
        b = False
    if b:
      lt.append( [t[i+1], {i+1}] )

if len(ls) != len(lt):
  print("No")
else:
  for i in range(len(ls)):
    if ls[i][1] != lt[i][1]:
      print("No")
      exit()
  print("Yes")

Buggy python submission (verdict: Time Limit Exceeded):
s, t = input(), input()
for i in range(len(s)):
  if s[i] != t[i]:
    a = s[i]
    b = t[i]
    s = s.translate(str.maketrans({a: b, b: a}))
if s == t:
  print("Yes")
else:
  print("No")


Fixed submission:
s, t = input(), input()
ls, lt = [ [s[0], {0}] ], [ [t[0], {0}] ]

for i in range(len(s)-1):
  if s[i] != s[i+1]:
    b = True
    for j in range(len(ls)):
      if s[i+1] in ls[j][0]:
        ls[j][1].add(i+1)
        b = False
    if b:
      ls.append( [s[i+1], {i+1}] )
      
for i in range(len(t)-1):
  if t[i] != t[i+1]:
    b = True
    for j in range(len(lt)):
      if t[i+1] in lt[j][0]:
        lt[j][1].add(i+1)
        b = False
    if b:
      lt.append( [t[i+1], {i+1}] )

if len(ls) != len(lt):
  print("No")
else:
  for i in range(len(ls)):
    if ls[i][1] != lt[i][1]:
      print("No")
      exit()
  print("Yes")

Buggy python submission (verdict: Time Limit Exceeded):
s, t = input(), input()
for i in range(len(s)):
  if s[i] != t[i]:
    a = s[i]
    b = t[i]
    s = s.translate(str.maketrans({a: b, b: a}))
if s == t:
  print("Yes")
else:
  print("No")

Fixed submission:
s, t = input(), input()
ls, lt = [ [s[0], {0}] ], [ [t[0], {0}] ]

for i in range(len(s)-1):
  if s[i] != s[i+1]:
    b = True
    for j in range(len(ls)):
      if s[i+1] in ls[j][0]:
        ls[j][1].add(i+1)
        b = False
    if b:
      ls.append( [s[i+1], {i+1}] )
      
for i in range(len(t)-1):
  if t[i] != t[i+1]:
    b = True
    for j in range(len(lt)):
      if t[i+1] in lt[j][0]:
        lt[j][1].add(i+1)
        b = False
    if b:
      lt.append( [t[i+1], {i+1}] )

if len(ls) != len(lt):
  print("No")
else:
  for i in range(len(ls)):
    if ls[i][1] != lt[i][1]:
      print("No")
      exit()
  print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

n, m = map(int, input().split())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
ans = 0
for i in range(1, n+1):
  for j in range(i):
    if (L[i]-L[j])%m == 0:
      ans += 1
print(ans)

Fixed submission:
from itertools import accumulate
from collections import Counter

n, m = map(int, input().split())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
L = [ i%m for i in L ]
C = Counter(L)
ans = 0
for i in C.values():
  ans += i*(i-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

n, m = map(int, input().split())
A = list(map(int, input().split()))
dp = [ [0]*(n+1) for _ in range(n+1) ]
L = [0] + list(accumulate(A))
ans = 0
for i in range(1, n+1):
  for j in range(i):
    if (L[i]-L[j])%m == 0:
      ans += 1
print(ans)

Fixed submission:
from itertools import accumulate
from collections import Counter

n, m = map(int, input().split())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
L = [ i%m for i in L ]
C = Counter(L)
ans = 0
for i in C.values():
  ans += i*(i-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

n = int(input())
S = input()
A = S[:n]
B = S[n:][::-1]
Da = defaultdict(int)
Db = defaultdict(int)
ans = 0
for i in range(2**n):
  a1, a2 = "", ""
  for j in range(n):
    if i>>j & 1:
      a1 += A[j]
    else:
      a2 += A[j]
  Da[(a1, a2)] += 1
for i in range(2**n):
  b1, b2 = "", ""
  for j in range(n):
    if i>>j & 1:
      b1 += B[j]
    else:
      b2 += B[j]
  Db[(b1, b2)] += 1

for k in Da:
  ans += Da[k] * Db[k]
print(ans)

Fixed submission:
from collections import defaultdict

n = int(input())
S = input()
A = S[:n]
B = S[n:][::-1]
Da = defaultdict(int)
Db = defaultdict(int)
ans = 0
for i in range(2**n):
  a1, a2 = "", ""
  for j in range(n):
    if i>>j & 1:
      a1 += A[j]
    else:
      a2 += A[j]
  Da[(a1, a2)] += 1
for i in range(2**n):
  b1, b2 = "", ""
  for j in range(n):
    if i>>j & 1:
      b1 += B[j]
    else:
      b2 += B[j]
  Db[(b1, b2)] += 1

for k in Da:
  ans += Da[k] * Db[k]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from itertools import accumulate

def main():
  
  def merge(i, j):
    if dp1[i] >= A[j]:
      dp2[i] = max(dp2[i], A[j])
    else:
      dp2[i] = dp1[i]
      dp1[i] = A[j]
  n = int(input())
  A = tuple(map(int, input().split()))
  dp1 = [0]*(1<<n)
  dp2 = [0]*(1<<n)
  for i in range(1<<n):
    j = i
    while j>0:
      merge(i, j)
      j = (j-1)&i
    merge(i, 0)
  L = list(accumulate([a+b for a, b in zip(dp1, dp2)], max))
  print(*L[1:], sep="\n")

if __name__ == "__main__":
  main()

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

def merge(x, y):
  D = sorted([dp[x][0], dp[x][1], dp[y][0], dp[y][1]], reverse=True)
  return (D[0], D[1])
  
n = int(input())
A = tuple(map(int, input().split()))
dp = [(a, 0) for a in A]
for j in range(n):
  for i in range(1<<n):
    if i & (1<<j):
      dp[i] = merge(i, i & ~(1<<j))
L = tuple(accumulate((sum(d) for d in dp), max))
print(*L[1:], sep="\n")

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

def merge(i, j):
  if dp1[i] >= A[j]:
    dp2[i] = max(dp2[i], A[j])
  else:
    dp2[i] = dp1[i]
    dp1[i] = A[j]
n = int(input())
A = tuple(map(int, input().split()))
dp1 = [0]*(1<<n)
dp2 = [0]*(1<<n)
for i in range(1<<n):
  j = i
  while j>0:
    merge(i, j)
    j = (j-1)&i
  merge(i, 0)
L = list(accumulate([a+b for a, b in zip(dp1, dp2)], max))
print(*L[1:], sep="\n")

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

def merge(x, y):
  D = sorted([dp[x][0], dp[x][1], dp[y][0], dp[y][1]], reverse=True)
  return (D[0], D[1])
  
n = int(input())
A = tuple(map(int, input().split()))
dp = [(a, 0) for a in A]
for j in range(n):
  for i in range(1<<n):
    if i & (1<<j):
      dp[i] = merge(i, i & ~(1<<j))
L = tuple(accumulate((sum(d) for d in dp), max))
print(*L[1:], sep="\n")

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

def merge(x, y):
  D = sorted([dp[x][0], dp[x][1], dp[y][0], dp[y][1]], reverse=True)
  return (D[0], D[1])
  
n = int(input())
A = tuple(map(int, input().split()))
dp = [(a, 0) for a in A]
for j in range(n):
  for i in range(1<<n):
    if i & (1<<j):
      dp[i] = merge(i, i & ~(1<<j))
L = tuple(accumulate((sum(d) for d in dp), max))
print(*L[1:], sep="\n")

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

def merge(x, y):
  D = sorted([dp[x][0], dp[x][1], dp[y][0], dp[y][1]], reverse=True)
  return (D[0], D[1])
  
n = int(input())
A = tuple(map(int, input().split()))
dp = [(a, 0) for a in A]
for j in range(n):
  for i in range(1<<n):
    if i & (1<<j):
      dp[i] = merge(i, i & ~(1<<j))
L = tuple(accumulate((sum(d) for d in dp), max))
print(*L[1:], sep="\n")
Buggy python submission (verdict: Runtime Error):
n = input()
k = list(map(int, list(n)))
s = sum(n)
n = int(n)
if n%k:
  print("No")
else:
  print("Yes")

Fixed submission:
s = input()
c = 0
for i in s:
  c += int(i)
if int(s) % c:
  print("No")
else:
  print("Yes")
Buggy python submission (verdict: Runtime Error):
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
w = a.index(1)
if w<k or n-w-1<k:
  print( math.ceil((n-1)/(k-1)) )
else:
  print( math.seil((w)/(k-1)) + math.ceil((n-w-1)/(k-1)) )

Fixed submission:
n, k = map(int, input().split())
print(-((1-n)//(k-1)))
Buggy python submission (verdict: Runtime Error):
from fractions import Fraction
L = []
for i in range(1, 18):
    for j in range(1, 9*i+1):
        if (j-1)//9 >= i-1:
            temp = str(9-(-j%9)) + "9"*(i-1)
        else:
            temp = "1"
            t = j-1
            for rest in range(i-1, 0, -1):
                if t <= 9*(rest-1):
                    temp += "0"
                else:
                    temp += str(t-9*(rest-1))
                    t = 9*(rest-1)
        L.append((int(temp), j))
L.sort(reverse=True)
A = []
m = float("inf")
for l, k in L:
    if Fraction(l, k) <= m:
        A.append(l)
        m = Fraction(l, k)
k = int(input())
for i in range(k):
    print(A.pop())

Fixed submission:
from fractions import Fraction
def S(n):
  res = 0
  while n:
    n, r = divmod(n, 10)
    res += r
  return res
k = int(input())
n = 1
for _ in range(k):
  print(n)
  n += 1
  m = Fraction(n, S(n))
  temp = n
  for d in range(len(str(n))+1):
    x = 10**(d+1)*(n//(10**(d+1))+1)-1
    if Fraction(x, S(x)) < m:
      m = Fraction(x, S(x))
      temp = x
  n = temp
Buggy python submission (verdict: Time Limit Exceeded):
d = tuple([1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)])
M = 10**6+1
B = [float("inf")]*M
B[0] = 0
for i in range(M):
  for j in d:
    if i+j < M:
      B[i+j] = min(B[i+j], B[i]+1)
n = int(input())
print(B[n])

Fixed submission:
d = tuple([1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)])
M = 10**6+1
B = [float("inf")]*M
B[0] = 0
for i in range(M):
  for j in d:
    if i+j < M:
      B[i+j] = min(B[i+j], B[i]+1)
n = int(input())
print(B[n])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline
n, c = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(c)]
C = [list(map(int, input().split())) for _ in range(n)]
A = [[0]*c for _ in range(3)]
for i in range(n):
  for j in range(n):
    x = C[i][j] - 1
    r = (i+j)%3
    for y in range(c):
      A[r][y] += D[x][y]
ans = float("inf")
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i == j or j == k or k == i:
        continue
      temp = A[0][i] + A[1][j] + A[2][k]
      ans = min(ans, temp)
print(ans)

Fixed submission:
import sys
input = sys.stdin.buffer.readline
n, c = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(c)]
C = [list(map(int, input().split())) for _ in range(n)]
A = [[0]*c for _ in range(3)]
for i in range(n):
  for j in range(n):
    x = C[i][j] - 1
    r = (i+j)%3
    for y in range(c):
      A[r][y] += D[x][y]
ans = float("inf")
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i == j or j == k or k == i:
        continue
      temp = A[0][i] + A[1][j] + A[2][k]
      ans = min(ans, temp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
M=998244353;n,A,B,K=map(int,input().split());F=[1]
for i in range(n):F+=[F[-1]*(i+1)%M]
C=lambda k:F[n]*pow(F[k]*F[n-k],M-2,M)if 0<=k<=n else 0;a=0
for i in range(n+1):
 r=K-i*A
 if r%B==0:a+=C(i)*C(r//B);a%=M
print(a)

Fixed submission:
U = 3*10**5
MOD = 998244353
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
n, a, b, k = map(int, input().split())
ans = 0
for i in range(n+1):
  r = k - i*a
  if r%b==0 and 0 <= r//b <= n:
    ans += comb(n, i) * comb(n, r//b)
    ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
M=998244353;n,A,B,K=map(int,input().split());F=[1]
for i in range(n):F+=[F[-1]*(i+1)%M]
C=lambda k:F[n]*pow(F[k]*F[n-k],M-2,M)if 0<=k<=n else 0;a=0
for i in range(n+1):
 r=K-i*A
 if r%B==0:a+=C(r//B)*C(i)
print(a%M)

Fixed submission:
U = 3*10**5
MOD = 998244353
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
n, a, b, k = map(int, input().split())
ans = 0
for i in range(n+1):
  r = k - i*a
  if r%b==0 and 0 <= r//b <= n:
    ans += comb(n, i) * comb(n, r//b)
    ans %= MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
M=998244353;n,A,B,K=map(int,input().split());F=[1]
for i in range(n):F+=[F[-1]*(i+1)%M]
C=lambda k:F[n]*pow(F[k]*F[n-k],M-2,M)if 0<=k<=n else 0;a=0
for i in range(n+1):
 r=K-i*A
 if r%B==0:a+=C(i)*C(r//B)
print(a%M)

Fixed submission:
U = 3*10**5
MOD = 998244353
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
n, a, b, k = map(int, input().split())
ans = 0
for i in range(n+1):
  r = k - i*a
  if r%b==0 and 0 <= r//b <= n:
    ans += comb(n, i) * comb(n, r//b)
    ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from heapq import merge

n, k, q = map(int, input().split())
A = list(map(int, input().split())) + [-1]
ans = float("inf")
for a in A:
  L = []
  S = []
  for t in A:
    if t >= a:
      L.append(t)
    else:
      L.sort()
      S.append(L[:max(len(L)-k+1, 0)])
      L = []
  K = list(merge(*S))
  if len(K) < q:
    continue
  y = K[q-1]
  ans = min(ans, y-a)
print(ans)

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

n, k, q = map(int, input().split())
A = list(map(int, input().split())) + [-1]
ans = float("inf")
for a in A:
  L = []
  K = []
  for t in A:
    if t >= a:
      L.append(t)
    else:
      L.sort()
      for c in range(len(L)-k+1):
        K.append(L[c])
      L = []
  K.sort()
  if len(K) < q:
    continue
  else:
    y = K[q-1]
    ans = min(ans, y-a)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n = int(input())
S = np.array([ list(input()) for _ in range(n) ])
ans = 0
for i in range(n):
  for j in range(n):
    M = S[:, [(l+j)%n for l in range(n)]]
    L = M[[(k+i)%n for k in range(n)], :]
    if (L==L.T).all():
      ans += 1 
print(ans)

Fixed submission:
import numpy as np
n = int(input())
S = np.array([ list(input()) for _ in range(n) ])
ans = 0
for j in range(n):
  M = S[:, [(l+j)%n for l in range(n)]]
  if (M==M.T).all():
    ans += n
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, k = map(int, input().split())
for i in range(a, b+1):
  if min(i-a+1, b-i+1) <= k:
    print(i)

Fixed submission:
a, b, k = map(int, input().split())
s, l = [], []
for i in range(k):
  if a+i == b-i:
    s.append(a+i)
    break
  else:
    s.append(a+i)
    l.append(b-i)
    if b-a-2*i == 1:
      break
for i in s:
  print(i)
for i in l[::-1]:
  print(i)
Buggy python submission (verdict: Runtime Error):
s = input()
if len(s)<26:
  for i in al:
    if i not in s:
      print(s+i)
      break
else:
  if s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
  else:
    k = []
    for i in range(25, 0, -1):
      k.append(s[i])
      if s[i-1] < s[i]:
        for j in sorted(k):
          if j > s[i-1]:
            print(s[:i-1] + j)
            exit()

Fixed submission:
al = "abcdefghijklmnopqrstuvwxyz"
s = input()
if len(s)<26:
  for i in al:
    if i not in s:
      print(s+i)
      break
else:
  if s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
  else:
    k = []
    for i in range(25, 0, -1):
      k.append(s[i])
      if s[i-1] < s[i]:
        for j in sorted(k):
          if j > s[i-1]:
            print(s[:i-1] + j)
            exit()
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
ans = 0
for i in range(30):
  t = 1<<i
  cnt = 0
  C = sorted(b%(t*2) for b in B)
  for a in A:
    a %= t*2
    cnt += bisect.bisect_left(C, 2*t-a) - bisect.bisect_left(C, t-a)
    cnt += bisect.bisect_left(C, 4*t-a) - bisect.bisect_left(C, 3*t-a)
    cnt %= 2
  ans |= cnt << i
print(ans)

Fixed submission:
import numpy as np
n = int(input())
A = np.array(list(map(int, input().split())), dtype=np.int64)
B = np.array(list(map(int, input().split())), dtype=np.int64)
ans = 0
for i in range(30):
  t = 1<<i
  C = B.copy()%(2*t)
  E = A.copy()%(2*t)
  C.sort()
  E.sort()
  D = np.searchsorted(C, 2*t-E, side="left")
  D -= np.searchsorted(C, t-E, side="left")
  D += np.searchsorted(C, 4*t-E, side="left")
  D -= np.searchsorted(C, 3*t-E, side="left")
  cnt = D.sum()%2
  ans |= cnt << i
print(ans)
Buggy python submission (verdict: Runtime Error):
n=input()
if "Y" in input():
  print("Four")
else:
  print("Three)

Fixed submission:
n=input()
if "Y" in input():
  print("Four")
else:
  print("Three")
Buggy python submission (verdict: Time Limit Exceeded):
import random

n = int(input())
L = list(range(n))
random.shuffle(L)
K = []
now = -1
for a in L:
  print(a, flush=True)
  t = input()
  if t == "Vacant":
    exit()
  if now == -1:
    now = t
    K.append(a)
  else:
    if now != t:
      m = min(K), M = max(K)
      if abs(m-a) < abs(M-a):
        l, r = m, a
      else:
        l, r = M, a
      l_s, r_s = now, t
      break
    else:
      K.append(a)
if l > r:
  l, r = r, l
  l_s, r_s = r_s, l_s
while True:
  mid = (l+r)//2
  print(mid, flush=True)
  t = input()
  if t == "Vacant":
    exit()
  if t == l_s:
    l = mid
  else:
    r = mid

Fixed submission:
n = int(input())
l, r = 0, n-1
print(0, flush=True)
l_s = input()
if l_s == "Vacant":
  exit()
print(n-1, flush=True)
l_t = input()
if l_t == "Vacant":
  exit()
while True:
  mid = (l+r)//2
  print(mid, flush=True)
  t = input()
  if t == "Vacant":
    exit()
  if ((mid-l)%2 and l_s==t) or ((mid-l)%2==0 and l_s!=t):
    r = mid
  else:
    l = mid
    l_s = t

Buggy python submission (verdict: Time Limit Exceeded):
import random

n = int(input())
L = list(range(n))
random.shuffle(L)
K = []
now = -1
for a in L:
  print(a, flush=True)
  t = input()
  if t == "Vacant":
    exit()
  if now != -1 and now != t:
    m = min(K), M = max(K)
    if abs(m-a) < abs(M-a):
      l, r = m, a
    else:
      l, r = M, a
    l_s, r_s = now, t
    break
if l > r:
  l, r = r, l
  l_s, r_s = r_s, l_s
while True:
  mid = (l+r)//2
  print(mid, flush=True)
  t = input()
  if t == "Vacant":
    exit()
  if t == l_s:
    l = mid
  else:
    r = mid

Fixed submission:
n = int(input())
l, r = 0, n-1
print(0, flush=True)
l_s = input()
if l_s == "Vacant":
  exit()
print(n-1, flush=True)
l_t = input()
if l_t == "Vacant":
  exit()
while True:
  mid = (l+r)//2
  print(mid, flush=True)
  t = input()
  if t == "Vacant":
    exit()
  if ((mid-l)%2 and l_s==t) or ((mid-l)%2==0 and l_s!=t):
    r = mid
  else:
    l = mid
    l_s = t
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
  n, m = map(int, input().split())
  F = [[] for _ in range(n)]
  lrd = [list(map(int, input().split())) for _ in range(m)]
  for _ in range(2):
    for i in range(m):
      l, r, d = lrd[i]
      l -= 1
      r -= 1
      for nr, nd in F[l]:
        if r == nr:
          if d != nd:
            print("No")
            exit()
        else:
          F[nr].append((r, d-nd))
          F[r].append((nr, nd-d))
      F[l].append((r, d))
      for nl, nd in F[r]:
        if l == nl:
          if -d != nd:
            print("No")
            exit()
        else:
          F[l].append((nl, nd+d))
          F[nl].append((l, -nd-d))
      F[r].append((l, -d))
  print("Yes")
  
if __name__ == "__main__":
  main()

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

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  l, r, d = map(int, input().split())
  l -= 1
  r -= 1
  G[l].append((r, d))
  G[r].append((l, -d))
dist = [float("inf")]*n
def dfs(v):
  for nv, d in G[v]:
    if dist[nv] == float("inf"):
      dist[nv] = dist[v]+d
      if not dfs(nv):
        return False
    else:
      if dist[nv] != dist[v]+d:
        return False
  return True
for i in range(n):
  if dist[i] == float("inf"):
    dist[i] = 0
    if not dfs(i):
      print("No")
      break
else:
  print("Yes")

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

def main():
  n, m = map(int, input().split())
  F = [[] for _ in range(n)]
  lrd = [list(map(int, input().split())) for _ in range(m)]
  for _ in range(2):
    for i in range(m):
      l, r, d = lrd[i]
      l -= 1
      r -= 1
      for nr, nd in F[l]:
        if r == nr:
          if d != nd:
            print("No")
            exit()
        else:
          F[nr].append((r, d-nd))
          F[r].append((nr, nd-d))
      F[l].append((r, d))
      for nl, nd in F[r]:
        if l == nl:
          if -d != nd:
            print("No")
            exit()
        else:
          F[l].append((nl, nd+d))
          F[nl].append((l, -nd-d))
      F[r].append((l, -d))
  print("Yes")
  
if __name__ == "__main__":
  main()

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

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  l, r, d = map(int, input().split())
  l -= 1
  r -= 1
  G[l].append((r, d))
  G[r].append((l, -d))
dist = [float("inf")]*n
def dfs(v):
  for nv, d in G[v]:
    if dist[nv] == float("inf"):
      dist[nv] = dist[v]+d
      if not dfs(nv):
        return False
    else:
      if dist[nv] != dist[v]+d:
        return False
  return True
for i in range(n):
  if dist[i] == float("inf"):
    dist[i] = 0
    if not dfs(i):
      print("No")
      break
else:
  print("Yes")
Buggy python submission (verdict: Runtime Error):
n = int(input())
M = 10**4
dp = [0]*(2*M)
dp[M] = 1
A = tuple(map(int, input().split()))
for i, a in enumerate(A):
  for j in range(2*M):
    if j-a >= 0 and dp[j-a]:
      dp[j] = 1
l = sum(divmod(sum(A), 2))
now = M+l
while True:
  if dp[now]:
    print(now-M)
    break
  now += 1

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
M = sum(A)

s = 1 << M
for a in A:
  s |= s >> a
ans = bin(s)[2+(M+1)//2:].find("1") + (M+1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
s = input()
s[3] = "8"
print(s)

Fixed submission:
s = input()
print(s[:3]+"8"+s[4:])