Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
assert len(A) == N

class multiset:
    def __init__(self, L):
        self.dic = {}
        for a in L:
            if a not in self.dic:
                self.dic[a] = 0
            self.dic[a] += 1
    def has(self, x):
        return x in self.dic and self.dic[x] > 0
    def remove(self, x):
        if self.has(x):
            self.dic[x] -= 1

def check(x, y):
    a = x
    S = multiset(A)
    S.remove(x)
    S.remove(y)
    for i in range(N - 2):
        z = (x ^ y)
        if not S.has(z):
            return False
        S.remove(z)
        x, y = y, z
    return a == x ^ y

yes = any(check(A[0], a) for a in A[1:])
print('Yes' if yes else 'No')

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
assert len(A) == N

def yes():
    S = set(A)
    if A.count(0) == N:
        return True
    if N % 3 != 0:
        return False
    if len(S) == 3:
        a, b, c = tuple(S)
        return all(A.count(x) == N // 3 for x in S) and a ^ b == c
    if len(S) == 2:
        a, b = tuple(S)
        return (a == 0 or b == 0) and A.count(0) == N // 3

print('Yes' if yes() else 'No')

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
assert len(A) == N

class multiset:
    def __init__(self, L):
        self.dic = {}
        for a in L:
            if a not in self.dic:
                self.dic[a] = 0
            self.dic[a] += 1
    def has(self, x):
        return x in self.dic and self.dic[x] > 0
    def remove(self, x):
        if self.has(x):
            self.dic[x] -= 1

def check(x, y):
    a = x
    S = multiset(A)
    S.remove(x)
    S.remove(y)
    for i in range(N - 2):
        z = (x ^ y)
        if not S.has(z):
            return False
        S.remove(z)
        x, y = y, z
    return a == x ^ y

yes = any(check(A[0], a) for a in A[1:])
print('Yes' if yes else 'No')


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
assert len(A) == N

def yes():
    S = set(A)
    if A.count(0) == N:
        return True
    if N % 3 != 0:
        return False
    if len(S) == 3:
        a, b, c = tuple(S)
        return all(A.count(x) == N // 3 for x in S) and a ^ b == c
    if len(S) == 2:
        a, b = tuple(S)
        return (a == 0 or b == 0) and A.count(0) == N // 3

print('Yes' if yes() else 'No')
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate

N  = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]

# earliest deadline first
AB.sort(key=lambda x: x[1])

# 累積時刻とデッドライン
tB = accumulate(AB, lambda x, y: (x[0] + y[0], y[1]))

yes = all(t <= b for t, b in tB)
print('Yes' if yes else 'No')


Fixed submission:
from itertools import accumulate

N  = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]

# earliest deadline first
AB.sort(key=lambda x: x[1])

# 累積時刻とデッドライン
tB = accumulate(AB, lambda x, y: (x[0] + y[0], y[1]))

yes = all(t <= b for t, b in tB)
print('Yes' if yes else 'No')
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()))
assert len(S) == N
assert len(T) == M

modulo = 10 ** 9 + 7

# tab[j][i] = S[i] == T[j]
tab = [[s == t for s in S] for t in T]

# 番兵
for t in tab:
    t.append(1)
tab.append([1] * (len(S) + 1))

# 右下から計算
for j in range(M - 1, -1, -1):
    for i in range(N - 1, -1, -1):
        v  = tab[j + 1][i] + tab[j][i + 1]
        v -= 0 if tab[j][i] else tab[j + 1][i + 1]
        tab[j][i] = v % modulo

print(tab[0][0])


Fixed submission:
N, M =      map(int, input().split())
S    = list(map(int, input().split()))
T    = list(map(int, input().split()))
assert len(S) == N
assert len(T) == M

modulo = 10 ** 9 + 7

# tab[j][i] = S[i] == T[j]
tab = [[s == t for s in S] for t in T]

# 番兵
for t in tab:
    t.append(1)
tab.append([1] * (len(S) + 1))

# 右下から計算
for j in range(M - 1, -1, -1):
    for i in range(N - 1, -1, -1):
        v  = tab[j + 1][i] + tab[j][i + 1]
        v -= 0 if tab[j][i] else tab[j + 1][i + 1]
        tab[j][i] = v % modulo

print(tab[0][0])
Buggy python submission (verdict: Time Limit Exceeded):
M, K = map(int, input().split())

if K == 0:
    a = sum([[i, i] for i in range(2 ** M)], [])

elif 2 <= M and K < 2 ** M:
    a  = [K] + [i for i in range(2 ** M - 1, -1, -1) if i != K]
    a += [K] + [i for i in range(2 ** M) if i != K]

else:
    a = [-1]

print(' '.join(map(str, a)))


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

if K == 0:
    a  = [i for i in range(2 ** M - 1, -1, -1)]
    a += [i for i in range(2 ** M)]
elif 2 <= M and K < 2 ** M:
    a  = [K] + [i for i in range(2 ** M - 1, -1, -1) if i != K]
    a += [K] + [i for i in range(2 ** M) if i != K]

else:
    a = [-1]

print(' '.join(map(str, a)))
Buggy python submission (verdict: Runtime Error):
import itertools

N, K = map(int, input().split())
S = input()
assert len(S) == N

# list of run-length
runlen = [len(list(g)) for k, g in itertools.groupby(S)]

# runlen starts and ends with the length of a run of '1'
if S[0] == '0':
    runlen = [0] + runlen
if S[-1] == '0':
    runlen = runlen + [0]

# list of sum of runlen[i : i + k]
k = 2 * K + 1
sublen = [sum(runlen[i : i + k]) for i in range(0, N - k, 2)]

print(max(sublen))


Fixed submission:
import itertools

N, K = map(int, input().split())
S = input()
assert len(S) == N

# list of run-length
runlen = [len(list(g)) for k, g in itertools.groupby(S)]

# runlen starts and ends with the length of a run of '1'
if S[0] == '0':
    runlen = [0] + runlen
if S[-1] == '0':
    runlen = runlen + [0]

# list of sum of runlen[i : i + k]
k = 2 * K + 1
s = sum(runlen[:k])
sublen = [s]
for i in range(2, N - k, 2):
    s -= sum(runlen[i - 2 : i])
    s += sum(runlen[i - 2 + k : i + k])
    sublen.append(s)

print(max(sublen))
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
assert len(S) == N

def solve(l, r):
    return sum(1 for i in range(l - 1, r - 1) if S[i : i + 2] == 'AC')

for i in range(Q):
    l, r = map(int, input().split())
    print(solve(l, r))

Fixed submission:
N, Q = map(int, input().split())
S = input()
assert len(S) == N

AC = [S[i : i + 2] == 'AC' for i in range(len(S) - 1)]

nAC = [0]  # nAC[i] == the number of 'AC' whose head 'A' is in S[:i]
for i in range(len(AC)):
    nAC.append(nAC[-1] + (1 if AC[i] else 0))

def solve(l, r):
    return nAC[r - 1] - nAC[l - 1]

for i in range(Q):
    l, r = map(int, input().split())
    print(solve(l, r))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
b = [int(x) for x in input().split()]

def solve(b):
    if len(b) == 0:
        return []
    ls = [(i+1, b[i]) for i in range(len(b)) if i+1 == b[i]]
    ls.sort(reverse=True)
    for i, _ in ls:
        a = solve(b[:i-1] + b[i:])
        if a != None:
            return [i] + a
    return None

a = solve(b)
if a == None:
    print(-1)
else:
    a.reverse()
    print('\n'.join(map(str, a)))

Fixed submission:
N = int(input())
b = [int(x) for x in input().split()]

def solve(b):
    if len(b) == 0:
        return []
    if any(i+1 < b[i] for i in range(len(b))):
        return None
    erasable = [i+1 for i in range(len(b)) if i+1 == b[i]]
    if len(erasable) == 0:
        return None
    i = erasable[-1]  # 一番右から消す
    a = solve(b[:i-1] + b[i:])
    if a != None:
        return [i] + a
    return None

a = solve(b)
if a == None:
    print(-1)
else:
    a.reverse()
    print('\n'.join(map(str, a)))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
b = [int(x) for x in input().split()]

def solve(b):
    if len(b) == 0:
        return []
    for i in range(len(b)):
        if b[i] == i+1:
            a = solve(b[:i] + b[i+1:])
            if a != None:
                return [i+1] + a
    return None

a = solve(b)
if a == None:
    print(-1)
else:
    a.reverse()
    print('\n'.join(map(str, a)))

Fixed submission:
N = int(input())
b = [int(x) for x in input().split()]

def solve(b):
    if len(b) == 0:
        return []
    if any(i+1 < b[i] for i in range(len(b))):
        return None
    erasable = [i+1 for i in range(len(b)) if i+1 == b[i]]
    if len(erasable) == 0:
        return None
    i = erasable[-1]  # 一番右から消す
    a = solve(b[:i-1] + b[i:])
    if a != None:
        return [i] + a
    return None

a = solve(b)
if a == None:
    print(-1)
else:
    a.reverse()
    print('\n'.join(map(str, a)))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
b = [int(x) for x in input().split()]

def solve(b):
    if len(b) == 0:
        return []
    for i in range(len(b)):
        if b[i] == i+1:
            a = solve(b[:i] + b[i+1:])
            if a != None:
                return [i+1] + a
    return None

a = solve(b)
if a == None:
    print(-1)
else:
    a.reverse()
    print('\n'.join(map(str, a)))


Fixed submission:
N = int(input())
b = [int(x) for x in input().split()]

def solve(b):
    if len(b) == 0:
        return []
    if any(i+1 < b[i] for i in range(len(b))):
        return None
    erasable = [i+1 for i in range(len(b)) if i+1 == b[i]]
    if len(erasable) == 0:
        return None
    i = erasable[-1]  # 一番右から消す
    a = solve(b[:i-1] + b[i:])
    if a != None:
        return [i] + a
    return None

a = solve(b)
if a == None:
    print(-1)
else:
    a.reverse()
    print('\n'.join(map(str, a)))
Buggy python submission (verdict: Runtime Error):
import math

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

d = max(d for d in range(1, math.ceil(M / (N - 1))) if M % d == 0)
print(d)


Fixed submission:
import math

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

if N == 1:
    print(M)
else:
    d = max(d for d in range(1, math.ceil(M / (N - 1))) if M % d == 0)
    print(d)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

def factorized(M):
    d = 2
    f = []
    while d <= M:
        count = 0
        while M % d == 0:
            M //= d
            count += 1
        if count > 0:
            f.append(count)
        d += 1
    return f

def tetra(n, m):
    x = 1
    for y in range(1, n):
        x = x * (m + y - 1) // y
    return x

x = 1
for f in factorized(M):
    x *= tetra(N, f + 1)
    x %= 10 ** 9 + 7

print(x)


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

def factorized(M):
    d = 2
    f = []
    while d <= M:
        count = 0
        while M % d == 0:
            M //= d
            count += 1
        if count > 0:
            f.append(count)
        d += 1
        if d < M and d * d > M:
            d = M
    return f

def tetra(n, m):
    x = 1
    for y in range(1, n):
        x = x * (m + y - 1) // y
    return x

x = 1
for f in factorized(M):
    x *= tetra(N, f + 1)
    x %= 10 ** 9 + 7

print(x)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

def factorized(M):
    d = 2
    f = []
    while d <= M:
        count = 0
        while M % d == 0:
            M //= d
            count += 1
        if count > 0:
            f.append(count)
        d += 1
    return f

def tetra(n, m):
    x = 1
    for y in range(1, n):
        x = x * (m + y - 1) // y
    return x

x = 1
for f in factorized(M):
    x *= tetra(N, f + 1)
    x %= 10 ** 9 + 7

print(x)


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

def factorized(M):
    d = 2
    f = []
    while d <= M:
        count = 0
        while M % d == 0:
            M //= d
            count += 1
        if count > 0:
            f.append(count)
        d += 1
        if d < M and d * d > M:
            d = M
    return f

def tetra(n, m):
    x = 1
    for y in range(1, n):
        x = x * (m + y - 1) // y
    return x

x = 1
for f in factorized(M):
    x *= tetra(N, f + 1)
    x %= 10 ** 9 + 7

print(x)
Buggy python submission (verdict: Runtime Error):
import fraction

N, X   = map(int, input().split())
x = list(map(int, input().split()))
assert len(x) == N

x.sort()

# distance between each two cities
dist = [x[i] - x[i-1] for i in range(1, len(x))]

# distance between the first city and the start point
dist.append(abs(x[0] - X))

def listgcd(xs):
    g = xs[0]
    for i in range(1, len(xs)):
        g = fraction.gcd(g, xs[i])
    return g

print(listgcd(dist))


Fixed submission:
import fractions

N, X   = map(int, input().split())
x = list(map(int, input().split()))
assert len(x) == N

x.sort()

# distance between each two cities
dist = [x[i] - x[i-1] for i in range(1, len(x))]

# distance between the first city and the start point
dist.append(abs(x[0] - X))

def listgcd(xs):
    g = xs[0]
    for i in range(1, len(xs)):
        g = fractions.gcd(g, xs[i])
    return g

print(listgcd(dist))

Buggy python submission (verdict: Runtime Error):
import math

N, X   = map(int, input().split())
x = list(map(int, input().split()))
assert len(x) == N

x.sort()

# distance between each two cities
dist = [x[i] - x[i-1] for i in range(1, len(x))]

# distance between the first city and the start point
dist.append(abs(x[0] - X))

def listgcd(xs):
    g = xs[0]
    for i in range(1, len(xs)):
        g = math.gcd(g, xs[i])
    return g

print(listgcd(dist))


Fixed submission:
import fractions

N, X   = map(int, input().split())
x = list(map(int, input().split()))
assert len(x) == N

x.sort()

# distance between each two cities
dist = [x[i] - x[i-1] for i in range(1, len(x))]

# distance between the first city and the start point
dist.append(abs(x[0] - X))

def listgcd(xs):
    g = xs[0]
    for i in range(1, len(xs)):
        g = fractions.gcd(g, xs[i])
    return g

print(listgcd(dist))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

from math import log2, floor

L = int(input())

N = floor(log2(L)) + 1
edge = []

# 長さ0の辺
for i in range(1, N):
    edge.append((i, i+1, 0))

# 長さ2**(i-1)の辺
for i in range(1, N):
    edge.append((i, i+1, 2**(i-1)))

# ここまでで長さ0,...,X-1のパスが完成
X = 2 ** (N-1)

# 残りの辺
while L > X:
    r = floor(log2(L - X))
    edge.append((r + 1, N, X))
    X += 2 ** r

# 出力
M = len(edge)
print(N, M)
for e in edge:
    print(' '.join(map(str, e)))

Fixed submission:
L = int(input())

def decompose(L):
    if L < 3:
        return [L]
    r = L % 3
    return [r] + decompose((L - r) // 3)

dec = decompose(L)

N = len(dec) + 1
edge = []

for w in range(dec[-1]):
    edge.append((N-1, N, w))

base = dec[-1]
for i in range(len(dec) - 2, -1, -1):
    for w in range(3):
        edge.append((i+1, i+2, w * base))
    base = 3 * base
    for w in range(dec[i]):
        edge.append((i+1, N, base + w))
    base += dec[i]

M = len(edge)
print(N, M)
for e in edge:
    print(' '.join(map(str, e)))

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env pypy3
# -*- coding: utf-8 -*-

from math import log2, floor

L = int(input())

N = floor(log2(L)) + 1
edge = []

# 長さ0の辺
for i in range(1, N):
    edge.append((i, i+1, 0))

# 長さ2**(i-1)の辺
for i in range(1, N):
    edge.append((i, i+1, 2**(i-1)))

# ここまでで長さ0,...,X-1のパスが完成
X = 2 ** (N-1)

# 残りの辺
while L > X:
    r = floor(log2(L - X))
    edge.append((r + 1, N, X))
    X += 2 ** r

# 出力
M = len(edge)
print(N, M)
for e in edge:
    print(' '.join(map(str, e)))

Fixed submission:
L = int(input())

def decompose(L):
    if L < 3:
        return [L]
    r = L % 3
    return [r] + decompose((L - r) // 3)

dec = decompose(L)

N = len(dec) + 1
edge = []

for w in range(dec[-1]):
    edge.append((N-1, N, w))

base = dec[-1]
for i in range(len(dec) - 2, -1, -1):
    for w in range(3):
        edge.append((i+1, i+2, w * base))
    base = 3 * base
    for w in range(dec[i]):
        edge.append((i+1, N, base + w))
    base += dec[i]

M = len(edge)
print(N, M)
for e in edge:
    print(' '.join(map(str, e)))
Buggy python submission (verdict: Runtime Error):
N, K   = map(int, input().split())
x = list(map(int, input().split()))
assert len(x) == N

m = min(x[i] - x[i-K+1] + min(abs(x[i], abs(x[i-K+1])) for i in range(K-1, N))
print(m)

Fixed submission:
N, K   = map(int, input().split())
x = list(map(int, input().split()))
assert len(x) == N

m = min(x[i] - x[i-K+1] + min(abs(x[i]), abs(x[i-K+1])) for i in range(K-1, N))
print(m)
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
from math import ceil
 
D, G = [int(t) for t in input().split()]
p = []
c = []
for i in range(D):
    p_, c_ = [int(t) for t in input().split()]
    p.append(p_)
    c.append(c_)
 
def minsolve(G, p, c, i):
    """100i点以下の問題だけでGを達成する最小問題数"""
    if i <= 0:
        return float('inf')
    n = min(ceil(G / (100 * i)), p[i-1])
    s = 100 * i * n
    if n == p[i-1]:
        s += c[i-1]
    if s >= G:
        return min(n, minsolve(G, p, c, i-1))
    else:
        return min(n + minsolve(G - s, p, c, i-1), minsolve(G, p, c, i-1))
 
m = min(minsolve(G, p, c, i) for i in range(1, D+1))
print(m)

Fixed submission:
R = int(input())

if R < 1200:
  print('ABC')
elif R < 2800:
  print('ARC')
else:
  print('AGC')
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from math import ceil

def solve(A, B, C, D):
    zaiko = A
    visited = set([zaiko])
    while zaiko >= B:
        zaiko -= B
        if zaiko > C:
            zaiko -= ceil((zaiko - C) / B) * B
            if zaiko < 0 or zaiko > C: return False
        zaiko += D
        if zaiko in visited: return True
        visited.add(zaiko)
    return False


T = int(input())
for i in range(T):
    A, B, C, D = [int(t) for t in input().split()]
    print('Yes' if solve(A, B, C, D) else 'No')

Fixed submission:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from math import ceil

def gcd(a, b):
    assert a > 0 and b > 0
    while b > 0:
        r = a % b
        a = b
        b = r
    return a

def solve(A, B, C, D):
    if A < B or D < B: return False
    if A % B > C: return False
    if D % B == 0: return True

    g = gcd(B, D)
    r = A % g  # +D -B を繰り返すと x % g == r であるxを訪れる
    # x % g == r and C < x < B である x が存在するなら False を返す
    return not (C < B - g + r)

T = int(input())
for i in range(T):
    A, B, C, D = [int(t) for t in input().split()]
    print('Yes' if solve(A, B, C, D) else 'No')
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil, floor

N = int(input())
A = [int(t) for t in input().split()]
if len(A) != N: raise

p = [A[i-1] - i for i in range(1, N+1)]

q = []
for b in p:
    q.append(sum(abs(x - b) for x in p))
print(min(q))

Fixed submission:
from math import ceil, floor

N = int(input())
A = [int(t) for t in input().split()]
if len(A) != N: raise

p = [A[i-1] - i for i in range(1, N+1)]
p.sort()

q = []
for b in p[N//2 - 1 : N//2 + 2]:
    q.append(sum(abs(x - b) for x in p))
print(min(q))
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/python
# coding: utf-8

from sys import stdin

memo = {}

# それぞれ z 枚目, w 枚目を持っている局面での最適解
def solve(z, w, player):
  global a, memo
  n = max(z, w) + 1  # 取り終わっている枚数
  if n == len(a): return abs(a[z] - a[w])
  if (z, w, player) in memo: return memo[(z, w, player)]

  m      = 0   if player == 0 else 1000000000
  minmax = max if player == 0 else min
  for i in range(n, len(a)):
    if player == 0: zz = i; ww = w
    else:           ww = i; zz = z
    m = minmax(m, solve(zz, ww, 1 - player))
  memo[(z, w, player)] = m
  return m

N, Z, W = map(int, stdin.readline().split())
a       = map(int, stdin.readline().split())
if len(a) != N: raise

# Z, Wを山の先頭に置く
a = [Z, W] + a

print(solve(0, 1, 0))


Fixed submission:
#!/usr/bin/python
# coding: utf-8

from sys import stdin

def solve(a):
  n = len(a)
  xmemo = [0 for i in range(n)]  # player X の手番での最適スコア
  ymemo = [0 for i in range(n)]  # player Y 　　　〃

  # 自分がj (< i) 枚目, 相手がi枚目を持っている
  for i in range(n - 2, -1, -1):
    # 自分が取り切ったときのスコア
    f = abs(a[i] - a[n - 1])
    # j, i の差が何枚でも同じ
    xmemo[i] = max([f] + [ymemo[jj] for jj in range(i + 1, n - 1)])
    ymemo[i] = min([f] + [xmemo[jj] for jj in range(i + 1, n - 1)])

  return xmemo[1]

N, Z, W = map(int, stdin.readline().split())
a       = map(int, stdin.readline().split())
if len(a) != N: raise

# Z, Wを山の先頭に置く
a = [Z, W] + a

print(solve(a))
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python

# AtCoder Beginner Contest 077
# C - Snuke Festival

from sys import stdin

def solve(As, Bs, Cs):
    # Bs :: [(b, # of bottom parts > b)]
    Bs = [(b, sum([1 for c in Cs if c > b])) for b in Bs]
    # As :: [# of mid & bottom parts > a]
    As = [sum([b[1] for b in Bs if b[0] > a]) for a in As]
    return sum(As)

N = int(stdin.readline())
As = [int(w) for w in stdin.readline().split()]
Bs = [int(w) for w in stdin.readline().split()]
Cs = [int(w) for w in stdin.readline().split()]
if len(As) != N or len(Bs) != N or len(Cs) != N: raise
print(solve(As, Bs, Cs))

Fixed submission:
#!/usr/bin/python

# AtCoder Beginner Contest 077
# C - Snuke Festival

from sys import stdin

def solve(As, Bs, Cs):
    As.sort()
    Bs.sort()
    Cs.sort()
    # Bs :: [(b, # of bottom parts > b)]
    # Bs = [(b, sum([1 for c in Cs if c > b])) for b in Bs]
    j = 0
    for i in range(len(Bs)):
        while j < len(Cs) and Bs[i] >= Cs[j]: j += 1
        Bs[i] = (Bs[i], len(Cs) - j)
    # Accumulate Bs[][1]
    for i in range(len(Bs) - 1, 0, -1):
        Bs[i-1] = (Bs[i-1][0], Bs[i-1][1] + Bs[i][1])
    # As :: [# of mid & bottom parts > a]
    # As = [sum([b[1] for b in Bs if b[0] > a]) for a in As]
    j = 0
    for i in range(len(As)):
        while j < len(Bs) and As[i] >= Bs[j][0]: j += 1
        As[i] = Bs[j][1] if j < len(Bs) else 0
    return sum(As)

N = int(stdin.readline())  # <= 1e+5
As = [int(w) for w in stdin.readline().split()]
Bs = [int(w) for w in stdin.readline().split()]
Cs = [int(w) for w in stdin.readline().split()]
if len(As) != N or len(Bs) != N or len(Cs) != N: raise
print(solve(As, Bs, Cs))
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/python

# AtCoder Beginner Contest 076
# C - Dubious Document 2

from sys import stdin

def match(S, pos, T):
  for i in range(len(T)):
    if S[pos + i] != '?' and S[pos + i] != T[i]:
      return False
  return True

def solve(S, T):
  minS = '~' * len(S)
  for pos in range(len(S) - len(T) + 1):
    # S[pos : pos + len(T)] matches T ?
    if match(S, pos, T):
      S_ = S[:pos] + T + S[pos + len(T):]       # replace the mid part with T
      S_ = [c if c != '?' else 'a' for c in S_] # replace '?' with 'a'
      if minS > S_: minS = S_
  return ''.join(minS) if minS[0] != '~' else 'UNRESTORABLE'

S = stdin.readline().strip()
T = stdin.readline().strip()
print(solve(S, T))

Fixed submission:
#!/usr/bin/python

# AtCoder Beginner Contest 076
# C - Dubious Document 2

from sys import stdin

def match(S, pos, T):
  for i in range(len(T)):
    if S[pos + i] != '?' and S[pos + i] != T[i]:
      return False
  return True

def solve(S, T):
  minS = '~' * len(S)
  for pos in range(len(S) - len(T) + 1):
    # S[pos : pos + len(T)] matches T ?
    if match(S, pos, T):
      S_ = S[:pos] + T + S[pos + len(T):]       # replace the mid part with T
      S_ = [c if c != '?' else 'a' for c in S_] # replace '?' with 'a'
      if minS > S_: minS = S_
  return ''.join(minS) if minS[0] != '~' else 'UNRESTORABLE'

S = stdin.readline().strip()
T = stdin.readline().strip()
print(solve(S, T))