Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):

"""
bitDPというらしい
dp[i][j] = i番目の入力に対して、状態jを実現する最小値
j : 2^12通り。それぞれの宝箱をbitと見立てる
"""

N, M = map(int, input().split())
INF = 10**5+1


dp = [[INF for i in range(2**N+1)] for j in range(1100)]
dp[0][0] = 0

for i in range(M):
    dp[i+1] = [v for v in dp[i]]
    cost,b = map(int, input().split())
    boxes = list(map(int, input().split()))
    status = 0
    for box in boxes:
        status += 2**(box-1)
    for j in range(2**N):
        if dp[i][j] != INF:
            nxt = status | j
            dp[i+1][nxt] = min(dp[i][j] + cost, dp[i][nxt], dp[i+1][nxt])

ans = dp[M][2**N-1]
if ans == INF:
    print(-1)
else:
    print(ans)

# for i in range(M):
#     print(dp[i])

Fixed submission:

"""
bitDPというらしい
dp[i][j] = i番目の入力に対して、状態jを実現する最小値
j : 2^12通り。それぞれの宝箱をbitと見立てる
"""

N, M = map(int, input().split())
INF = 10**5+1


dp = [[INF for i in range(2**N+1)] for j in range(1100)]
dp[0][0] = 0

for i in range(M):
    dp[i+1] = [v for v in dp[i]]
    cost,b = map(int, input().split())
    boxes = list(map(int, input().split()))
    status = 0
    for box in boxes:
        status += 2**(box-1)
    for j in range(2**N):
        if dp[i][j] != INF:
            nxt = status | j
            dp[i+1][nxt] = min(dp[i][j] + cost, dp[i][nxt], dp[i+1][nxt])

ans = dp[M][2**N-1]
if ans == INF:
    print(-1)
else:
    print(ans)

# for i in range(M):
#     print(dp[i])
Buggy python submission (verdict: Runtime Error):
h,w,a,b = map(int, input().split())
if h == 1:
    S = "1"*a+"0"*(w-a)
    print(S)
elif w == 1:
    S = [1]*b+[0]*(h-b)
    for s in S:
        print(s)
elif h >= 2 and w >= 2:
    if b*w != a*h:
        print("No")
        exit()
    else:
        for i in range(h):
            S = ["0"]*w
            init = i//b
            for j in range(a*init,a*(init+1)):
                S[j] = "1"
            print("".join(S))

Fixed submission:
h,w,a,b = map(int, input().split())
if h == 1:
    S = "1"*a+"0"*(w-a)
    print(S)
elif w == 1:
    S = [1]*b+[0]*(h-b)
    for s in S:
        print(s)
elif h >= 2 and w >= 2:
    # if b*w != a*h:
    #     print("No")
    #     exit()
    # else:
    for i in range(h):
        # print(a,i)
        if i < b:
            S = "1"*a + "0"*(w-a)
        else:
            S = "0"*a + "1"*(w-a)
        print(S)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

dp = [[0] * (N+1) for i in range(N+1)]

for i in range(N-1,-1,-1):
    for j in range(N-1,-1,-1):
        # print(i,j)
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1 

# print(dp)
ans = 0
for i in range(N):
    for j in range(N):
       val = min(abs(i-j),dp[i][j])
       ans = max(val,ans)

print(ans) 

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

dp = [[0] * (N+1) for i in range(N+1)]

for i in range(N-1,-1,-1):
    for j in range(N-1,-1,-1):
        # print(i,j)
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1 

# print(dp)
ans = 0
for i in range(N):
    for j in range(N):
       val = min(abs(i-j),dp[i][j])
       ans = max(val,ans)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+10)
    def add(self,x,w):
        while x <= self.n:
            self.bit[x] += w
            x += (x&-x)
            
    def sum(self,x):
        cnt = 0
        while x > 0:
            cnt += self.bit[x]
            x -= (x&-x)
        return cnt

    def psum(self,a,b):
        return self.sum(b-1)-self.sum(a-1)

    def bisect(self, w):
        # 値がw以上となる最小のindex
        x = 0
        k = 1
        while k < self.n:
            k *= 2            
        while k > 0:
            # x+kの値がwより小さければ、treeの右側に移動
            if x+k<=self.n and self.bit[x+k] < w:
                w -= self.bit[x+k]
                x += k            
            k //= 2
        return x + 1
    
n = int(input())
ps = list(map(int, input().split()))

# 1-indexedにする
inds = [0]*(n+1)
for i, p in enumerate(ps):
    inds[p] = i+1
bit = BIT(n)
cnt = 0
# 大きい順に
for p in range(n,0,-1):
    ind = inds[p]
    nl = bit.sum(ind)   # 自分より左にあるやつの個数
    nr = (n-p) - nl     # 自分より左にあるやつの個数    
    bit.add(ind, 1)     # bitを1で埋めていく
    # 自分を含んで左右のインデックスを見る(端注意)
    ixl2 = bit.bisect(nl-1) if nl >= 2 else 0
    ixl1 = bit.bisect(nl)   if nl >= 1 else 0
    ixr1 = bit.bisect(nl+2) if nr >= 1 else n+1
    ixr2 = bit.bisect(nl+3) if nr >= 2 else n+1
    tmp = 0
    tmp += (ixl1-ixl2)*(ixr1-ind) #左側から1個取る
    tmp += (ixr2-ixr1)*(ind-ixl1) #右側から1個取る
    cnt += p*tmp    
    # print("p",p,nl,nr,"ind",ixl2,ixl1,ind,ixr1,ixr2,tmp,cnt)
print(cnt)

Fixed submission:
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+10)
    def add(self,x,w):
        while x <= self.n:
            self.bit[x] += w
            x += (x&-x)
            
    def sum(self,x):
        cnt = 0
        while x > 0:
            cnt += self.bit[x]
            x -= (x&-x)
        return cnt

    def psum(self,a,b):
        return self.sum(b-1)-self.sum(a-1)

    def bisect(self, w):
        # 値がw以上となる最小のindex
        x = 0
        k = 1
        while k < self.n:
            k *= 2            
        while k > 0:
            # x+kの値がwより小さければ、treeの右側に移動
            if x+k<=self.n and self.bit[x+k] < w:
                w -= self.bit[x+k]
                x += k            
            k //= 2
        return x + 1
    
n = int(input())
ps = list(map(int, input().split()))

# 1-indexedにする
inds = [0]*(n+1)
for i, p in enumerate(ps):
    inds[p] = i+1
bit = BIT(n)
cnt = 0
# 大きい順に
for p in range(n,0,-1):
    ind = inds[p]
    nl = bit.sum(ind)   # 自分より左にあるやつの個数
    nr = (n-p) - nl     # 自分より左にあるやつの個数    
    bit.add(ind, 1)     # bitを1で埋めていく
    # 自分を含んで左右のインデックスを見る(端注意)
    ixl2 = bit.bisect(nl-1) if nl >= 2 else 0
    ixl1 = bit.bisect(nl)   if nl >= 1 else 0
    ixr1 = bit.bisect(nl+2) if nr >= 1 else n+1
    ixr2 = bit.bisect(nl+3) if nr >= 2 else n+1
    tmp = 0
    tmp += (ixl1-ixl2)*(ixr1-ind) #左側から1個取る
    tmp += (ixr2-ixr1)*(ind-ixl1) #右側から1個取る
    cnt += p*tmp    
    # print("p",p,nl,nr,"ind",ixl2,ixl1,ind,ixr1,ixr2,tmp,cnt)
print(cnt)
Buggy python submission (verdict: Runtime Error):

cnt = 0
for i in range(3):
    if S[i] == T[i]:
        cnt += 1
print(cnt)

Fixed submission:
S = input()
R = input()
cnt = 0
for s,r in zip(S,R):
    if s==r:
        cnt += 1
print(cnt)
Buggy python submission (verdict: Runtime Error):
N = int(input())
vs = sorted(list(map(int,input().split())))
ans = (vs[0]+v[1])/2
for v in vs[2:]:
  ans = (ans + v)/2
print(ans)

Fixed submission:

N = int(input())
vs  = sorted(list(map(int, input().split())))
ans = 0
ans = vs[0]+vs[1]
for i,v in enumerate(vs[2:]):
    ans += v*2**(i+1)
ans/=2**(N-1)
print(ans)
Buggy python submission (verdict: Runtime Error):

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

# 木
G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))

## クエリを覚えておく
scores = [0]*N
for i in range(Q):
    p,x = map(int, input().split())
    scores[p-1] += x 

# 和をとっていく
ans = [0]*N
ans[0] = scores[0]
used = [False] * N

"""
dfs TLEする。なんで
"""
# import sys
# sys.setrecursionlimit(100000)
# def dfs(G, v):
#    # vを訪問済みにする
#    used[v] = True
#    #グラフ中の次のVについて
#    for next_v in G[v]:
#        if used[next_v]: continue
#        ans[next_v] = ans[v] + scores[next_v]
#        dfs(G, next_v)
# dfs(G,0)
# print(*ans)

# 木をBFSをする
from collections import deque
used = [False] * N
used[0] = True # 始めどこから行くか
q = deque([0])
while len(q) > 0:
    v = q.popleft()
    Vs = G[v]
    for next_v in Vs: 
        if not used[next_v]:
            q.append(next_v)
            ans[next_v] = ans[v] + scores[next_v]
            used[next_v] = True
print(*ans)

Fixed submission:
from bisect import bisect_right
from collections import defaultdict

S = input()
S_set = set(S)
d = defaultdict(list)
for i,s in enumerate(S):
    d[s].append(i)
# print(d)

T = input()
T_set = set(T)
for t in T_set:
    if t not in S_set:
        print(-1)
        exit()

cnt = 0
loop = 0
prev = -1

for t in T:
    num = d[t]
    a = bisect_right(num,prev)
    # print(prev,a,num)
    
    if a >= len(num):
        loop += 1
        a = 0
    prev = num[a]

print(prev+1+(loop)*len(S))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
alphabet = "abcdefghijklmnopqrstuvwxyz"

from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    s = input()
    num = 0
    for i,a in enumerate(alphabet):
        if s.count(a) == 10:
            continue #アナグラムはない
        num += s.count(a)*10**i
    d[num] += 1

ans = 0

for key in d.keys():
    ans += d[key]*(d[key]-1)//2
print(ans)

Fixed submission:
N = int(input())
alphabet = "abcdefghijklmnopqrstuvwxyz"

from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    s = input()
    num = 0
    sorted(alphabet)
    for i,a in enumerate(alphabet):
        if s.count(a) == 10:
            continue #アナグラムはない
        num += s.count(a)*10**i
    d[num] += 1

ans = 0

for key in d.keys():
    ans += d[key]*(d[key]-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)

S_inv = S[::-1]
mod = 10**9 +7
dp = [[0] * 13 for i in range(10**6)]

dp[0][0] = 1
for i,s in enumerate(S_inv):
    keta = i%6
    if s != "?":
        for j in range(13):
            amari = (j + int(s)*10**keta)%13 #桁を追加
            dp[i+1][amari] += dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                amari = (j + k*10**keta)%13
                dp[i+1][amari] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= mod
print(dp[N][5]%mod)

Fixed submission:
S = input()
N = len(S)

mod = 10**9 +7
dp = [[0] * 13 for i in range(10**6)]

dp[0][0] = 1
for i,s in enumerate(S):
    keta = (N-i-1)%6
    if s != "?":
        for j in range(13):
            amari = (j + int(s)*10**keta)%13 #桁を追加
            dp[i+1][amari] += dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                amari = (j + k*10**keta)%13
                dp[i+1][amari] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= mod
print(dp[N][5]%mod)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int, input().split()))

A_all = sum(As)//2

ans = []
for i in range(N):
    cnt = 0
    for j in range(N//2):
        index = i+2*j
        cnt += As[index%N]
    ans.append((A_all-cnt)*2)
 
a = ""
for i in range(1,N+1):
    a += str(ans[i%N])+" "
print(a)

Fixed submission:
N = int(input())
As = list(map(int, input().split()))
A_all = sum(As)//2
ans = [0]*N

a0 = sum(As[1:N:2])
ans[0] = (A_all-a0)
for i in range(1,N):
    ans[i] = As[i-1]-ans[i-1]

ans = [a*2 for a in ans]
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys 
sys.setrecursionlimit(10**6)
n, k = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
    
mod = 10**9 + 7
def P(x,y):
    # x = k - 2
    # y = n - 1
    cnt = 0
    ans = 1
    waru = 1
    while cnt < y:
        ans *= (x-cnt)
        ans %= mod
        cnt += 1
    return ans%mod


ans = 1
def dfs(v,p):
    global ans
    us = edges[v]
    for u in us:
        if u == p: continue
        if len(edges[u]) == 1: ans *= 1
        ans *= P(k-2, len(edges[u])-1)   
        dfs(u,v)

dfs(0,-1)
n0 = len(edges[0])
a = P(k,n0+1)
# print(n0,a)
ans *= a
ans %= mod
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(100000)

from collections import deque
# 木構造を作る
N,K = map(int, input().split())
G = [[] for i in range(N)]
for i in range(N-1):
    # グラフに頂点を追加(距離があるときは,u,vの後に入れる)
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))

# print(G)

used = [False] * N
used[0] = True
mod = 10**9 + 7
cnt = 0
ans = K
def dfs(G, i, v):
    global cnt
    global ans 
    #グラフ中の次のVについて
    used[v] = True
    cnt += 1
    numv = 0
    for next_v in G[v]:
        # すでに見られていたら無視
        if used[next_v]: continue
        numv += 1
        ans %= mod
        if i <= 1:
            ans *= K-i-numv
        else:
            ans *= K - 1 - numv
        # print("v",v,"n{},cnt{},ans{}".format(numv,cnt,ans))
        ans %= mod
        dfs(G,i+1, next_v)



dfs(G,0,0)
print(ans%mod)
Buggy python submission (verdict: Runtime Error):
from scipy.special import comb
N,K = map(int, input().split())
mod = 10**9 +7
m = 0
if N - K > K - 1:
    m = K
else:
    m = N - K + 1

for i in range(1,m+1):
    a = comb(K-1, i-1, exact=True)%mod
    b = comb(N-K+1, N-K-i+1, exact=True)%mod
    print(a*b%mod)

Fixed submission:
from operator import mul
from functools import reduce

N,K = map(int, input().split())
mod = 10**9 +7

if N - K > K - 1:
    m = K
else:
    m = N - K + 1

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

for i in range(1,K+1):
    if i <= m:
        a = cmb(K-1, i-1)%mod
        b = cmb(N-K+1, N-K-i+1)%mod
        print(a*b%mod)
    else:
        print(0)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int, input().split())
# As = [N//i for i in range(1,int(N**0.5)+1)]
# Bs = [As[i]-As[i+1] for i in range(len(As)-1)]
# Bs[0] -= 1
# Bs = sorted(Bs) + [1]
As = [] 
for i in range(1,int(N**0.5)+1):
    As.append(i)
    if N//i != i:
        As.append(N//i)
As = sorted(As,reverse=False)
nums = []
for i in range(len(As)-1):
    nums.append(As[i+1]-As[i])
nums = [1] + nums
nums.reverse()
mod = 10**9 + 7
ans = 0
dp = [[0] * len(As) for i in range(K+1)]


from itertools import accumulate
# print(As,nums)
dp[0][0] = 1
for i in range(K):
    # 1だと全通り分が成り立つし、Nだと1通り。
    # それぞれ種別にまとまっているので、それらをかける
    acc = list(accumulate(dp[i]))
    for j in range(len(As)):
        dp[i+1][len(As)-j-1] = acc[j]*nums[j]%mod
print(sum(dp[K])%mod)


Fixed submission:
from itertools import accumulate

N,K = map(int, input().split())
As = [] 
for i in range(1,int(N**0.5)+1):
    As.append(i)
    if N//i != i:
        As.append(N//i)
As = sorted(As,reverse=False)
nums = []
for i in range(len(As)-1):
    nums.append(As[i+1]-As[i])
nums = [1] + nums
nums.reverse()
mod = 10**9 + 7
ans = 0
dp = [[0] * len(As) for i in range(K+1)]


dp[0][0] = 1
for i in range(K):
    # 1だと全通り分が成り立つし、Nだと1通り。
    # それぞれ種別にまとまっているので、それらをかける
    acc = list(accumulate(dp[i]))
    for j in range(len(As)):
        dp[i+1][len(As)-j-1] = acc[j]*nums[j]%mod
print(sum(dp[K])%mod)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int, input().split())
Ss = list(map(int, input().split()))
Ts = list(map(int, input().split()))
mod = 10**9 + 7

x = 2160
dp = [[0]*x for i in range(x)]
for i in range(N):
    for j in range(M):
        if Ss[i] == Ts[j]:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] + 1) % mod
        else:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j])%mod

print((dp[N][M]+1)%mod)

Fixed submission:
N,M = map(int, input().split())
Ss = list(map(int, input().split()))
Ts = list(map(int, input().split()))
mod = 10**9 + 7

x = 2160
dp = [[0]*x for i in range(x)]
for i in range(N):
    for j in range(M):
        if Ss[i] == Ts[j]:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] + 1) % mod
        else:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j])%mod

print((dp[N][M]+1)%mod)
Buggy python submission (verdict: Runtime Error):
N = int(input())
xys = []
for i in range(N):
    x,y = map(int, input().split())
    xys.append((x,y))

xys.sort()
diffs = []
count = []
# 全探索して、一番共通項が多い差分から計算する
for i in range(N):
    for j in range(i+1,N):
        x1,y1 = xys[i]
        x2,y2 = xys[j]
        diff = (x1-x2, y1-y2)
        if diff not in diffs:
            diffs.append(diff)
            count.append(1)
        else:
            k = diffs.index(diff)
            count[k] += 1

print(N-max(count))

Fixed submission:
N = int(input())
xys = []
for i in range(N):
    x,y = map(int, input().split())
    xys.append((x,y))

xys.sort()
diffs = []
count = []
# 全探索して、一番共通項が多い差分から計算する
for i in range(N):
    for j in range(i+1,N):
        x1,y1 = xys[i]
        x2,y2 = xys[j]
        diff = (x1-x2, y1-y2)
        if diff not in diffs:
            diffs.append(diff)
            count.append(1)
        else:
            k = diffs.index(diff)
            count[k] += 1
if N == 1:
    print(1)
else:
    print(N-max(count))
Buggy python submission (verdict: Runtime Error):

"""
左・上からゴリゴリ攻めていくパターン
一回通ったかどうかのフラグが必要
"""

cnt = [[0] * (W+1) for i in range(H+1)]
# 横
for i in range(H):
    done = [False] * (W+1)
    for j in range(W):
        l = 0
        if done[j]: continue
        if S[i][j] == ".":
            while j+l < W:
                if S[i][j+l] == ".":
                    l += 1
                else:
                    break
        for k in range(j,j+l):
            cnt[i][k] += l
            done[k] = True

# 縦
for j in range(W):
    done = [False] * (H+1)
    for i in range(H):
        l = 0
        if done[i]: continue
        if S[i][j] == ".":
            while i+l < H:
                if S[i+l][j] == ".":
                    l += 1
                else:
                    break
        for k in range(i,i+l):
            cnt[k][j] += l
            done[k] = True

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,cnt[i][j])
print(ans-1)

Fixed submission:
H,W = map(int,input().split())
S = [input() for i in range(H)]

# 4方向の累積和をとって計算する
Rs = [[0]*W for i in range(H)]
Ls = [[0]*W for i in range(H)]
Ds = [[0]*W for i in range(H)]
Us = [[0]*W for i in range(H)]

for i in range(H):
    tmp = 0
    # 順方向(左にどれだけ伸びてるか)
    for j in range(W):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            Ls[i][j] = tmp
    tmp = 0
    # 逆方向(右にどれだけ伸びてるか)
    for j in reversed(range(W)):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            Rs[i][j] = tmp

# 行列転置 順番逆にするだけ
for j in range(W):
    tmp = 0
    # 順方向 上にどれだけ伸びているか
    for i in range(H):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            Us[i][j] = tmp
    tmp = 0
    # 順方向 下にどれだけ伸びているか
    for i in reversed(range(H)):
        if S[i][j] == '#':
            tmp = 0
        else:
            tmp += 1
            Ds[i][j] = tmp

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#': 
            continue
        # 上下左右に伸びた数を重なっている部分引く
        tmp = Rs[i][j] + Ls[i][j] + Ds[i][j] + Us[i][j] - 3
        ans = max(ans, tmp)
print(ans)
Buggy python submission (verdict: Runtime Error):
"""
imos
"""
N, M = map(int,input().split())

from itertools import accumulate
imos = [0]*(N+1)
for i in range(M):
    L,R = map(int,input().split())
    imos[L] += 1
    imos[R+1] -= 1
acc = list(accumulate(imos))
print(sum([1 for a in acc if a == M]))

Fixed submission:
N, M = map(int,input().split())
Ls,Rs = [],[]
for i in range(M):
    L,R = map(int,input().split())
    Ls.append(L)
    Rs.append(R)

print(max(0,min(Rs)-max(Ls)+1))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int,input().split())
A = [0] * (N+1)
for i in range(M):
    L,R = map(int,input().split())
    for i in range(L,R+1):
        A[i] += 1
print(sum([1 for a in A if a == M]))

Fixed submission:
N, M = map(int,input().split())
Ls,Rs = [],[]
for i in range(M):
    L,R = map(int,input().split())
    Ls.append(L)
    Rs.append(R)

print(max(0,min(Rs)-max(Ls)+1))

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N, M = map(int,input().split())
A = np.zeros(N+1)
for i in range(M):
    L,R = map(int,input().split())
    A[L:R+1] += 1
print(sum([1 for a in A if a == M]))

Fixed submission:
N, M = map(int,input().split())
Ls,Rs = [],[]
for i in range(M):
    L,R = map(int,input().split())
    Ls.append(L)
    Rs.append(R)

print(max(0,min(Rs)-max(Ls)+1))
Buggy python submission (verdict: Runtime Error):
import heapq
N,M = map(int,input().split())
As = list(map(int,input().split()))

As = sorted(As)
BCs = []
heapq.heapify(BCs)
for i in range(M):
    B,C =   map(int,input().split())
    heapq.heappush(BCs,(-C,B))

ind = 0
ans = 0
flg = False
for i in range(M):
    _C,B = heapq.heappop(BCs)
    for i in range(B):
        if As[ind+i] > -_C:
            flg = True
            ind += i
            break
        else:
            ans -= _C
    if flg: break
    ind += B
ans += sum(As[ind:])
print(ans)

Fixed submission:
import heapq
N,M = map(int,input().split())
As = list(map(int,input().split()))

As = sorted(As)
BCs = []
heapq.heapify(BCs)
for i in range(M):
    B,C =   map(int,input().split())
    heapq.heappush(BCs,(-C,B))

ind = 0
ans = 0
flg = False
for i in range(M):
    _C,B = heapq.heappop(BCs)
    for i in range(B):
        if As[ind+i] > -_C:
            flg = True
            ind += i
            break
        else:
            ans -= _C
        if ind+i+1 > N-1:
            flg = True
            ind += i+1
            break
    if flg: break
    ind += B
ans += sum(As[ind:])
print(ans)
Buggy python submission (verdict: Runtime Error):
M, K = map(int,input().split())


if M == 1 and K == 1:
    print(-1)
elif M==1 and K == 0:
    print("0 0 1 1")
elif K >= 2**M:
    print(-1)
else:
    else:
        M = [i for i in range(2**M)]
        M.remove(K)
        ans = M + [K] + M[::-1] + [K]
        anstr = ""
        for a in ans:
            anstr += str(a) + " "
        print(anstr[:-1])

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


if M == 1 and K == 1:
    print(-1)
elif M==1 and K == 0:
    print("0 0 1 1")
elif K >= 2**M:
    print(-1)
else:
    M = [i for i in range(2**M)]
    M.remove(K)
    ans = M + [K] + M[::-1] + [K]
    anstr = ""
    for a in ans:
        anstr += str(a) + " "
    print(anstr[:-1])
Buggy python submission (verdict: Time Limit Exceeded):
R, B, G,N = map(int,input().split())


cnt = 0
ball = 0
a = sorted([R,G,B])
for r in range(N//a[0]+1):
    ball = r*a[0]
    for b in range((N-ball)//a[1]+1):
        if N-ball >= 0 and (N-ball-b*a[1])%a[2] == 0:
            cnt += 1

print(cnt)

Fixed submission:
R, B, G, N = map(int,input().split())
 
 
cnt = 0
ball = 0
a = sorted([R,G,B])
for r in range(N//a[0]+1):
    ball = r*a[0]
    for b in range((N-ball)//a[1]+1):
        if N-ball >= 0 and (N-ball-b*a[1])%a[2] == 0:
            cnt += 1
 
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int,input().split())
coords = []
blacks = deque([])
for i in range(H):
    rows = list(input())
    coords.append(rows)
    for j,row in enumerate(rows):
        if row == "#":
            blacks.append((i,j,0))

ans = 0
while len(blacks) > 0: 
    h,w,dist = blacks.popleft()
    ans = max(dist,ans)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni = h + di
        nj = w + dj
        if 0 <= ni < H and 0 <= nj < W:
            if coords[ni][nj] == ".":
                blacks.append((ni,nj,dist+1))
                coords[ni][nj] = "#"

print(ans)

Fixed submission:
from collections import deque

H, W = map(int,input().split())
coords = []
blacks = deque([])
for i in range(H):
    rows = list(input())
    coords.append(rows)
    for j,row in enumerate(rows):
        if row == "#":
            blacks.append((i,j,0))

ans = 0
while len(blacks) > 0: 
    h,w,dist = blacks.popleft()
    ans = max(dist,ans)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni = h + di
        nj = w + dj
        if 0 <= ni < H and 0 <= nj < W:
            if coords[ni][nj] == ".":
                blacks.append((ni,nj,dist+1))
                coords[ni][nj] = "#"

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()
K = int(input())

letter = S[K]
ans = ""
for s in S:
    if s != letter:
        ans += "*"
    else:
        ans += s
print(ans)

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

letter = S[K-1]

ans = ""
for s in S:
    if s != letter:
        ans += "*"
    else:
        ans += s
print(ans)