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


def warshalFloyd(n):
    G=[list(map(int,input().split())) for _ in range(n)]
    D=copy.deepcopy(G)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                G[i][j]=min(G[i][j],G[i][k]+G[k][j])

    return G if G==D else -1


n=int(input())
Graph=warshalFloyd(n)
if Graph==-1:print(-1);exit()

for k in range(n):
    for i in range(n):
        for j in range(n):
            if Graph[i][j]!=0 and Graph[i][k]!=0 and Graph[k][j]!=0:
                if Graph[i][j]==Graph[i][k]+Graph[k][j]:
                    Graph[i][j]=0

ans=0
for i in range(n):
    ans +=sum(Graph[i])
print(ans//2)

Fixed submission:
import copy


def warshalFloyd(n):
    G=[list(map(int,input().split())) for _ in range(n)]
    D=copy.deepcopy(G)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                G[i][j]=min(G[i][j],G[i][k]+G[k][j])

    return G if G==D else -1


n=int(input())
Graph=warshalFloyd(n)
if Graph==-1:print(-1);exit()

for k in range(n):
    for i in range(n):
        for j in range(n):
            if Graph[i][j]!=0 and Graph[i][k]!=0 and Graph[k][j]!=0:
                if Graph[i][j]==Graph[i][k]+Graph[k][j]:
                    Graph[i][j]=0

ans=0
for i in range(n):
    for j in range(i,n):
        ans +=Graph[i][j]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=input()
m=len(n)

cnt=0
for i in range(m):
    cnt +=n[i+1:].count(n[i])
print(m*(m-1)//2-cnt+1)

Fixed submission:
n=input()
m=len(n)

A={chr(i):0 for i in range(97,97+26)}
B={chr(i):0 for i in range(97,97+26)}

cnt=0
for i in range(m):
    A[n[i]] +=1
for i in range(m):
    B[n[i]] +=1
    cnt +=A[n[i]]-B[n[i]]
print(m*(m-1)//2-cnt+1)
Buggy python submission (verdict: Runtime Error):
from math import gcd
def lcm(x,y):
    return (x*y)//gcd(x,y)
n=int(input())
t=int(input())
for i in range(n-1):
    t=lcm(t,int(input()))
print(t)

Fixed submission:
def gcd(x,y):
    while y!=0:
        x,y=y,x%y
    return x
def lcm(x,y):
    return (x*y)//gcd(x,y)
n=int(input())
t=int(input())
for i in range(n-1):
    t=lcm(t,int(input()))
print(t)
Buggy python submission (verdict: Runtime Error):
from math import gcd


def gcd_list(A):
    num=A[0]
    for i in A:
        num=gcd(num,i)
    return num


n,k=map(int,input().split())
A=list(map(int,input().split()))
print("POSSIBLE" if k%gcd_list(A)==0 and k<=max(A) else "IMPOSSIBLE")

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


def gcd_list(A):
    num=A[0]
    for i in A:
        num=gcd(num,i)
    return num


n,k=map(int,input().split())
A=list(map(int,input().split()))
print("POSSIBLE" if k%gcd_list(A)==0 and k<=max(A) else "IMPOSSIBLE")

Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce


def gcd_list(A):
    return reduce(math.gcd,A)


n,k=map(int,input().split())
A=list(map(int,input().split()))
print("POSSIBLE" if k%gcd_list(A)==0 and k<=max(A) else "IMPOSSIBLE")

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


def gcd_list(A):
    num=A[0]
    for i in A:
        num=gcd(num,i)
    return num


n,k=map(int,input().split())
A=list(map(int,input().split()))
print("POSSIBLE" if k%gcd_list(A)==0 and k<=max(A) else "IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
cnt=1
def plot():
    if cnt>=10**9+7:
        cnt %=10**9+7
    return cnt
if abs(n-m)>1:print(0);exit()
elif (n+m)%2==1:
    for i in range(n):
        cnt *=(i+1)
        plot()
    for j in range(m):
        cnt *=(j+1)
        plot()
    print(cnt)
else:
    cnt *=(n+m)
    n -=1
    for i in range(n):
        cnt *=(i+1)
        plot()
    for j in range(m):
        cnt *=(j+1)
        plot()
    print(cnt)

Fixed submission:
n,m=map(int,input().split())
cnt=1
if abs(n-m)>1:print(0);exit()
elif (n+m)%2==1:
    for i in range(n):
        cnt *=(i+1)
        if cnt>=10**9+7:cnt %=10**9+7
    for j in range(m):
        cnt *=(j+1)
        if cnt >= 10 ** 9 + 7: cnt %= 10 ** 9 + 7
    print(cnt)
else:
    cnt *=(n+m)
    n -=1
    for i in range(n):
        cnt *=(i+1)
        if cnt >= 10 ** 9 + 7: cnt %= 10 ** 9 + 7
    for j in range(m):
        cnt *=(j+1)
        if cnt >= 10 ** 9 + 7: cnt %= 10 ** 9 + 7
    print(cnt)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
n=int(input())
s=[input() for i in range(n)]
count=Counter(s[0])
for i in range(n):
    count &=s[i]

ans=""
for i in sorted(count.keys()):
    ans +=i*count[i]
print(ans)

Fixed submission:
from collections import Counter
n=int(input())
s=[input() for i in range(n)]
count=Counter(s[0])
for i in range(n):
    count &=Counter(s[i])

ans=""
for i in sorted(count.keys()):
    ans +=i*count[i]
print(ans)
Buggy python submission (verdict: Runtime Error):
def DFS(num):
    global ans,color
    color[num]="black"
    if "white" not in color:
        ans +=1
    for i in M[num]:
        DFS(i)
    color[num]="white"


n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

M=[[] for _ in range(n)]
color=["white" for _ in range(n)]
for a,b in AB:
    M[a-1].append(b-1)
    M[b-1].append(a-1)

ans=0
DFS(0)
print(ans)

Fixed submission:
from itertools import permutations
n,m=map(int,input().split())

M=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    M[a-1].append(b-1)
    M[b-1].append(a-1)

ans=0
for A in permutations(range(n),n):
    if A[0]==0:
        for i in range(n):
            if i==n-1:
                ans +=1
                break
            if A[i+1] not in M[A[i]]:break

print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
A=[]
cnt=0
add=0
for i in range(4471):
    cnt +=i+1
    A.append((cnt,i+1))
for i in range(len(A)-1):
    if A[i][0]<=n<=A[i+1][0]:
        add=(A[i+1][1],A[i+1][0]-n)
        break

for i in range(add[0]):
    if i+1==add[1]:
        continue
    print(i+1)

Fixed submission:
n=int(input())
A=[]
cnt=0
add=0
for i in range(4472):
    cnt +=i+1
    A.append((cnt,i+1))
for i in range(len(A)-1):
    if A[i][0]<=n<=A[i+1][0]:
        add=(A[i+1][1],A[i+1][0]-n)
        break

for i in range(add[0]):
    if i+1==add[1]:
        continue
    print(i+1)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()

while 1:
    num=len(s)
    s=s.replace("ST","")
    if num==len(s):break
print(num)

Fixed submission:
from collections import deque
s=list(input())
A=deque([])
for i in s:
    if i=="S":A.append(i)
    elif i=="T":
        if len(A)==0 or A[-1]=="T":A.append(i)
        else:A.pop()
print(len(A))

Buggy python submission (verdict: Runtime Error):
s=list(input())
word,cnt=s[0],0
n=len(s)
S=""
for i in range(n):
    if word!=s[i]:
        S +=word+str(cnt)
        cnt=1
        word=s[i]
    else:
        cnt +=1
S +=word+str(cnt)
S +="G"
S=list(S)
cnt=0
for i in range(0,len(S)-1,2):
    if S[i]+S[i+2]=="ST":
        cnt +=(min(int(S[i+1]),int(S[i+3])))*2
print(n-cnt)

Fixed submission:
from collections import deque
s=list(input())
A=deque([])
for i in s:
    if i=="S":A.append(i)
    elif i=="T":
        if len(A)==0 or A[-1]=="T":A.append(i)
        else:A.pop()
print(len(A))

Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())+["G"]*2
n=0
while s[n+1]!="G":
    if s[n]+s[n+1]=="ST":
        del s[n]
        del s[n]
        if n!=0: n-=1
    else:
        n +=1
print(len(s)-2)

Fixed submission:
from collections import deque
s=list(input())
A=deque([])
for i in s:
    if i=="S":A.append(i)
    elif i=="T":
        if len(A)==0 or A[-1]=="T":A.append(i)
        else:A.pop()
print(len(A))
Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
m=len(s)

word={j:26-i for i,j in enumerate([chr(_) for _ in range(97,97+26)])}
number={i:j for i,j in enumerate(chr(_) for _ in range(97,97+26))}
ans=""

for i,j in enumerate(s):
    if i==m-1 and k>0:
        k %=26
        if k>word[j]:ans +=number[k-word[j]]
        else:ans +=number[26-word[j]+k]
    elif word[j]<=k:
        k -=word[j]
        ans +="a"
    else:ans +=j
    
print(ans)

Fixed submission:
N = 26
ord_a = ord('a')
S = [ord(s) - ord_a for s in input()]
K = int(input())


for i in range(len(S)):
    r = (N - S[i]) % N
    if K >= r:
        K -= r
        S[i] = 0


S[-1] += K % N
S[-1] %= N

answer = ''.join(chr(s + ord_a) for s in S)
print(answer)
Buggy python submission (verdict: Runtime Error):
n,l=map(int,input().split())
A=list(map(int,input().split()))
A=list([i+1,A[i]] for i in range(n))
cnt,cnt_list=0,[]
ans=[]
for x,y in A:
    cnt +=y
    cnt_list.append(x)
    if x==n:cnt_list.pop()
    if cnt>=l:
        ans.append(cnt_list.pop())
        for i in cnt_list:
            ans.append(i)
        cnt=0
        cnt_list=[]

if len(ans)==n-1:
    print("Possible")
    for i in ans:print(i)
else:print("Impossible")

Fixed submission:
n,l=map(int,input().split())
A=list(map(int,input().split()))
add=0
for i in range(1,n):
    if A[i]+A[i-1]>=l:
        add=i+1
        break
if add==0:print("Impossible");exit()
print("Possible")
for i in range(1,add-1):print(i)
for i in [j for j in range(add,n)][::-1]:print(i)
print(add-1)
Buggy python submission (verdict: Runtime Error):
n = int(input())

xl = (map(int, input().split()) for _ in range(n))
w = [(x - l, x + l) for x, l in xl]
w = sorted(w, key=lambda x: x[1])
cur = w[0][1]
res = 1
for l, r in w[1:]:
    if l >= cur:
        res += 1
        cur = r
print(res)


Fixed submission:
MAX = int(1e9)
n, k, s = map(int, input().split())
if s != MAX:
    for _ in range(k):
        print(s, end=" ")
    for _ in range(n - k):
        print(MAX, end=" ")
else:
    for _ in range(k):
        print(s, end=" ")
    for _ in range(n - k):
        print(1, end=" ")
Buggy python submission (verdict: Runtime Error):
import numpy as np

n, m = map(int, input().split())
is_ac = np.zeros(n, dtype=int)
wc_count = np.zeros(n, dtype=int)

for _ in range(m):
    p, s = input().split()
    p = int(p)
    if is_ac[p - 1] == 0:
        if s == "WA":
            wc_count[p - 1] += 1
        else:
            is_ac[p - 1] = 1
print(is_ac.sum(), wc_count[is_ac].sum())


Fixed submission:
import numpy as np

n, m = map(int, input().split())
is_ac = np.zeros(n, dtype=bool)
wc_count = np.zeros(n, dtype=int)

for _ in range(m):
    p, s = input().split()
    p = int(p)
    if not is_ac[p - 1]:
        if s == "WA":
            wc_count[p - 1] += 1
        else:
            is_ac[p - 1] = True
print(is_ac.sum(), wc_count[is_ac].sum())
Buggy python submission (verdict: Runtime Error):
"""
Union-Find Tree / Disjoint Set Union (DSU)
"""


def init_unionfind(N):
    global parent, rank, NUM_VERTEX
    NUM_VERTEX = N
    parent = [-1] * N
    rank = [0] * N


def find_root(x):
    p = parent[x]
    if p == -1:
        return x
    p2 = find_root(p)
    parent[x] = p2
    return p2


def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if x == y:
        return  # already united
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def is_connected(x, y):
    return (find_root(x) == find_root(y))


def num_components():
    return len(set(find_root(x) for x in range(NUM_VERTEX)))

# --- end of library ---


def main_yosupo():
    # verified: https://judge.yosupo.jp/problem/unionfind
    N, Q = [int(x) for x in input().split()]
    init_unionfind(N)
    for q in range(Q):
        typ, u, v = [int(x) for x in input().split()]
        if typ == 0:
            unite(u, v)
        else:
            print(1 if is_connected(u, v) else 0)


def main_abl():
    N, M = map(int, input().split())
    init_unionfind(N)
    for _i in range(M):
        a, b = map(int, input().split()))
        unite(a - 1, b - 1)

    return num_components() - 1


if __name__ == "__main__":
    # main_yosupo()
    main_abl()


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def init_unionfind(N):
    global parent, rank
    parent = [-1] * N
    rank = [0] * N


def find_root(x):
    p = parent[x]
    if p == -1:
        return x
    p2 = find_root(p)
    parent[x] = p2
    return p2


def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if x == y:
        return  # already united
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def is_connected(x, y):
    return (find_root(x) == find_root(y))


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, M, edges):
    init_unionfind(N)
    for e in edges:
        unite(e[0] - 1, e[1] - 1)

    s = set(find_root(x) for x in range(N))

    return len(s) - 1


def main():
    # parse input
    N, M = map(int, input().split())
    edges = []
    for _i in range(M):
        edges.append(tuple(map(int, input().split())))

    print(solve(N, M, edges))


# tests
T1 = """
3 1
1 2
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(S, T):
    buf = []
    for i in range(len(S) - len(T)):
        diff = 0
        for j in range(len(T)):
            if S[i + j] != T[j]:
                diff += 1
        buf.append(diff)
    return min(buf)


def main():
    # parse input
    S = input().strip()
    T = input().strip()
    print(solve(S, T))


# tests
T1 = """
cabacc
abc
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
codeforces
atcoder
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
6
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(S, T):
    buf = []
    for i in range(len(S) - len(T) + 1):
        diff = 0
        for j in range(len(T)):
            if S[i + j] != T[j]:
                diff += 1
        buf.append(diff)
    return min(buf)


def main():
    # parse input
    S = input().strip()
    T = input().strip()
    print(solve(S, T))


# tests
T1 = """
cabacc
abc
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
codeforces
atcoder
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
6
"""

T3 = """
aaa
bbb
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
3
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

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

ok = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if AS[i] % AS[j] == 0:
            break
    else:
        ok.append(i)

print(len(ok))


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

AS.sort(reverse=True)
MAX_AS = AS[0]
table = [0] * (MAX_AS + 1)  # 1..max(AS)

alreadyVisited = {}
for i in range(N):
    x = dx = AS[i]
    if alreadyVisited.get(x, False):
        table[x] = 0
        continue
    alreadyVisited[x] = True

    table[x] = 1
    while True:
        x += dx
        if x > MAX_AS:
            break
        table[x] = 0

print(sum(table))
Buggy python submission (verdict: Runtime Error):
a, b, c = [int(x) for x in input().split()]
d = c - a - b

if d <= 0:
    print("No")
else:
    if 4 * a * b < d * d:
        print("Yes")
    else:
        print("No")

Fixed submission:
A, B = input().split()
A = int(A)
B = int(B.replace(".", ""))
print(A * B // 100)

Buggy python submission (verdict: Runtime Error):
a, b, c = [int(x) for x in input().split()]
d = c - a - b

if d <= 0:
    print("No")
else:
    if 4 * a * b < d * d:
        print("Yes")
    else:
        print("No")

Fixed submission:
A, B = input().split()
A = int(A)
B = int(B.replace(".", ""))
print(A * B // 100)

Buggy python submission (verdict: Runtime Error):
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8');

const [a, b, c] = input.split(" ").map((s) => parseInt(s, 10));

// ya + vb < Vc
// a + 2yab + b < c
// 2/ab < c - a - b
// c - a - b A5 false
// 4ab < (c - a - b)^2

// console.log(Number.MAX_SAFE_INTEGER);
// expected output: 9007199254740991

//const [a, b, c] = [249999999, 250000000, 999999998];

const d = BigInt(c - a - b);
if (d <= 0) {
  console.log("No");
} else {
  console.log((4 * a) * b < d * d ? "Yes" : "No");
}


Fixed submission:
A, B = input().split()
A = int(A)
B = int(B.replace(".", ""))
print(A * B // 100)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
P = 998244353

# N = 10
# S = 10
# AS = list(map(int, "3 1 4 1 5 9 2 6 5 3".split()))
N, S = map(int, input().split())
AS = list(map(int, input().split()))
DP = np.zeros((S + 1, N + 1), dtype=np.int64)
DP[0, 0] = 1
# print(DP)

for i in range(N):
    for j in range(S + 1):
        v = DP[j, i] * 2
        if AS[i] <= j:
            v += DP[j - AS[i], i]
        DP[j, i + 1] = v % P

# print(DP)
print(DP[S, N])


Fixed submission:
import sys
import numpy as np
P = 998244353


def main(N, S, AS):
    DP = np.zeros((S + 1, N + 1), dtype=np.int64)
    DP[0, 0] = 1
    # print(DP)

    for i in range(N):
        for j in range(S + 1):
            v = DP[j, i] * 2
            if AS[i] <= j:
                v += DP[j - AS[i], i]
            DP[j, i + 1] = v % P

    # print(DP)
    print(DP[S, N])


if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'void(i8,i8,i8[:])')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
    exit()
else:
    # read parameter
    N, S = map(int, input().split())
    AS = np.array(list(map(int, input().split())))
    from my_module import main
    main(N, S, AS)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=map(int,input().split())
val = 1
for i in a:
	val*=i
if(val>1000000000000000000):
	print(-1)
else:
	print(val)

Fixed submission:
n=int(input())
a=map(int,input().split())
val = 1
exceed = 0
for i in a:
	if(exceed==0 or i==0):
		val*=i
	if(val==0):
		print(0)
		exit(0)
	if(val>1000000000000000000):
		exceed=1
if(exceed==0):
	print(val)
else:
	print(-1)
Buggy python submission (verdict: Runtime Error):
import math

def lcm (a, b):
    return a // math.gcd (a, b) * b

n, ts = int(input()), []
for i in range (n):
    ts.append (int (input ()))

ans = 1
for i in range (n):
    ans = lcm (ans, ts[i])

print (ans)

Fixed submission:
from fractions import gcd

def lcm (a, b):
    return a // gcd (a, b) * b

n, ts = int (input ()), []
for i in range (n):
    ts.append (int (input ()))

ans = 1
for i in range (n):
    ans = lcm (ans, ts[i])

print (ans)
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.spatial import ConvexHull
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
tmp = set()
dots = []
for _ in range(N):
    x, y = map(int, input().split())
    tmp.add((x, y))
    dots.append([x, y])

# 直線状か判定
isline = True
x1, y1 = dots[0]
x2, y2 = dots[1]
for i in range(2, N):
    x3, y3 = dots[i]
    isline &= (y3 - y1) * (x2 - x1) == (y2 - y1) * (x3 - x1)

if not isline:
    hull = ConvexHull(dots).points + 0.1

    dots = np.array(hull, dtype=np.int64).tolist()
    M = len(dots)

    ans = 0
    for i in range(M-1):
        xi, yi = dots[i]
        for j in range(i + 1, M):
            xj, yj = dots[j]
            ans = max(ans, abs(xi - xj) + abs(yi - yj))
    print(ans)
else:
    dots.sort()
    xi, yi = dots[0]
    xj, yj = dots[-1]
    print(abs(xi - xj) + abs(yi - yj))

Fixed submission:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10**18

N = int(input())
xmax = -inf
xmin = inf
ymax = -inf
ymin = inf
for _ in range(N):
    a, b = map(int, input().split())
    x = a + b
    y = a - b
    xmax = max(xmax, x)
    xmin = min(xmin, x)
    ymax = max(ymax, y)
    ymin = min(ymin, y)

print(max(xmax-xmin, ymax-ymin))
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
a = list(map(int,input().split()))

leq,high = 0,10**19
while high-leq > 1:
  l = (leq+high)//2
  cnt = 0
  for ai in a:
    cnt += int((ai-1)/l)
  if cnt>k:
    leq = l
  else:
    high = l

print(high)


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

# 合計N+Kこになる


l = 0
r = 2 * 10 ** 9 + 10 ** 6
while r - l > 1:
    m = (r + l) // 2
    cnt = 0
    for a in A:
        cnt += (a + m - 1) // m
    if cnt <= N + K:
        r = m
    else:
        l = m

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

if K == 1:
    for a, b in zip(A[:-1], A[1:]):
        if a < b:
            print("Yes")
        else:
            print("No")
else:
    score = 1
    for i in range(K):
        score *= A[i]
    for i in range(K, N):
        tmp = score // A[i - K] * A[i]
        if tmp > score:
            print("Yes")
        else:
            print("No")
        score = tmp

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

if K == 1:
    for a, b in zip(A[:-1], A[1:]):
        if a < b:
            print("Yes")
        else:
            print("No")
else:
    for i in range(K, N):
        if A[i] > A[i-K]:
            print("Yes")
        else:
            print("No")