Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,q = map(int, input().split())
tree = [set() for i in range(n+1)]
for _ in range(n-1):
  a,b = map(int, input().split())
  tree[a].add(b)
  tree[b].add(a)
lazy = [0]*(n+1)
ans = [0]*(n+1)
cnt = 0

for _ in range(q):
  x,v = map(int, input().split())
  lazy[x] += v

def dfs(v,p,tree):
  ans[v] += lazy[v]
  for x in tree[v]:
    if x == p:
      continue
    lazy[x] += lazy[v]
    dfs(x,v,tree)
  lazy[v] = 0
  return

dfs(1,0,tree)

print(" ".join(map(str,ans[1:])))


Fixed submission:
n,q = map(int, input().split())
tree = [set() for i in range(n+1)]
for _ in range(n-1):
  a,b = map(int, input().split())
  tree[a].add(b)
  tree[b].add(a)
lazy = [0]*(n+1)
cnt = 0

for _ in range(q):
  x,v = map(int, input().split())
  lazy[x] += v

que = [(1,0)]
while que:
  v,p = que.pop()
  for x in tree[v]:
    if x == p:
      continue
    lazy[x] += lazy[v]
    que.append((x,v))

print(" ".join(map(str,lazy[1:])))

Buggy python submission (verdict: Runtime Error):
n,q = map(int, input().split())
tree = [set() for i in range(n+1)]
for _ in range(n-1):
  a,b = map(int, input().split())
  tree[a].add(b)
  tree[b].add(a)
lazy = [0]*(n+1)
ans = [0]*(n+1)
cnt = 0

for _ in range(q):
  x,v = map(int, input().split())
  lazy[x] += v

def dfs(v,p,tree):
  ans[v] += lazy[v]
  for x in tree[x]:
    if x == p:
      continue
    lazy[x] += lazy[v]
    dfs(x,v,tree)
  lazy[v] = 0
  return

dfs(1,0,tree)

print(" ".join(map(str,ans[1:])))

Fixed submission:
n,q = map(int, input().split())
tree = [set() for i in range(n+1)]
for _ in range(n-1):
  a,b = map(int, input().split())
  tree[a].add(b)
  tree[b].add(a)
lazy = [0]*(n+1)
cnt = 0

for _ in range(q):
  x,v = map(int, input().split())
  lazy[x] += v

que = [(1,0)]
while que:
  v,p = que.pop()
  for x in tree[v]:
    if x == p:
      continue
    lazy[x] += lazy[v]
    que.append((x,v))

print(" ".join(map(str,lazy[1:])))
Buggy python submission (verdict: Runtime Error):
import heapq as h
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
e6 = 10**6
q = [-b[i]*e6-i for i in range(n)]
q.sort()
cnt = 0
while q:
  w = -h.heappop(q)
  v, i = divmod(w, e6)
  u = b[i-1] + b[(i+1)%n]
  if v < u or a[i] == v: continue
  elif a[i] > v: print(-1); exit(0)
  t = (v-a[i])//u
  if not t: print(-1); exit(0)
  cnt += t
  b[i] -= t*u
  if b[i] > a[i]:
    h.heappush(q,-b[i]*e6-i)
print(cnt if a==b else -1)

Fixed submission:
mod = 998244353
n = int(input())
a = list(map(lambda x: ord(x)%3, list(input())))
g = [list() for _ in range(3)]
for i in range(3*n):
  g[a[i]].append(i)
l = [0]*3*n
for i in range(n):
  a, b, c = sorted([g[0][i], g[1][i], g[2][i]])
  l[b] = 1
  l[c] = 2
ans = 1
for i in range(n):
  ans = ans * (i+1) % mod
c = 0
for x in l:
  if x == 0:
    c += 1
  elif x == 1:
    ans = ans * c % mod
    c -= 1
for x in reversed(l):
  if x == 2:
    c += 1
  elif x == 1:
    ans = ans * c % mod
    c -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def Lagrange_interpolation(X, Y, mod): # O(N**2)
    n = len(X) - 1
    for i in range(n+1):
        t = 1
        for j in range(n+1):
            if i != j:
                t = t * (X[i] - X[j]) % mod
        Y[i] = Y[i] * modinv(t, mod) % mod

    cur, nxt = 0, 1
    dp = [[0]*(n+2) for _ in range(2)]
    dp[0][0], dp[0][1] = -X[0], 1
    for i in range(1, n+1):
        for j in range(n+2):
            dp[nxt][j] = dp[cur][j] * -X[i] % mod
            if j:
                dp[nxt][j] = (dp[nxt][j] + dp[cur][j-1]) % mod
        cur, nxt = nxt, cur
    xinv = [modinv(v, mod) for v in X]
    ret = [0]*(n+1)
    for i in range(n+1):
        if Y[i] == 0:
            continue # 0割り対策
        if X[i] == 0:
            for j in range(n+1):
                ret[j] = (ret[j] + dp[cur][j+1] * Y[i]) % mod
        else:
            ret[0] = (ret[0] - dp[cur][0] * xinv[i] * Y[i]) % mod
            pre = -dp[cur][0] * xinv[i] % mod
            for j in range(1, n+1):
                ret[j] = (ret[j] - (dp[cur][j] - pre) * xinv[i] * Y[i]) % mod
                pre = (pre - dp[cur][j]) * xinv[i] % mod
    return ret

p = int(input())
a = list(map(int, input().split()))
x = list(range(p))
res = Lagrange_interpolation(x, a, p)
print(*res)

Fixed submission:
def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def Lagrange_interpolation(X, Y, mod): # O(N**2)
    n = len(X) - 1
    for i in range(n+1):
        t = 1
        for j in range(n+1):
            if i != j:
                t = t * (X[i] - X[j]) % mod
        Y[i] = Y[i] * modinv(t, mod) % mod

    cur, nxt = 0, 1
    dp = [[0]*(n+2) for _ in range(2)]
    dp[0][0], dp[0][1] = -X[0], 1
    for i in range(1, n+1):
        for j in range(n+2):
            dp[nxt][j] = dp[cur][j] * -X[i] % mod
            if j:
                dp[nxt][j] = (dp[nxt][j] + dp[cur][j-1]) % mod
        cur, nxt = nxt, cur
    xinv = [modinv(v, mod) for v in X]
    ret = [0]*(n+1)
    for i in range(n+1):
        if Y[i] == 0:
            continue # 0割り対策
        if X[i] == 0:
            for j in range(n+1):
                ret[j] = (ret[j] + dp[cur][j+1] * Y[i]) % mod
        else:
            ret[0] = (ret[0] - dp[cur][0] * xinv[i] * Y[i]) % mod
            pre = -dp[cur][0] * xinv[i] % mod
            for j in range(1, n+1):
                ret[j] = (ret[j] - (dp[cur][j] - pre) * xinv[i] * Y[i]) % mod
                pre = (pre - dp[cur][j]) * xinv[i] % mod
    return ret

p = int(input())
a = list(map(int, input().split()))
x = list(range(p))
res = Lagrange_interpolation(x, a, p)
print(*res)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == "?":
        for t in range(10):
            for k in range(13):
                dp[i+1][(k*10+t)%13] += dp[i][k]
        for k in range(13):
            dp[i+1][k] %= mod
    else:
        t = int(s[i])
        for k in range(13):
            dp[i+1][(k*10+t)%13] += dp[i][k]
print(dp[n][5])

Fixed submission:
s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == "?":
        for t in range(10):
            for k in range(13):
                dp[i+1][(k*10+t)%13] += dp[i][k]
        for k in range(13):
            dp[i+1][k] %= mod
    else:
        t = int(s[i])
        for k in range(13):
            dp[i+1][(k*10+t)%13] += dp[i][k]
print(dp[n][5])
Buggy python submission (verdict: Time Limit Exceeded):
def bi(l,x,m):
    ok = m
    ng = -1
    while ok - ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

def bi2(l,x,c,m):
    ok = c
    ng = -1
    while ok - ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return l[:ok] + [x] + l[ok:c] + l[c+1:]

n = int(input())
a = [int(input()) for _ in range(n)]
t = [a[0]]
m = 1
for x in a[1:]:
    c = bi(t,x,m)
    if c == m:
        t.append(x)
        m += 1
    else:
        t = bi2(t,x,c,m)
print(m)

Fixed submission:
def bi(l,x):
    ok = len(l)
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
print(m)

Buggy python submission (verdict: Time Limit Exceeded):
def bi(l,x,m):
    ok = m
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x,m) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
        t.sort(reverse=True) 
print(m)


Fixed submission:
def bi(l,x):
    ok = len(l)
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
print(m)

Buggy python submission (verdict: Time Limit Exceeded):
def bi(l,x):
    ok = len(l)
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
        t.sort(reverse=True) 
print(m)

Fixed submission:
def bi(l,x):
    ok = len(l)
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
print(m)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
mx = 10**10
for i in range(n):
    if a[i] < mx:
        mx = a[i]
        mi =  i
a = a[i:]+a[:i]
for v in range(0,2*(a[0]+1),2):
    mou[0] = v
    for i in range(1,n):
        mou[i] = (a[i-1]-mou[i-1]//2)*2
        if mou[i]<0:
            break
    else:
        if (mou[-1]+mou[0])//2 == a[-1]:
            ans = mou[n-i:]+mou[:n-i]
            break
print(" ".join(map(str,ans)))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
for i in range(1,n):
  mou[i*2%n] =  mou[(i-1)*2%n] + (a[i*2%n-1]-a[(i-1)*2%n])*2
mous = 0
for i in range(n):
  mous += a[i]-mou[i]
p = mous//n
for i in range(n):
  mou[i] += p
print(" ".join(map(str,mou)))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
mx = 10**10
for i in range(n):
    if a[i] < mx:
        mx = a[i]
        mi =  i
a = a[i:]+a[:i]
for v in range(0,2*(a[0]+1),2):
    mou[0] = v
    for i in range(1,n):
        mou[i] = (a[i-1]-mou[i-1]//2)*2
        if mou[i]<0:
            break
    else:
        if (mou[-1]+mou[0])//2 == a[-1]:
            ans = mou[n-i:]+mou[:n-i]
            break
print(" ".join(map(str,ans)))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
for i in range(1,n):
  mou[i*2%n] =  mou[(i-1)*2%n] + (a[i*2%n-1]-a[(i-1)*2%n])*2
mous = 0
for i in range(n):
  mous += a[i]-mou[i]
p = mous//n
for i in range(n):
  mou[i] += p
print(" ".join(map(str,mou)))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
mx = 10**10
for i in range(n):
    if a[i] < mx:
        mx = a[i]
        mi =  i
a = a[i:]+a[:i]
for v in range(0,2*(a[0]+1),2):
    mou[0] = v
    for i in range(1,n):
        mou[i] = (a[i-1]-mou[i-1]//2)*2
    if (mou[-1]+mou[0])//2 == a[-1]:
        ans = mou[n-i:]+mou[:n-i]
        break
print(" ".join(map(str,ans))) 

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
for i in range(1,n):
  mou[i*2%n] =  mou[(i-1)*2%n] + (a[i*2%n-1]-a[(i-1)*2%n])*2
mous = 0
for i in range(n):
  mous += a[i]-mou[i]
p = mous//n
for i in range(n):
  mou[i] += p
print(" ".join(map(str,mou)))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
mx = 10**10
for i in range(n):
    if a[i] < mx:
        mx = a[i]
        mi =  i
a = a[i:]+a[:i]
for v in range(0,2*(a[0]+1),2):
    mou[0] = v
    for i in range(1,n):
        mou[i] = (a[i-1]-mou[i-1]//2)*2
    if (mou[-1]+mou[0])//2 == a[-1]:
        ans = mou[n-i:]+mou[:n-i]
        break
print(" ".join(map(str,ans))) 

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
for i in range(1,n):
  mou[i*2%n] =  mou[(i-1)*2%n] + (a[i*2%n-1]-a[(i-1)*2%n])*2
mous = 0
for i in range(n):
  mous += a[i]-mou[i]
p = mous//n
for i in range(n):
  mou[i] += p
print(" ".join(map(str,mou)))
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
mod = 10**9+7
gr = [set() for _ in range(n+1)]
for _ in range(n-1):
    a,b = map(int,input().split())
    gr[a].add(b)
    gr[b].add(a)
par = [0]*(n+1)
ans = [0]*(n+1)
done = [0]*(n+1)
done[1] = -1
done[0] = -2
def dfs2(gr,p,v,done,ans):
    ans[v] = k-2-done[p]
    for x in gr[v]:
        if x == p:
            continue
        dfs2(gr,v,x,done,ans)
        done[v] += 1
    return
dfs2(gr,0,1,done,ans)
m = 1
for x in ans[1:]:
    m = m*x%mod
print(m)

Fixed submission:
import sys
sys.setrecursionlimit(200000)
n,k = map(int,input().split())
mod = 10**9+7
gr = [set() for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    gr[a].add(b)
    gr[b].add(a)
ans = [0]*(n+1)
done = [0]*(n+1)
done[1] = -1
done[0] = -2
def dfs2(gr,p,v,done,ans):
    ans[v] = k-2-done[p]
    for x in gr[v]:
        if x == p:
            continue
        dfs2(gr,v,x,done,ans)
        done[v] += 1
    return
dfs2(gr,0,1,done,ans)
m = 1
for x in ans[1:]:
    m = m*x%mod
print(m)
Buggy python submission (verdict: Runtime Error):
n,k = map(int, input().split())
k -= n*(n-1)//2 - (n-1)
if k > 0:
  print(-1)
else:
  i = 2
  j = 3
  tl = [(1,f) for f in range(2,n+1)]
  for _ in range(-k):
    tl.append((i,j))
    j += 1
    if j > n:
      i += 1
      j = i+1
print(len(tl))
for x,y in tl:
  print(x,y)

Fixed submission:
n,k = map(int, input().split())
k -= n*(n-1)//2 - (n-1)
if k > 0:
  print(-1)
  exit()
else:
  i = 2
  j = 3
  tl = [(1,f) for f in range(2,n+1)]
  for _ in range(-k):
    tl.append((i,j))
    j += 1
    if j > n:
      i += 1
      j = i+1
print(len(tl))
for x,y in tl:
  print(x,y)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
mod = 10**9 + 7
dp = [[1]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j]*(s[i] != t[j])) % mod
print(dp[n][m])

Fixed submission:
n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
mod = 10**9 + 7
dp = [[1]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j]*(s[i] != t[j])) % mod
print(dp[n][m])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict as ddict
d = ddict(int)
n = int(input())
l = [tuple(map(int, input().split())) for _ in range(n)]
l.sort()
for i in range(n-1):
  for j in range(i+1,n):
    curx = l[j][0] - l[i][0]
    cury = l[j][1] - l[i][1]
    d[(curx,cury)] += 1
print(n-max(d.values()))

Fixed submission:
from collections import defaultdict as ddict
d = ddict(int)
d[0] = 0
n = int(input())
l = [tuple(map(int, input().split())) for _ in range(n)]
l.sort()
for i in range(n-1):
  for j in range(i+1,n):
    curx = l[j][0] - l[i][0]
    cury = l[j][1] - l[i][1]
    d[(curx,cury)] += 1
print(n-max(d.values()))
Buggy python submission (verdict: Runtime Error):
l = map(int,input().split())
print(sum(*l)-max(*l))


Fixed submission:
l = list(map(int,input().split()))
print(sum(l)-max(l))

Buggy python submission (verdict: Runtime Error):
l = map(int,input().split())
print(sum(l)-max(l))


Fixed submission:
l = list(map(int,input().split()))
print(sum(l)-max(l))

Buggy python submission (verdict: Runtime Error):
l* = map(int,input().split())
print(sum(l)-max(l))

Fixed submission:
l = list(map(int,input().split()))
print(sum(l)-max(l))
Buggy python submission (verdict: Runtime Error):
n = int(input())
l = []
for i in range(1,n+1):
  s,p = input(),split()
  l.append(s,-int(p),i)
l.sort()
for x in l:
  print(x[2])
       

Fixed submission:
n = int(input())
l = []
for i in range(1,n+1):
  s,p = input().split()
  l.append((s,-int(p),i))
l.sort()
for x in l:
  print(x[2])
Buggy python submission (verdict: Runtime Error):
n,m,k = map(int, input().split())
mod = 10**9+7
def cc(a,b):
  b = min(b,a-b)
  tot = 1
  for i in range(1,b+1):
    tot = (tot*(a-i+1)//i)%mod
  return tot
xans = 0
yans = 0
for i in range(1,n):
  xans+=i*(n-i)*m**2
  xans%=mod
for j in range(1,m):
  yans+=i*(m-i)*n**2
  yans%=mod
print((xans+yans)*cc(n*m-2,k-2)%mod)

Fixed submission:
n,m,k = map(int, input().split())
n_ = n*m
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
  
x = sum(i*(n-i) for i in range(n))%mod
y = sum(i*(m-i) for i in range(m))%mod
ans = (x*m**2 + y*n**2)%mod*nCr(n*m-2,k-2)%mod
print(ans)

Buggy python submission (verdict: Runtime Error):
n,m,k = map(int, input().split())
mod = 10**9+7
def cc(a,b):
  b = min(b,a-b)
  tot = 1
  for i in range(1,b+1):
    tot = (tot*(a-i+1)//i)%mod
    return tot
xans = 0
yans = 0
for i in range(1,n):
  xans+=i*(n-i)*m**2
  xans%=mod
for j in range(1,m):
  yans+=i*(m-i)*n**2
  yans%=mod
print((xans+yans)*cc(n*m-2,k-2)%mod)

Fixed submission:
n,m,k = map(int, input().split())
n_ = n*m
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
  
x = sum(i*(n-i) for i in range(n))%mod
y = sum(i*(m-i) for i in range(m))%mod
ans = (x*m**2 + y*n**2)%mod*nCr(n*m-2,k-2)%mod
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
l = [list() for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

dep = [n]*n
def dfs(v,t,p):
  dep[v] = t
  for x in l[v]:
    if x == p:
      continue
    dfs(x,t+1,v)
  return

dfs(0,0,-1)
p = dep.index(max(dep))
dep = [n]*n
dfs(p,0,-1)
q = max(dep)-1
print("First" if q%3 else "Second") 

Fixed submission:
n = int(input())
l = [list() for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

def dfs(p):
  dep = [None]*n
  dep[p] = 0
  q = [p]
  while q:
    v = q.pop()
    for x in l[v]:
      if dep[x] is None:
        dep[x] = dep[v] + 1
        q.append(x)
  return dep
      
dep = dfs(0)
p = dep.index(max(dep))
dep = dfs(p)
q = max(dep)-1
print("First" if q%3 else "Second")
Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int, input().split())
s = "#" + input() + "#"
l = [tuple(input().split()) for _ in range(q)]
d = {"L":-1, "R":1}
def move(x):
  for i in l:
    if i[0] == s[x]:
      x += d[i[1]]
    if x in [0,n+1]:
      break
  return x
def isr(x):
  if move(x) == n+1:
    return True
  else:
    return False
def isl(x):
  if move(x) == 0:
    return True
  else:
    return False
hi1,hi2 = n+1,n+1
lo1,lo2 = 0,0
while hi1-lo1>1:
  mid1 = (hi1+lo1)//2
  if isr(mid1):
    hi1 = mid1
  else:
    lo1 = mid1
while hi2-lo2>1:
  mid2 = (hi2+lo2)//2
  if isl(mid2):
    lo2 = mid2
  else:
    hi2 = mid2
print(max(hi1-lo2-1,0))

Fixed submission:
n,q = map(int, input().split())
s = "#" + input() + "#"
l = [tuple(input().split()) for _ in range(q)]
def move(x,g):
  for i in l:
    if i[0] == s[x]:
      x += (i[1]=="R") or -1
  return x==g
hi1 = n+1
lo1,lo2 = 0,0
while hi1-lo1>1:
  mid1 = (hi1+lo1)//2
  if move(mid1,n+1):
    hi1 = mid1
  else:
    lo1 = mid1
hi2 = hi1
while hi2-lo2>1:
  mid2 = (hi2+lo2)//2
  if move(mid2,0):
    lo2 = mid2
  else:
    hi2 = mid2
print(hi1-lo2-1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
mod = 10**9+7
a = [1]*16
no = [0,0]
for _ in range(n-2):
  b = [0]*16
  b[0] = a[0] + a[4] + a[8] + a[12]
  b[1] = a[0] + a[4] + a[12]
  b[2] = a[0] + a[4] + a[8] + a[12]
  b[3] = a[0] + a[4] + a[8] + a[12]
  b[4] = a[1] + a[5] + a[9] + a[13]
  b[5] = a[1] + a[5] + a[9] + a[13]
  b[6] = a[5] + a[9] + a[13]
  b[7] = a[1] + a[5] + a[9] + a[13]
  b[8] = a[2] + a[6] + a[9] + a[14]
  b[9] = a[6] + a[9] + a[14] - no[0] - no[1]
  b[10] = a[2] + a[6] + a[9] + a[14]
  b[11] = a[2] + a[6] + a[9] + a[14]
  b[12] = a[3] + a[7] + a[10] + a[15]
  b[13] = a[3] + a[7] + a[10] + a[15] - no[1]
  b[14] = a[3] + a[7] + a[10] + a[15]
  b[15] = a[3] + a[7] + a[10] + a[15]
  no[0] = a[2]
  no[1] = a[3]
  a = b
  for i in range(16):
    a[i] %= mod
print(sum(a))


Fixed submission:
print(input().translate(str.maketrans("ATGC","TACG")))
Buggy python submission (verdict: Runtime Error):
n = int(input())
l = [int(input()) for _ in range(n)] + [0]
p = [0]
for i in range(n):
  if l[i] != l[i+1]:
    p.append(l[i])
lp = len(p)
l = [0]*lp
l[0] = 1
d = dict()
for i in range(1,lp):
  l[i] = l[i-1]
  if p[i] in d:
    l[i] += l[p[i]]
  d[p[i]] = i
print(l[-1])

Fixed submission:
n = int(input())
oth = [int(input()) for _ in range(n)]
mod = 10**9 + 7
l = list()
for x in oth:
    if l and l[-1] == x:
        continue
    l.append(x)
lenl = len(l)
last = [-1] * 200001
l2 = [-1] * 200001
for i, a in enumerate(l):
    l2[i] = last[a]
    last[a] = i

dp = [0] * lenl
dp[0] = 1
for i in range(1, lenl):
    prev = 0 if l2[i] < 0 else dp[l2[i]]
    dp[i] = (dp[i - 1] + prev) % mod
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
n,a,b,c = map(int, input().split())
l = [int(input()) for _ in range(n)]
def dfs(k,p,q,r):
  if k == n:
    if min(a,b,c) > 0:
      return abs(p-a)+abs(q-b)+abs(r-c)-30
    else:
      return 10**5
  t1 = dfs(k+1,p,q,r)
  t2 = dfs(k+1,p+l[k],q,r)+10
  t3 = dfs(k+1,p,q+l[k],r)+10
  t2 = dfs(k+1,p,q,r+l[k])+10
  return min(t1,t2,t3,t4)

print(dfs(0,0,0,0))

Fixed submission:
n,a,b,c = map(int, input().split())
l = [int(input()) for _ in range(n)]
def dfs(k,p,q,r):
  if k == n:
    if min(p,q,r) > 0:
      return abs(p-a)+abs(q-b)+abs(r-c)-30
    else:
      return 10**7
  t1 = dfs(k+1,p,q,r)
  t2 = dfs(k+1,p+l[k],q,r)+10
  t3 = dfs(k+1,p,q+l[k],r)+10
  t4 = dfs(k+1,p,q,r+l[k])+10
  return min(t1,t2,t3,t4)

print(dfs(0,0,0,0))

Buggy python submission (verdict: Runtime Error):
n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]
cnt = 0
for k in [a,b,c]:
    ans = 0
    for i in range(1, 257):
        s = 0
        for j in range(n):
            if i & 2**j:
                if s > 0:
                    s += 10
                s += l[j]
        v = abs(k - s)
        if v < ans:
            ans = v
            x = i
    cnt += ans
    for j in range(n):
        if x & 2**j:
            l[j] = 0
print(cnt)

Fixed submission:
n,a,b,c = map(int, input().split())
l = [int(input()) for _ in range(n)]
def dfs(k,p,q,r):
  if k == n:
    if min(p,q,r) > 0:
      return abs(p-a)+abs(q-b)+abs(r-c)-30
    else:
      return 10**7
  t1 = dfs(k+1,p,q,r)
  t2 = dfs(k+1,p+l[k],q,r)+10
  t3 = dfs(k+1,p,q+l[k],r)+10
  t4 = dfs(k+1,p,q,r+l[k])+10
  return min(t1,t2,t3,t4)

print(dfs(0,0,0,0))

Buggy python submission (verdict: Runtime Error):
n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]
cnt = 0
for k in [a,b,c]:
    ans = 0
    for i in range(1, 257):
        s = 0
        for j in range(7):
            if i & 2**j:
                if s > 0:
                    s += 10
                s += l[j]
        v = abs(k - s)
        if v < ans:
            ans = v
            x = i
    cnt += ans
    for j in range(7):
        if x & 2**j:
            l[j] = 0
print(cnt)

Fixed submission:
n,a,b,c = map(int, input().split())
l = [int(input()) for _ in range(n)]
def dfs(k,p,q,r):
  if k == n:
    if min(p,q,r) > 0:
      return abs(p-a)+abs(q-b)+abs(r-c)-30
    else:
      return 10**7
  t1 = dfs(k+1,p,q,r)
  t2 = dfs(k+1,p+l[k],q,r)+10
  t3 = dfs(k+1,p,q+l[k],r)+10
  t4 = dfs(k+1,p,q,r+l[k])+10
  return min(t1,t2,t3,t4)

print(dfs(0,0,0,0))