Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
S = input()

arr = []
now = S[0]
if now == "1":
    count = 1
else:
    count = -1
for c in S[1:]:
    next = c
    if c == now:
        if now == "1":
            count += 1
        else:
            count -= 1
    else:
        arr.append(count)
        if now == "1":
            count = -1
            now = "0"
        else:
            count = 1
            now = "1"
arr.append(count)

anss = []
Sum = 0
if arr[0] >= 0:
    head = 0
else:
    head = 0
    arr = [0] + arr
while head+2*K <= len(arr):
    tail = head+2*K
    Sum += sum(map(abs, arr[head:tail+1]))
    anss.append(Sum)
    head += 2
    Sum = 0
if anss == []:
    ans = sum(map(abs,arr))
else:
    ans = max(anss)
print(ans)

Fixed submission:
from itertools import accumulate
N,K = map(int,input().split())
S = input()

arr = []
now = S[0]
if now == "1":
    count = 1
else:
    count = -1
for c in S[1:]:
    next = c
    if c == now:
        if now == "1":
            count += 1
        else:
            count -= 1
    else:
        arr.append(count)
        if now == "1":
            count = -1
            now = "0"
        else:
            count = 1
            now = "1"
arr.append(count)

anss = []
Sum = 0
head = 0
if arr[0] < 0:
    arr = [0] + arr
arr2 = [0] + list(accumulate(list(map(abs, arr))))
while head+2*K <= len(arr):
    tail = head+2*K
    Sum += arr2[tail+(tail < len(arr2)-1)]-arr2[head]
    #Sum += sum(map(abs, arr[head:tail+1]))
    anss.append(Sum)
    head += 2
    Sum = 0
if anss == []:
    ans = sum(map(abs,arr))
else:
    ans = max(anss)
print(ans)
Buggy python submission (verdict: Runtime Error):
H,W = map(int,input().split())
h,w = map(int,input().split())
print(H*W-h*W-wH+h*w)

Fixed submission:
H,W = map(int,input().split())
h,w = map(int,input().split())
print(H*W-h*W-w*H+h*w)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
L = [X[i+1] - X[i] for i in range(len(X)-1)]
k = 0
while k < N-1 and L != []:
    L.remove(max(L))
    k += 1
print(sum(L) if X != [] else 0)

Fixed submission:
N,M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
L = [X[i+1] - X[i] for i in range(len(X)-1)]
L.sort(reverse=True)
K = L[N-1:]
print(sum(K) if K != [] else 0)
Buggy python submission (verdict: Runtime Error):
print(int(input()) + int(input())//2)

Fixed submission:
x,y = map(int,input().split())
print(x+y//2)

Buggy python submission (verdict: Runtime Error):
print(int(input())+int(input())//2)

Fixed submission:
x,y = map(int,input().split())
print(x+y//2)
Buggy python submission (verdict: Runtime Error):
N = int(input())
T, A = map(int,input().split())
H = list(map(int,input().split()))
sa = [abs(T-0.006*H[i] - A) for i in range(N)]
print(sa.index(min(sa))+1)N = int(input())
T, A = map(int,input().split())
H = list(map(int,input().split()))
sa = [abs(T-0.006*H[i] - A) for i in range(N)]
print(sa.index(min(sa))+1)

Fixed submission:
N = int(input())
T, A = map(int,input().split())
H = list(map(int,input().split()))
sa = [abs(T-0.006*H[i] - A) for i in range(N)]
print(sa.index(min(sa))+1)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int,input().split())
L = []
for i in range(M):
    p, y = map(int,input().split())
    L.append((p,y))
PY = sorted(L, key = lambda x: x[1])
from collections import defaultdict
d = defaultdict(list)
for p,y in PY:
    d[p].append(y)
for i in range(M):
    p,y = L[i]
    print("{:06}{:06}".format(p, d[p].index(y)+1))

Fixed submission:
N, M = map(int,input().split())
L = []
for i in range(M):
    p, y = map(int,input().split())
    L.append((p,y,i))
PY = sorted(L)
from collections import defaultdict
d = defaultdict(int)
ID = [None]*M
for p,y,i in PY:
    d[p] += 1
    ID[i] = d[p]
for i in range(M):
    p,y,j = L[i]
    print("{:06}{:06}".format(p, ID[i]))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int,input().split())
L = []
for i in range(M):
    p, y = map(int,input().split())
    L.append((p,y,i))
PY = sorted(L)
from collections import defaultdict
d = defaultdict(list)
for p,y,i in PY:
    d[p].append(y)
for i in range(M):
    p,y,j = L[i]
    print("{:06}{:06}".format(p, d[p].index(y)+1))

Fixed submission:
N, M = map(int,input().split())
L = []
for i in range(M):
    p, y = map(int,input().split())
    L.append((p,y,i))
PY = sorted(L)
from collections import defaultdict
d = defaultdict(int)
ID = [None]*M
for p,y,i in PY:
    d[p] += 1
    ID[i] = d[p]
for i in range(M):
    p,y,j = L[i]
    print("{:06}{:06}".format(p, ID[i]))
Buggy python submission (verdict: Runtime Error):
import numpy as np
N,M=map(int,input().split())
S = input()
T = input()
g = np.gcd(M,N)
n = N//g
m = M//g
l = N*M // g
f = True
for i in range(g):
    a = n*i
    b = m*i
    if S[a] != T[b]:
        f = False
print(l if f else -1)

Fixed submission:
def gcd(x,y):
    a = max(x,y)
    b = min(x,y)
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b
N,M=map(int,input().split())
S = input()
T = input()
g = gcd(M,N)
n = N//g
m = M//g
l = N*M // g
f = True
for i in range(g):
    a = n*i
    b = m*i
    if S[a] != T[b]:
        f = False
print(l if f else -1)

Buggy python submission (verdict: Runtime Error):
import math
N,M=map(int,input().split())
S = input()
T = input()
g = math.gcd(N,M)
n = N//g
m = M//g
l = N*M // g
f = True
for i in range(g):
    a = n*i
    b = m*i
    if S[a] != T[b]:
        f = False
print(l if f else -1)

Fixed submission:
def gcd(x,y):
    a = max(x,y)
    b = min(x,y)
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b
N,M=map(int,input().split())
S = input()
T = input()
g = gcd(M,N)
n = N//g
m = M//g
l = N*M // g
f = True
for i in range(g):
    a = n*i
    b = m*i
    if S[a] != T[b]:
        f = False
print(l if f else -1)
Buggy python submission (verdict: Runtime Error):
import collections as c
N = int(input())
a = list(map(int,input().split()))
ue = a[0::2]
sita = a[1::2]
dictue = c.defaultdict(int)
dictsita = c.defaultdict(int)
for i in ue:
    dictue[i] += 1
for i in sita:
    dictsita[i] += 1
ue = list(dictue.items())
ue.sort(key=lambda x:x[1])
sita = list(dictsita.items())
sita.sort(key=lambda x:x[1])
m = ue[len(ue)-1]
n = sita[len(sita)-1]
if m[0] == n[0]:
    if len(ue) == 1:
        if len(sita) == 1:
            print(N//2)
        else:
            print(N-sita[len(sita)-2][1])
    else:
        if len(sita) == 1:
            print(N-ue[len(ue)-2])
        else:
            print(min(N-ue[len(ue)-2],N-sita[len(sita)-2]))
else:
    print(N-m[1]-n[1])

Fixed submission:
import collections as c
N = int(input())
a = list(map(int,input().split()))
ue = a[0::2]
sita = a[1::2]
dictue = c.defaultdict(int)
dictsita = c.defaultdict(int)
for i in ue:
    dictue[i] += 1
for i in sita:
    dictsita[i] += 1
ue = list(dictue.items())
ue.sort(key=lambda x:x[1])
sita = list(dictsita.items())
sita.sort(key=lambda x:x[1])
m = ue[len(ue)-1]
n = sita[len(sita)-1]
if m[0] == n[0]:
    if len(ue) == 1:
        if len(sita) == 1:
            print(N//2)
        else:
            print(N-m[1]-sita[len(sita)-2][1])
    else:
        if len(sita) == 1:
            print(N-n[1]-ue[len(ue)-2][1])
        else:
            print(min(N-n[1]-ue[len(ue)-2][1],N-m[1]-sita[len(sita)-2][1]))
else:
    print(N-m[1]-n[1])
Buggy python submission (verdict: Time Limit Exceeded):
h,w = map(int,input().split())
a = []
for i in range(h):
    a.append(list(map(int,input().split())))
chk = []
for i in range(h):
    if i % 2 == 0:
        tmp = [(i,j) for j in range(w)]
    else:
        tmp = [(i,w-j-1) for j in range(w)]
    chk += tmp
log = []
while len(chk) != 1:
    c = chk.pop(0)
    if a[c[0]][c[1]] % 2 == 1:
        a[chk[0][0]][chk[0][1]] += 1
        log.append([c[0]+1,c[1]+1,chk[0][0]+1,chk[0][1]+1])
print(len(log))
for l in log:
    print(" ".join(map(str,l)))

Fixed submission:
h,w = map(int,input().split())
a = []
for i in range(h):
    a.append(list(map(int,input().split())))
chk = []
for i in range(h):
    if i % 2 == 0:
        tmp = [(i,j) for j in range(w)]
    else:
        tmp = [(i,w-j-1) for j in range(w)]
    chk += tmp
log = []
for i in range(len(chk)-1):
    c = chk[i]
    nc = chk[i+1]
    if a[c[0]][c[1]] % 2 == 1:
        a[c[0]][c[1]] -= 1
        a[nc[0]][nc[1]] += 1
        log.append(" ".join(map(str,[c[0]+1,c[1]+1,nc[0]+1,nc[1]+1])))
print(len(log))
for l in log:
    print(l)
Buggy python submission (verdict: Time Limit Exceeded):
N,k = map(int,input().split())
a = list(map(int,input().split()))
i = 0
while i < N:
    if a[i] >= 0:
        break
    i += 1
x = []
y = []
for j in range(i-k,i+1):
    if j>=0 and j+k-1<N:
        x = a[j:j+k]
        if x[0] < 0 and x[k-1] > 0:
            y.append(min(-x[0],x[k-1])*2 + max(-x[0],x[k-1]))
        else:
            y.append(max(-x[0],x[k-1]))
print(min(y))

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

if 0 in x:
    K -= 1

cand = []
hasleft = x[0] < 0
hasright = x[N-1] > 0
if K == 0:
    cand = [0]
else:
    for i in range(N-K+1):
        left = x[i]
        right = x[i+K-1]
        if left < 0 and right > 0:
            cand.append(min(abs(left)*2+right, right*2+abs(left)))
        elif right < 0:
            cand.append(abs(left))
        elif left > 0:
            cand.append(right)
print(min(cand))

Buggy python submission (verdict: Time Limit Exceeded):
N,k = map(int,input().split())
a = list(map(int,input().split()))
i = 0
while i < N:
    if a[i] >= 0:
        break
    i += 1
x = []
for j in range(i-k,i+1):
    if j>=0 and j+k-1<N:
        x.append(a[j:j+k])
y = []
for i in range(len(x)):
    if x[i][0] < 0 and x[i][k-1] > 0:
        y.append(min(-x[i][0],x[i][k-1])*2 + max(-x[i][0],x[i][k-1]))
    else:
        y.append(max(-x[i][0],x[i][k-1]))
print(min(y))

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

if 0 in x:
    K -= 1

cand = []
hasleft = x[0] < 0
hasright = x[N-1] > 0
if K == 0:
    cand = [0]
else:
    for i in range(N-K+1):
        left = x[i]
        right = x[i+K-1]
        if left < 0 and right > 0:
            cand.append(min(abs(left)*2+right, right*2+abs(left)))
        elif right < 0:
            cand.append(abs(left))
        elif left > 0:
            cand.append(right)
print(min(cand))
Buggy python submission (verdict: Runtime Error):
class Node:
    def __init__(self,mod):
        self.mod = mod
        self.samemod = 1
        self.right = None
        self.left = None
def sumx(node,s):
    if node.left != None:
        s = sumx(node.left,s)
    s += node.samemod*(node.samemod-1)//2
    if node.right != None:
        s = sumx(node.right,s)
    return s
def add(node,x):
    if node == None:
        return Node(x)
    elif node.mod == x:
        node.samemod += 1
    elif node.mod > x:
        node.left = add(node.left,x)
    else:
        node.right = add(node.right,x)
    return node

n,m = map(int,input().split())
A = list(map(int,input().split()))
B = [0]
tmp = 0
root = None
root = add(root,0)
for i in range(n):
    tmp = B[i]+A[i]
    B.append(tmp)
    root = add(root,tmp%m)
ans = sumx(root,0)
print(ans)

Fixed submission:
import itertools
import collections
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = [0] + list(itertools.accumulate(A))
d = collections.defaultdict(int)
for i in range(N+1):
    d[B[i]%M] += 1
d = list(d.items())
ans = 0
for i in d:
    ans += i[1]*(i[1]-1)//2
print(ans)

Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
A = list(map(int,input().split()))
B = [0]
x = [0]*m
tmp = 0
for i in range(n):
    tmp = B[i]+A[i]
    B.append(tmp)
    x[tmp%m] += 1
print(sum(x))

Fixed submission:
import itertools
import collections
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = [0] + list(itertools.accumulate(A))
d = collections.defaultdict(int)
for i in range(N+1):
    d[B[i]%M] += 1
d = list(d.items())
ans = 0
for i in d:
    ans += i[1]*(i[1]-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
n = int(input())
a = list(map(int,input().split()))
x = 1
for i in range(n-1):
    x *= lcm(a[i],a[i+1])
Sum = 0
for i in range(n):
    Sum += (x-1)%a[i]
print(Sum)

Fixed submission:
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
def lcm(x, y):
    return (x * y) // gcd(x, y)
n = int(input())
a = list(map(int,input().split()))
x = 1
for i in range(n-1):
    x *= lcm(a[i],a[i+1])
Sum = 0
for i in range(n):
    Sum += (x-1)%a[i]
print(Sum)
Buggy python submission (verdict: Runtime Error):
import math
n = int(input())
x = []
for i in range(n):
    a,b,c,d = map(int,input().split())
    x.append((a,b,c,d))

def f(a,b,c,d):
    if a < b:
        print("No")
    elif b > d:
        print("No")
    elif c >= b:
        print("Yes")
    else:
        g = math.gcd(b,d)
        if b-g+(a%g) > c:
            print("No")
        else:
            print("Yes")

for i in range(n):
    a,b,c,d = x[i][0],x[i][1],x[i][2],x[i][3]
    f(a,b,c,d)

Fixed submission:
def gcd(x,y):
    if x < y:
        tmp = y
        y = x
        x = tmp

    while x % y != 0:
        r = x % y
        x = y
        y = r
    return y

n = int(input())
x = []
for i in range(n):
    a,b,c,d = map(int,input().split())
    x.append((a,b,c,d))

def f(a,b,c,d):
    if a < b:
        print("No")
    elif b > d:
        print("No")
    elif c >= b:
        print("Yes")
    else:
        g = gcd(b,d)
        if b-g+(a%g) > c:
            print("No")
        else:
            print("Yes")

for i in range(n):
    a,b,c,d = x[i][0],x[i][1],x[i][2],x[i][3]
    f(a,b,c,d)

Buggy python submission (verdict: Runtime Error):
import math
n = int(input())
for i in range(n):
    a,b,c,d = map(int,input().split())
    if a < b:
        print("No")
    elif b > d:
        print("No")
    elif c >= b:
        print("Yes")
    else:
        g = math.gcd(b,d)
        if b-g+(a%g) > c:
            print("No")
        else:
            print("Yes")

Fixed submission:
def gcd(x,y):
    if x < y:
        tmp = y
        y = x
        x = tmp

    while x % y != 0:
        r = x % y
        x = y
        y = r
    return y

n = int(input())
x = []
for i in range(n):
    a,b,c,d = map(int,input().split())
    x.append((a,b,c,d))

def f(a,b,c,d):
    if a < b:
        print("No")
    elif b > d:
        print("No")
    elif c >= b:
        print("Yes")
    else:
        g = gcd(b,d)
        if b-g+(a%g) > c:
            print("No")
        else:
            print("Yes")

for i in range(n):
    a,b,c,d = x[i][0],x[i][1],x[i][2],x[i][3]
    f(a,b,c,d)
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
x,y,z = [],[],[]
for i in range(n):
    line = list(map(int,input().split()))
    x.append(line[0])
    y.append(line[1])
    z.append(line[2])
ls = []
def dfs(sx,sy,sz,i,k):
    if k == 0:
        ls.append(abs(sx)+abs(sy)+abs(sz))
        return abs(sx)+abs(sy)+abs(sz)
    if i == n:
        return 0
    dfs(sx,sy,sz,i+1,k)
    dfs(sx+x[i],sy+y[i],sz+z[i],i+1,k-1)
dfs(0,0,0,0,m)
print(max(ls))

Fixed submission:
n,m = map(int,input().split())
xyz = []
for i in range(n):
    x,y,z = map(int,input().split())
    xyz.append((x,y,z))
k1 = [1,1,1,1,-1,-1,-1,-1]
k2 = [1,1,-1,-1,1,1,-1,-1]
k3 = [1,-1,1,-1,1,-1,1,-1]

sx,sy,sz = 0,0,0
ans_list = []
for i in range(8):
    xyz.sort(key=lambda x: x[0]*k1[i]+x[1]*k2[i]+x[2]*k3[i],reverse=True)
    for j in range(m):
        sx,sy,sz = sx+xyz[j][0],sy+xyz[j][1],sz+xyz[j][2]
    ans_list.append(abs(sx)+abs(sy)+abs(sz))
    sx,sy,sz = 0,0,0
print(max(ans_list))
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
l = len(s)
substrings = [None]*(l*(l+1)//2)
ind = 0
for i in range(1,l+1):
    for j in range(l-i+1):
        substrings[ind] = s[j:j+i]
        ind += 1
substrings = sorted(set(substrings))
print(substrings[k-1])

Fixed submission:
s = input()
k = int(input())
l = len(s)
substrings = []
for i in range(1,k+1):
    for j in range(l-i+1):
        substrings.append(s[j:j+i])
substrings = sorted(set(substrings))
print(substrings[k-1])
Buggy python submission (verdict: Runtime Error):
l = input().split()
h,w = int(l[0]),int(l[1])
mapxy = []
for i in range(h):
    mapxy.append(list(input()))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
flag1 = 0
flag2 = 0
for i in range(h):
    for j in range(w):
        if mapxy[i][j] == "#":
            for k in range(4):
                if 0<=i+dx[k]<w and 0<=j+dy[k]<h:
                    if mapxy[i+dx[k]][j+dy[k]] == "#":
                        flag1 = 1
            if flag1 == 0:
                flag2 = 1
                break
            flag1 = 0
    if flag2 == 1:
        print("No")
        break
if flag2 != 1:
    print("Yes")

Fixed submission:
l = input().split()
h,w = int(l[0]),int(l[1])
mapxy = []
for i in range(h):
    mapxy.append(list(input()))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
flag1 = 0
flag2 = 0
for i in range(h):
    for j in range(w):
        if mapxy[i][j] == "#":
            for k in range(4):
                if 0<=i+dy[k]<h and 0<=j+dx[k]<w:
                    if mapxy[i+dy[k]][j+dx[k]] == "#":
                        flag1 = 1
            if flag1 == 0:
                flag2 = 1
                break
            flag1 = 0
    if flag2 == 1:
        print("No")
        break
if flag2 != 1:
    print("Yes")

Buggy python submission (verdict: Runtime Error):
l = input().split()
h,w = int(l[0]),int(l[1])
maze = []
for i in range(h):
    maze.append(list(input()))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#" or maze[i][j] == 1:
            for k in range(4):
                if 0<=i+dx[k]<w and 0<=j+dy[k]<h:
                    if maze[i+dx[k]][j+dy[k]]=="#" or maze[i+dx[k]][j+dy[k]]==1:
                        maze[i+dx[k]][j+dy[k]]=1
flag = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            print("No")
            flag = 1
            break
if flag != 1:
    print("Yes")

Fixed submission:
l = input().split()
h,w = int(l[0]),int(l[1])
mapxy = []
for i in range(h):
    mapxy.append(list(input()))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
flag1 = 0
flag2 = 0
for i in range(h):
    for j in range(w):
        if mapxy[i][j] == "#":
            for k in range(4):
                if 0<=i+dy[k]<h and 0<=j+dx[k]<w:
                    if mapxy[i+dy[k]][j+dx[k]] == "#":
                        flag1 = 1
            if flag1 == 0:
                flag2 = 1
                break
            flag1 = 0
    if flag2 == 1:
        print("No")
        break
if flag2 != 1:
    print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
line = list(map(int,input().split()))
for i in range(n):
    l = line[:]
    l.pop(i)
    l = sorted(l)
    print(l[n//2-1])


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
y = sorted(a)
yl = y[n//2-1]
yr = y[n//2]
for i in range(n):
    print(yr if a[i] < yr else yl)
Buggy python submission (verdict: Time Limit Exceeded):
l = list(map(int,input().split()))
a,b,k = l[0],l[1],l[2]
for i in range(a,b+1):
    if a<=i<=a+k-1 or b-k+1<=i<=b:
        print(i)
        

Fixed submission:
l = list(map(int,input().split()))
a,b,k = l[0],l[1],l[2]
c = []
for i in range(a,min(a+k,b)):
    c.append(i)
for i in range(max(b-k+1,a),b+1):
    if i not in c:
        c.append(i)
for i in c:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
def solve(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return solve(n-1)+solve(n-2)
print(solve(N))

Fixed submission:
N = int(input())
dp = [0]*(N+1)
dp[0] = 2
dp[1] = 1
for i in range(2,N+1):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
D.sort()
def find(a, i):
    l = 0
    r = len(a)-1
    mid = (l+r)//2
    while l <= r:
        if i == a[mid]:
            return mid
        elif i < a[mid]:
            r = mid - 1
        else:
            l = mid + 1
        mid = (l+r)//2
    return -1

for i in range(M):
    j = find(D, T[i])
    if j == -1:
        print("NO")
        exit(0)
    D.pop(j)
print("YES")
    


Fixed submission:
from collections import defaultdict
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
dic = defaultdict(int)
for d in D:
    dic[d] += 1
def find(a, i):
    l = 0
    r = len(a)-1
    mid = (l+r)//2
    while l <= r:
        if i == a[mid]:
            return mid
        elif i < a[mid]:
            r = mid - 1
        else:
            l = mid + 1
        mid = (l+r)//2
    return -1
keys = list(dic.keys())
keys.sort()
for i in range(M):
    j = find(keys, T[i])
    if j == -1 or dic[keys[j]] == 0:
        print("NO")
        exit(0)
    dic[keys[j]] -= 1
print("YES")
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
ahoge = []
hanege = []
for i in range(m):
    ai,bi = map(int,input().split())
    if ai == 1:
        ahoge.append(bi)
    if bi == n:
        hanege.append(ai)
ahoge.sort()
hanege.sort()
def bis(i):
    under = 0
    upper = len(hanege)
    l = (under+upper)//2
    while under <= upper:
        if i == hanege[l]:
            return 1
        elif i < hanege[l]:
            upper = l-1
        elif i > hanege[l]:
            under = l+1
    return 0
flag = 0
for i in ahoge:
    if bis(i) == 1:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")

Fixed submission:
n,m = map(int,input().split())
ahoge = []
hanege = []
for i in range(m):
    ai,bi = map(int,input().split())
    if ai == 1:
        ahoge.append(bi)
    if bi == n:
        hanege.append(ai)
ahoge.sort()
hanege.sort()
def bis(i):
    under = 0
    upper = len(hanege)-1
    while under <= upper:
        l = (under+upper)//2
        if i == hanege[l]:
            return 1
        elif i < hanege[l]:
            upper = l-1
        elif i > hanege[l]:
            under = l+1
    return 0
flag = 0
for i in ahoge:
    if bis(i) == 1:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
ahoge = []
hanege = []
for i in range(m):
    ai,bi = map(int,input().split())
    if ai == 1:
        ahoge.append(bi)
    if bi == n:
        hanege.append(ai)
flag = 0
for i in ahoge:
    if i in hanege:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")

Fixed submission:
n,m = map(int,input().split())
ahoge = []
hanege = []
for i in range(m):
    ai,bi = map(int,input().split())
    if ai == 1:
        ahoge.append(bi)
    if bi == n:
        hanege.append(ai)
ahoge.sort()
hanege.sort()
def bis(i):
    under = 0
    upper = len(hanege)-1
    while under <= upper:
        l = (under+upper)//2
        if i == hanege[l]:
            return 1
        elif i < hanege[l]:
            upper = l-1
        elif i > hanege[l]:
            under = l+1
    return 0
flag = 0
for i in ahoge:
    if bis(i) == 1:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")