Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict as dd
import sys
sys.setrecursionlimit(6000)
N, M, P = map(int, input().split())
edges = []
revedgedict = dd(dict)
for _ in range(M):
  f, t, c = map(int, input().split())
  edges.append((f-1, t-1, -(c-P)))
  revedgedict[t-1][f-1] = 1

# Nに到達できない頂点を削除
visited = [False] * N
def dfs(f):
  visited[f] = True
  for t in revedgedict[f].keys():
    if not visited[t]:
      dfs(t)
dfs(N-1)

# ベルマンフォード
INF = float('inf')
d = [float('inf')] * N
d[0] = 0
for i in range(N):
  updated = False
  for f, t, c in edges:
    if d[f] != INF and visited[t] and d[t] > d[f] + c:
      d[t] = d[f] + c
      updated = True
  if not updated:
    break
else:
  print(-1)
  exit()
print(max(-d[-1], 0))

Fixed submission:
from collections import defaultdict as dd
import sys
sys.setrecursionlimit(6000)
N, M, P = map(int, input().split())
edges = []
revedgedict = dd(dict)
for _ in range(M):
  f, t, c = map(int, input().split())
  edges.append((f-1, t-1, -(c-P)))
  revedgedict[t-1][f-1] = 1

# Nに到達できない頂点を削除
visited = [False] * N
def dfs(f):
  visited[f] = True
  for t in revedgedict[f].keys():
    if not visited[t]:
      dfs(t)
dfs(N-1)

# ベルマンフォード
INF = float('inf')
d = [float('inf')] * N
d[0] = 0
for i in range(N):
  updated = False
  for f, t, c in edges:
    if d[f] != INF and visited[t] and d[t] > d[f] + c:
      d[t] = d[f] + c
      updated = True
  if not updated:
    break
else:
  print(-1)
  exit()
print(max(-d[-1], 0))

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict as dd
import sys
sys.setrecursionlimit(6000)
N, M, P = map(int, input().split())
edges = []
edgedict = dd(dict)
for _ in range(M):
  f, t, c = map(int, input().split())
  edges.append((f-1, t-1, -(c-P)))
  edgedict[f-1][t-1] = 1

# Nに到達できない頂点を削除
visited = [False] * N
unreach = set()
def dfs(f):
  visited[f] = True
  for t in edgedict[f].keys():
    if t == N-1:
      return True
    ret = False
    if not visited[t]:
      ret = ret or dfs(t)
  if not ret:
    unreach.add(f)
  return ret
dfs(0)

# ベルマンフォード
INF = float('inf')
d = [float('inf')] * N
d[0] = 0
for i in range(M):
  updated = False
  for f, t, c in edges:
    if d[f] != INF and t not in unreach and d[t] > d[f] + c:
      d[t] = d[f] + c
      updated = True
  if not updated:
    break
else:
  print(-1)
  exit()
print(max(-d[-1], 0))

Fixed submission:
from collections import defaultdict as dd
import sys
sys.setrecursionlimit(6000)
N, M, P = map(int, input().split())
edges = []
revedgedict = dd(dict)
for _ in range(M):
  f, t, c = map(int, input().split())
  edges.append((f-1, t-1, -(c-P)))
  revedgedict[t-1][f-1] = 1

# Nに到達できない頂点を削除
visited = [False] * N
def dfs(f):
  visited[f] = True
  for t in revedgedict[f].keys():
    if not visited[t]:
      dfs(t)
dfs(N-1)

# ベルマンフォード
INF = float('inf')
d = [float('inf')] * N
d[0] = 0
for i in range(N):
  updated = False
  for f, t, c in edges:
    if d[f] != INF and visited[t] and d[t] > d[f] + c:
      d[t] = d[f] + c
      updated = True
  if not updated:
    break
else:
  print(-1)
  exit()
print(max(-d[-1], 0))
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7
S = input()
if S[-1] == '?':
  dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
  dpsum = 10
else:
  dp = [0] * 13
  dp[int(S[-1])] = 1
  dpsum = 1

unitmod = 1
for i, c in enumerate(list(reversed(S))[1:]):
  ndp = [0] * 13
  ndpsum = 0
  unitmod = unitmod * 10 % 13
  if c == '?':
    d = 0
    k = 10 ** (i+1)
    s = set([1,2,3,4,5,6,7,8,9,10,11,12])
    tm = unitmod
    for _ in range(9):
      s.discard(tm)
      tm = (tm + unitmod) % 13
    for j in range(13):
      x = dpsum
      for e in s:
        x -= dp[(j-e) % 13]
        x %= MOD
      ndp[j] = x
      ndpsum += x
  else:
    mod = unitmod * int(c) % 13
    for j in range(13):
      x = dp[(j-mod) % 13]
      x %= MOD
      ndp[j] = x
      ndpsum += x
  dp = ndp
  dpsum = ndpsum % MOD
print(dp[5])

Fixed submission:
MOD = 10 ** 9 + 7
S = input()
if S[-1] == '?':
  dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
  dpsum = 10
else:
  dp = [0] * 13
  dp[int(S[-1])] = 1
  dpsum = 1

unitmod = 1
for i, c in enumerate(list(reversed(S))[1:]):
  ndp = [0] * 13
  ndpsum = 0
  unitmod = unitmod * 10 % 13
  if c == '?':
    s = set([1,2,3,4,5,6,7,8,9,10,11,12])
    tm = unitmod
    for _ in range(9):
      s.discard(tm)
      tm = (tm + unitmod) % 13
    for j in range(13):
      x = dpsum
      for e in s:
        x -= dp[(j-e) % 13]
        x %= MOD
      ndp[j] = x
      ndpsum += x
  else:
    mod = unitmod * int(c) % 13
    for j in range(13):
      x = dp[(j-mod) % 13]
      x %= MOD
      ndp[j] = x
      ndpsum += x
  dp = ndp
  dpsum = ndpsum % MOD
print(dp[5])
Buggy python submission (verdict: Runtime Error):
from collections import Counter
ct = Counter(input())
a1, a2 = ct.most_common(2)
if a1[1] == 2 and a2[1] == 2:
  print('Yes')
else:
  print('No')

Fixed submission:
from collections import Counter
ct = Counter(input())
a = ct.most_common(2)
if len(a) == 2 and a[0][1] == 2 and a[1][1] == 2:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
P = [list(map(int, input().split())) for _ in range(N)]
ct = Counter()
for i in range(len(P)):
  x1, y1 = P[i]
  for j in range(i+1, len(P)):
    x2, y2 = P[j]
    dx, dy = x2-x1, y2-y1
    if dx < 0:
      dx, dy = -dx, -dy
    ct[(dx, dy)] += 1

print(N - ct.most_common(1)[0][1])

Fixed submission:
from collections import Counter
N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]
P.sort()
if N == 1:
  print(1)
  exit()

ct = Counter()
for i in range(len(P)):
  x1, y1 = P[i]
  for j in range(i+1, len(P)):
    x2, y2 = P[j]
    dx, dy = x2-x1, y2-y1
    if dx < 0:
      dx, dy = -dx, -dy
    ct[(dx, dy)] += 1

print(N - ct.most_common(1)[0][1])
Buggy python submission (verdict: Runtime Error):
N = int(input())
Ga, Sa, Ba = map(int, input().split())
Gb, Sb, Bb = map(int, input().split())
M = max(Ga, Sa, Ba)

dp = [0]*(M+1)
for i in range(M+1, N+M+1):
  dp.append(max(
    dp[-1] + 1,
    dp[-Ga] + Gb,
    dp[-Sa] + Sb,
    dp[-Ba] + Bb,
  ))
N2 = dp[-1]

dp = [0]*(M+1)
for i in range(M+1, N2+M+1):
  dp.append(max(
    dp[-1] + 1,
    dp[-Gb] + Ga,
    dp[-Sb] + Sa,
    dp[-Bb] + Ba,
  ))
print(dp[-1])

Fixed submission:
N = int(input())
Ga, Sa, Ba = map(int, input().split())
Gb, Sb, Bb = map(int, input().split())

dp = [0]
for i in range(1, N+1):
  tmp = dp[-1] + 1
  if Ga <= i:
    t2 = dp[-Ga] + Gb
    tmp = tmp if tmp > t2 else t2
  if Sa <= i:
    t2 = dp[-Sa] + Sb
    tmp = tmp if tmp > t2 else t2
  if Ba <= i:
    t2 = dp[-Ba] + Bb
    tmp = tmp if tmp > t2 else t2
  dp.append(tmp)
N2 = dp[-1]

dp = [0]
for i in range(1, N2+1):
  tmp = dp[-1] + 1
  if Gb <= i:
    t2 = dp[-Gb] + Ga
    tmp = tmp if tmp > t2 else t2
  if Sb <= i:
    t2 = dp[-Sb] + Sa
    tmp = tmp if tmp > t2 else t2
  if Bb <= i:
    t2 = dp[-Bb] + Ba
    tmp = tmp if tmp > t2 else t2
  dp.append(tmp)
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2500)
H, W = map(int, input().split())
S = ['#'*(W+2)]+['#' + input() + '#' for _ in range(H)]+['#'*(W+2)]

ansX = [[None] * (W+2) for _ in range(H+2)]
ansY = [[None] * (W+2) for _ in range(H+2)]

def process(n, x, y, dx, dy):
  ret = 0
  if S[y][x] == '#':
    ret = n
  else:
    ret = process(n+1, x+dx, y+dy, dx, dy)
  if dx > 0:
    ansX[y][x] = ret
  else:
    ansY[y][x] = ret
  return ret

final = 0
for y in range(1, H+1):
  for x in range(1, W+1):
    if S[y][x] == '#':
      continue
    if ansX[y][x] is None:
      process(0, x, y, 1, 0)
    if ansY[y][x] is None:
      process(0, x, y, 0, 1)
    a = ansX[y][x] + ansY[y][x] - 1
    final = a if a > final else final
print(final)

Fixed submission:
H, W = map(int, input().split())
S = ['#'*(W+2)]+[
  '#' + input() + '#' for _ in range(H)
]+['#'*(W+2)]

ST = list(map(''.join, zip(*S)))

ansX = [[None] * (W+2) for _ in range(H+2)]
ansY = [[None] * (H+2) for _ in range(W+2)]

final = 0
for y in range(1, H+1):
  Sy = S[y]
  ansXy = ansX[y]
  #ansYy = ansY[y]
  for x in range(1, W+1):
    if Sy[x] == '#':
      continue
    if ansX[y][x] is None:
      t = Sy.find('#', x)
      ansXy[x:t] = [t-x] * (t-x)
    if ansY[x][y] is None:
      t = ST[x].find('#', y)
      ansY[x][y:t] = [t-y] * (t-y)
    a = ansXy[x] + ansY[x][y] - 1
    final = a if a > final else final
print(final)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2500)
H, W = map(int, input().split())
S = ['#'*(W+2)]+['#' + input() + '#' for _ in range(H)]+['#'*(W+2)]

ans = [[None] * (W+2) for _ in range(H+2)]
ansX = [[None] * (W+2) for _ in range(H+2)]
ansY = [[None] * (W+2) for _ in range(H+2)]

def process(n, x, y, dx, dy):
  ret = 0
  if S[y][x] == '#':
    ret = n
  else:
    ret = process(n+1, x+dx, y+dy, dx, dy)
  if dx > 0:
    ansX[y][x] = ret
  else:
    ansY[y][x] = ret
  return ret

final = 0
for y in range(1, H+1):
  for x in range(1, W+1):
    if S[y][x] == '#':
      continue
    if ansX[y][x] is None:
      process(0, x, y, 1, 0)
    if ansY[y][x] is None:
      process(0, x, y, 0, 1)
    ans = ansX[y][x] + ansY[y][x] - 1
    final = ans if ans > final else final
print(final)

Fixed submission:
H, W = map(int, input().split())
S = ['#'*(W+2)]+[
  '#' + input() + '#' for _ in range(H)
]+['#'*(W+2)]

ST = list(map(''.join, zip(*S)))

ansX = [[None] * (W+2) for _ in range(H+2)]
ansY = [[None] * (H+2) for _ in range(W+2)]

final = 0
for y in range(1, H+1):
  Sy = S[y]
  ansXy = ansX[y]
  #ansYy = ansY[y]
  for x in range(1, W+1):
    if Sy[x] == '#':
      continue
    if ansX[y][x] is None:
      t = Sy.find('#', x)
      ansXy[x:t] = [t-x] * (t-x)
    if ansY[x][y] is None:
      t = ST[x].find('#', y)
      ansY[x][y:t] = [t-y] * (t-y)
    a = ansXy[x] + ansY[x][y] - 1
    final = a if a > final else final
print(final)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
MOD = 10 ** 9 + 7
dp = 1

n = 1
for c in reversed(S):
  if c == '1':
    dp = (2 * dp + n) % MOD
  n *= 3
print(dp)

Fixed submission:
S = input()
MOD = 10 ** 9 + 7
dp = 1

n = 1
for c in reversed(S):
  if c == '1':
    dp = 2 * dp + n
  n *= 3
print(dp % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
MOD = 10 ** 9 + 7
dp = 1
p = 0

n = 1
for c in reversed(S):
  if c == '1':
    dp = (2 * dp + n) % MOD
  n *= 3 % MOD
print(dp)

Fixed submission:
S = input()
MOD = 10 ** 9 + 7
dp = 1

n = 1
for c in reversed(S):
  if c == '1':
    dp = 2 * dp + n
  n *= 3
print(dp % MOD)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict as dd
N = int(input())
edge = dd(lambda: dd(int))
for _ in range(N-1):
  a, b, w = map(int, input().split())
  edge[a-1][b-1] = w
  edge[b-1][a-1] = w

ans = [None] * N
def dfs(n, dist):
  ans[n] = dist % 2
  for t in edge[n]:
    if ans[t] is not None:
      continue
    dfs(t, dist + edge[n][t])
dfs(0, 0)
for a in ans:
  print(a)

Fixed submission:
import sys
from collections import defaultdict as dd
sys.setrecursionlimit(100000)
N = int(input())
edge = dd(lambda: dd(int))
for _ in range(N-1):
  a, b, w = map(int, input().split())
  edge[a-1][b-1] = w
  edge[b-1][a-1] = w

ans = [None] * N
def dfs(n, dist):
  ans[n] = dist % 2
  for t in edge[n]:
    if ans[t] is not None:
      continue
    dfs(t, dist + edge[n][t])
dfs(0, 0)
for a in ans:
  print(a)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = float('-inf')
for i in range(2 ** N):
  t = 0
  for j in range(N):
    if i & (1 << j):
      t += V[j]
      t -= C[j]
  ans = ans if ans > t else t
print(ans)

Fixed submission:
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))
print(sum([max(v-c, 0) for v, c in zip(V, C)]))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

# 辺を保持しつつ根を見つける
edge = [set() for _ in range(N+1)]
parent = [-1] + [0] * N
for _ in range(N-1+M):
  a, b = map(int, input().split())
  parent[b] = a
  edge[a].add(b)
root = parent.index(0)

# 根から幅優先でたどっていく
ans = [-1] * (N+1)
rank = [0] * (N+1)
q = set([root])
r = 0
while len(q):
  nq = set()
  for p in q:
    for c in edge[p]:
      nq.add(c)
      # 後に来る＝より深い ので上書きしてよいはず
      ans[c] = p
  q = nq

for i in range(1, N+1):
  print(ans[i] if ans[i] > 0 else 0)

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

# 辺を保持しつつ根を見つける
edge = [set() for _ in range(N+1)]
indim = [0] * (N+1)
parent = [-1] + [0] * N
for _ in range(N-1+M):
  a, b = map(int, input().split())
  parent[b] = a
  edge[a].add(b)
  indim[b] += 1
root = parent.index(0)

# 根から幅優先でたどっていく
ans = [-1] * (N+1)
q = set([root])
while len(q):
  nq = set()
  for p in q:
    for c in edge[p]:
      indim[c] -= 1
      if indim[c] == 0:
        nq.add(c)
        ans[c] = p
  q = nq

for i in range(1, N+1):
  print(ans[i] if ans[i] > 0 else 0)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict as dd
H, W = map(int, input().split())
S = [input() for _ in range(H)]

i = 0
color = []
edge = dd(lambda: dd(int))
for h in range(H):
  for w in range(W):
    color.append(S[h][w])
    if w != 0:
      j = i-1
      if S[h][w-1] != S[h][w]:
        edge[i][j] = 1
        edge[j][i] = 1
    if h != 0:
      j = i-W
      if S[h-1][w] != S[h][w]:
        edge[i][j] = 1
        edge[j][i] = 1
    i += 1

visited = [False] * i
def dfs(k):
  black = 1 if color[k] == '#' else 0
  white = 1 if color[k] == '.' else 0
  visited[k] = True
  for dst in edge[k]:
    if not visited[dst]:
      b, w = dfs(dst)
      black += b
      white += w
  return black, white

ans = 0
for k in range(i):
  black, white = dfs(k)
  ans += black * white
print(ans)

Fixed submission:
from collections import defaultdict as dd
H, W = map(int, input().split())
S = [input() for _ in range(H)]

i = 0
color = []
edge = dd(lambda: dd(int))
for h in range(H):
  for w in range(W):
    color.append(S[h][w])
    if w != 0:
      j = i-1
      if S[h][w-1] != S[h][w]:
        edge[i][j] = 1
        edge[j][i] = 1
    if h != 0:
      j = i-W
      if S[h-1][w] != S[h][w]:
        edge[i][j] = 1
        edge[j][i] = 1
    i += 1

visited = [False] * i
ans = 0
for k in range(i):
  if not visited[k]:
    count = { '#': 0, '.': 0 }
    queue = set([k])
    while queue:
      j = queue.pop()
      count[color[j]] += 1
      visited[j] = True
      for dst in edge[j]:
        if not visited[dst]:
          queue.add(dst)
    ans += count['#'] * count['.']
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
A = []
V = []
for i in range(N):
  a, v = map(int, input().split())
  A.append(a)
  V.append(v)

dp = [[0] * (W+1)]
for i in range(N)[::-1]:
  a = []
  for w in range(W+1):
    if A[i] > w:
      a.append(dp[-1][w])
    else:
      a.append(
        dp[-1][w]
        if dp[-1][w] > dp[-1][w-A[i]] + V[i]
        else dp[-1][w-A[i]] + V[i]
      )
  dp.append(a)

print(dp[-1][W])

Fixed submission:
N, W = map(int, input().split())
A = []
V = []
for i in range(N):
  a, v = map(int, input().split())
  A.append(a)
  V.append(v)

dp = [0] * (W+1)
for i in range(N)[::-1]:
  a = dp[:]
  for w in range(W+1):
    if A[i] <= w and a[w] < dp[w-A[i]] + V[i]:
      a[w] = dp[w-A[i]] + V[i]
  dp = a

print(dp[W])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(500)
N, W = map(int, input().split())
A = []
V = []
for i in range(N):
  a, v = map(int, input().split())
  A.append(a)
  V.append(v)

memo = {}
def dp(i, w):
  if (i, w) in memo:
    return memo[(i, w)]
  ret = None
  if i == N:
    ret = 0
  else:
    ret = dp(i+1, w)
    if A[i] <= w:
      ret2 = dp(i+1, w - A[i]) + V[i]
      ret = ret if ret > ret2 else ret2
  memo[(i, w)] = ret
  return ret

print(dp(0, W))

Fixed submission:
N, W = map(int, input().split())
A = []
V = []
for i in range(N):
  a, v = map(int, input().split())
  A.append(a)
  V.append(v)

dp = [0] * (W+1)
for i in range(N)[::-1]:
  a = dp[:]
  for w in range(W+1):
    if A[i] <= w and a[w] < dp[w-A[i]] + V[i]:
      a[w] = dp[w-A[i]] + V[i]
  dp = a

print(dp[W])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(500)
N, W = map(int, input().split())
A = []
V = []
for i in range(N):
  a, v = map(int, input().split())
  A.append(a)
  V.append(v)

memo = {}
def dp(i, w):
  if (i, w) in memo:
    return memo[(i, w)]
  ret = None
  if i == N:
    ret = 0
  else:
    ret = dp(i+1, w)
    if A[i] <= w:
      ret2 = dp(i+1, w - A[i]) + V[i]
      ret = ret if ret > ret2 else ret2
  memo[(i, w)] = ret
  return ret

print(dp(0, W))

Fixed submission:
N, W = map(int, input().split())
A = []
V = []
for i in range(N):
  a, v = map(int, input().split())
  A.append(a)
  V.append(v)

dp = [0] * (W+1)
for i in range(N)[::-1]:
  a = dp[:]
  for w in range(W+1):
    if A[i] <= w and a[w] < dp[w-A[i]] + V[i]:
      a[w] = dp[w-A[i]] + V[i]
  dp = a

print(dp[W])
Buggy python submission (verdict: Runtime Error):
import math
import bisect
N, M = map(int, input().split())
rootM = math.sqrt(M)

factors = set()
for i in range(1, math.ceil(rootM)):
  if M % i == 0:
    factors.add(i)
    factors.add(M // i)
factarr = sorted(list(factors))
print(M // factarr[bisect.bisect_left(factarr, N)])

Fixed submission:
import math
import bisect
N, M = map(int, input().split())
rootM = math.sqrt(M)

factors = set()
for i in range(1, math.ceil(rootM)+1):
  if M % i == 0:
    factors.add(i)
    factors.add(M // i)
factarr = sorted(list(factors))
print(M // factarr[bisect.bisect_left(factarr, N)])
Buggy python submission (verdict: Runtime Error):
N = int(input())
ps = [list(map(int, input().split())) for _ in range(N)]

prev = None
for x, y in ps:
  mandist = abs(x) + abs(y)
  if prev is not None and mandist % 2 != prev:
    print('-1')
    exit()
  prev = mandist % 2

isodd = mandist % 2
m = 39 if isodd else 40
print(m)
print(' '.join(['1'] * m))
for x, y in ps:
  mandist = abs(x) + abs(y)
  ans = 'RL' * ((m - mandist) // 2)
  if x >= 0:
    ans += 'R' * x
  else:
    ans += 'L' * (-x)
  if y >= 0:
    ans += 'U' * y
  else:
    ans += 'D' * (-y)
  print(ans)

Fixed submission:
N = int(input())
ps = [list(map(int, input().split())) for _ in range(N)]

prev = None
for x, y in ps:
  mandist = abs(x) + abs(y)
  if prev is not None and mandist % 2 != prev:
    print('-1')
    exit()
  prev = mandist % 2

isodd = mandist % 2
ds = [2 ** i for i in range(32)] # 10^9 より大きくなるように適当に
ds = ds[::-1]
if isodd:
  m = 32
else:
  m = 33
  ds += [1]

print(m)
print(' '.join(list(map(str, ds))))
for x, y in ps:
  px = py = 0
  ans = ''
  for d in ds:
    dx = x - px
    dy = y - py
    if abs(dx) >= abs(dy):
      if dx >= 0:
        ans += 'R'
        px += d
      else:
        ans += 'L'
        px -= d
    else:
      if dy >= 0:
        ans += 'U'
        py += d
      else:
        ans += 'D'
        py -= d
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
l = len(s)

if s[0] != '1' or s[-2] != '1' or s[-1] != '0':
  print('-1')
  exit()
if s[:-1] != s[:-1][::-1]:
  print('-1')
  exit()

# 1頂点に全部ついた状態から始める
e = [list(range(2, l+1))] + [[] for _ in range(l-1)]
now = 0
h = (l-1) // 2
for i in range(h, 0, -1):
  c = s[i]
  if c == '0':
    continue
  # now の木から子をi個取り出して繋げる
  nowl = len(e[now])
  e[l-i-1] = e[now][-i:]
  e[now] = e[now][:nowl-i]
  now = l-i-1

for i, arr in enumerate(e):
  for a in arr:
    print(i+1, a)

Fixed submission:
s = input()
l = len(s)

if s[0] != '1' or s[-2] != '1' or s[-1] != '0':
  print('-1')
  exit()
if s[:-1] != s[:-1][::-1]:
  print('-1')
  exit()

# 1頂点に全部ついた状態から始める
e = [l] + [-1] * (l-1)
now = 0
h = (l-1) // 2
for i in range(h, 0, -1):
  c = s[i]
  if c == '0':
    continue
  # now の木から子をi個取り出して繋げる
  e[now] = l - i
  e[l-i-1] = l
  now = l-i-1

for i, a in enumerate(e):
  for j in range(i+2, a+1):
    print(i+1, j)
Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())

head1num = 0
while S[head1num] == '1':
  head1num += 1

if K <= head1num:
  print(1)
else:
  print(S[head1num])

Fixed submission:
S = input() + '#'
K = int(input())

head1num = 0
while S[head1num] == '1':
  head1num += 1

if K <= head1num:
  print(1)
else:
  print(S[head1num])
Buggy python submission (verdict: Runtime Error):
import math
T = int(input())
for _ in range(T):
  A, B, C, D = map(int, input().split())
  if B > D or B > A:
    print('No')
    continue
  if C >= B - 1:
    print('Yes')
    continue
  a = A % B
  step = math.gcd(B, D)
  k = (B - a + step - 1) // step - 1
  if C - a < k * step:
    print('No')
  else:
    print('Yes')

Fixed submission:
def gcd(a, b):
  while b > 0:
    a, b = b, a % b
  return a

T = int(input())
for _ in range(T):
  A, B, C, D = map(int, input().split())
  if B > D or B > A:
    print('No')
    continue
  if C >= B - 1:
    print('Yes')
    continue
  a = A % B
  step = gcd(B, D)
  k = (B - a + step - 1) // step - 1
  if C - a < k * step:
    print('No')
  else:
    print('Yes')
Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
vals = [1]

tmp = 6
while tmp <= 100000:
  vals.append(tmp)
  tmp *= 6

tmp = 9
while tmp <= 100000:
  vals.append(tmp)
  tmp *= 9

vals.sort()

dp = [0] + [float('inf')] * N
for n in range(1, N+1):
  i = 0
  while vals[i] <= n:
    dp[n] = min(dp[n], dp[n-vals[i]]+1)
    i += 1

print(dp[N])

Fixed submission:
N = int(input())
vals = [1]

tmp = 6
while tmp <= 100000:
  vals.append(tmp)
  tmp *= 6

tmp = 9
while tmp <= 100000:
  vals.append(tmp)
  tmp *= 9

vals.sort()

dp = [0] + [float('inf')] * N
for n in range(1, N+1):
  i = 0
  while i < len(vals) and vals[i] <= n:
    dp[n] = min(dp[n], dp[n-vals[i]]+1)
    i += 1

print(dp[N])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())

accLeft = [0]
accRight = [0]

tmp = 0
for c in S:
  tmp += int(c == 'W')
  accLeft.append(tmp)
accLeft.append(0)

tmp = 0
for c in S[::-1]:
  tmp += int(c == 'E')
  accRight = [tmp] + accRight
accRight = [0] + accRight

print(min([accLeft[i-1] + accRight[i+1] for i in range(1, N+1)]))

Fixed submission:
N = int(input())
S = list(input())

accLeft = [0]
accRight = [0]

tmp = 0
for c in S:
  tmp += int(c == 'W')
  accLeft.append(tmp)
accLeft.append(0)

tmp = 0
for c in S[::-1]:
  tmp += int(c == 'E')
  accRight.append(tmp)
accRight.append(0)
accRight = accRight[::-1]

print(min([accLeft[i-1] + accRight[i+1] for i in range(1, N+1)]))