Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
M=41
B=[[0 for x in range(M-len(bin(A[i])[2:]))]+list([int(x) for x in bin(A[i])[2:]]) for i in range(N)]
C=[[0,0] for i in range(M)]
for i in range(N):
    for j in range(M):
        C[j][B[i][j]]+=1
D=[-1 for i in range(M)]
for j in range(M):
    if C[j][0]<=C[j][1]:
        D[j]=0
    else:
        D[j]=1
E=[2**(M-i-1) for i in range(M)]
tmp=0
for i in range(M):
    if tmp+E[i]*D[i]<=K:
        tmp+=E[i]*D[i]
ans=0
for i in range(N):
    ans+=tmp^A[i]
print(ans)

Fixed submission:
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
M=41
B=[[0 for x in range(M-len(bin(A[i])[2:]))]+list([int(x) for x in bin(A[i])[2:]]) for i in range(N)]
C=[[0,0] for i in range(M)]
for i in range(N):
    for j in range(M):
        C[j][B[i][j]]+=1
D=[-1 for i in range(M)]
for j in range(M):
    if C[j][0]<=C[j][1]:
        D[j]=0
    else:
        D[j]=1
E=[2**(M-i-1) for i in range(M)]
tmp=0
for i in range(M):
    if tmp+E[i]*D[i]<=K:
        tmp+=E[i]*D[i]
ans=0
for i in range(N):
    ans+=tmp^A[i]
print(ans)
Buggy python submission (verdict: Runtime Error):
N,K=map(int,input().split())
sushi=[]
for i in range(N):
    t,d=map(int,input().split())
    sushi.append((t,d))
sushi.sort(key=lambda x:(x[0],-x[1]))
#print(sushi)
X=[sushi[0][1]]
Y=[]
for i in range(1,N):
    if sushi[i-1][0]==sushi[i][0]:
        Y.append(sushi[i][1])
    else:
        X.append(sushi[i][1])
X.sort(reverse=True)
Y.sort(reverse=True)
SX=[0]
SY=[0]
for i in X:
    SX.append(SX[-1]+i)
for i in Y:
    SY.append(SY[-1]+i)
ans=0
#print(X)
#print(Y)
#1<=x<len(X)
#K-len(Y)<=x<=
for x in range(K-len(Y),min(len(SX),K+1)):
    ans=max(SX[x]+SY[K-x]+x*x,ans)
print(ans)

Fixed submission:
N,K=map(int,input().split())
t=[0 for i in range(N)]
d=[0 for i in range(N)]
for i in range(N):
    t[i],d[i]=map(int,input().split())
D=dict()
for i in range(N):
    if not(t[i] in D):
        D[t[i]]=[]
    D[t[i]].append((d[i],i))
E=[0 for i in range(N)]
for key in D:
    D[key].sort(reverse=True)
    E[D[key][0][1]]=1
A=[]
B=[]
for i in range(N):
    if E[i]==1:
        A.append(d[i])
    else:
        B.append(d[i])
A.sort(reverse=True)
B.sort(reverse=True)
X=len(A)
Y=len(B)
S=[0 for i in range(X+1)]
T=[0 for i in range(Y+1)]
for i in range(X):
    S[i+1]=A[i]+S[i]
for i in range(Y):
    T[i+1]=B[i]+T[i]
L=[]
for i in range(1,K+1):
    if i<=X and K-i<=Y:
        L.append(S[i]+T[K-i]+i*i)
print(max(L))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import itertools
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
flag1=1 if N<=30 else 0
flag2=1
flag3=1
for i in range(N):
    w[i],v[i]=map(int,input().split())
    if v[i]>100000:
        flag2=0
    if w[i]>100000:
        flag3=0
if flag1==1:
    A=[];B=[]
    for i in range(N):
        if i%2==0:
            A.append((v[i],w[i]))
        else:
            B.append((v[i],w[i]))
    Al=len(A);Bl=len(B)
    Xtmp=[]
    for seq in itertools.product(range(2),repeat=Al):
        tmp0=0
        tmp1=0
        for i in range(Al):
            if seq[i]==1:
                tmp0+=A[i][0]
                tmp1+=A[i][1]
        Xtmp.append((tmp0,tmp1))
    Xtmp.sort(key=lambda x:x[1])
    X=[]
    Xltmp=len(Xtmp)
    maxtmp=0
    for i,seq in enumerate(Xtmp):
        if maxtmp<=seq[0]:
            X.append(seq)
        maxtmp=max(maxtmp,seq[0])
    #print(X)
    wt=[i[1] for i in X]
    #print(wt)
    ans=0
    for seq in itertools.product(range(2),repeat=Bl):
        tmp0=0
        tmp1=0
        for i in range(Bl):
            if seq[i]==1:
                tmp0+=B[i][0]
                tmp1+=B[i][1]
        if W-tmp1<=0:
            continue
        index=bisect.bisect_right(wt,W-tmp1)-1
        tmp=X[index][0]+tmp0
        ans=max(ans,tmp)
    print(ans)
elif flag2==1:
    V=sum(v)
    INF=10**15
    dp=[[INF for j in range(V+1)] for i in range(N+1)]
    #dp[i][j]:iまで試して価値の合計がjのときの重さの最小値
    dp[0][0]=0
    for i in range(N):
        for j in range(V+1):
            if j-v[i]>=0:
                dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i],INF)
            else:
                dp[i+1][j]=min(dp[i][j],INF)
    b=[]
    for i in range(V+1):
        if dp[N][i]!=INF:
            b.append((dp[N][i],i))
    ans=0
    for (x,y) in b:
        if x<=W:
            ans=max(ans,y)
    print(ans)
elif flag3==1:
    dp=[[0 for i in range(W+1)] for i in range(N+1)]
    for j in range(W+1):
        dp[0][j]=0
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j]=dp[i][j]
            if j-w[i]>=0:
                if dp[i][j]<dp[i][j-w[i]]+v[i]:
                    dp[i+1][j]=dp[i][j-w[i]]+v[i]
    print(dp[N][W])


Fixed submission:
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(W+1)] for i in range(N+1)]
for j in range(W+1):
    dp[0][j]=0
for i in range(N):
    for j in range(W+1):
        dp[i+1][j]=dp[i][j]
        if j-w[i]>=0:
            if dp[i][j]<dp[i][j-w[i]]+v[i]:
                dp[i+1][j]=dp[i][j-w[i]]+v[i]
print(dp[N][W])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import itertools
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
flag1=1 if N<=30 else 0
flag2=1
flag3=1
for i in range(N):
    w[i],v[i]=map(int,input().split())
    if v[i]>100000:
        flag2=0
    if w[i]>100000:
        flag3=0
if flag1==1:
    A=[];B=[]
    for i in range(N):
        if i%2==0:
            A.append((v[i],w[i]))
        else:
            B.append((v[i],w[i]))
    Al=len(A);Bl=len(B)
    Xtmp=[]
    for seq in itertools.product(range(2),repeat=Al):
        tmp0=0
        tmp1=0
        for i in range(Al):
            if seq[i]==1:
                tmp0+=A[i][0]
                tmp1+=A[i][1]
        Xtmp.append((tmp0,tmp1))
    Xtmp.sort(key=lambda x:x[1])
    X=[]
    Xltmp=len(Xtmp)
    maxtmp=0
    for i,seq in enumerate(Xtmp):
        if maxtmp<=seq[0]:
            X.append(seq)
        maxtmp=max(maxtmp,seq[0])
    #print(X)
    wt=[i[1] for i in X]
    #print(wt)
    ans=0
    for seq in itertools.product(range(2),repeat=Bl):
        tmp0=0
        tmp1=0
        for i in range(Bl):
            if seq[i]==1:
                tmp0+=B[i][0]
                tmp1+=B[i][1]
        if W-tmp1<=0:
            continue
        index=bisect.bisect_right(wt,W-tmp1)-1
        tmp=X[index][0]+tmp0
        ans=max(ans,tmp)
    print(ans)
elif flag2==1:
    V=sum(v)
    INF=10**15
    dp=[[INF for j in range(V+1)] for i in range(N+1)]
    #dp[i][j]:iまで試して価値の合計がjのときの重さの最小値
    dp[0][0]=0
    for i in range(N):
        for j in range(V+1):
            if j-v[i]>=0:
                dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i],INF)
            else:
                dp[i+1][j]=min(dp[i][j],INF)
    b=[]
    for i in range(V+1):
        if dp[N][i]!=INF:
            b.append((dp[N][i],i))
    ans=0
    for (x,y) in b:
        if x<=W:
            ans=max(ans,y)
    print(ans)
elif flag3==1:
    dp=[[0 for i in range(W+1)] for i in range(N+1)]
    for j in range(W+1):
        dp[0][j]=0
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j]=dp[i][j]
            if j-w[i]>=0:
                if dp[i][j]<dp[i][j-w[i]]+v[i]:
                    dp[i+1][j]=dp[i][j-w[i]]+v[i]
    print(dp[N][W])


Fixed submission:
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
V=sum(v)
INF=10**15
dp=[[INF for j in range(V+1)] for i in range(N+1)]
#dp[i][j]:iまで試して価値の合計がjのときの重さの最小値
dp[0][0]=0
for i in range(N):
    for j in range(V+1):
        if j-v[i]>=0:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i],INF)
        else:
            dp[i+1][j]=min(dp[i][j],INF)
b=[]
for i in range(V+1):
    if dp[N][i]!=INF:
        b.append((dp[N][i],i))
ans=0
for (x,y) in b:
    if x<=W:
        ans=max(ans,y)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#出典
#http://d.hatena.ne.jp/mzp/20100623/lcs
#ここから完全にコピペしました
import sys
sys.setrecursionlimit(10**7)
def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y

table = { ("","") : "" }

def lcs(xs,ys):
    if (xs,ys) in table:
        return table[(xs,ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1],ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,lcs(xs[:-1],ys),lcs(xs,ys[:-1]))
    table[(xs,ys)] = ret
    return ret
S=input()
T=input()
print(lcs(S,T))


Fixed submission:
S=input()
T=input()
a=[ord(i) for i in S]
b=[ord(i) for i in T]
N=len(a);M=len(b)
X=[[0 for j in range(M+1)] for i in range(N+1)]
Y=[[0 for j in range(M+1)] for i in range(N+1)]
for i in range(N):
    for j in range(M):
        if a[i]==b[j]:
            X[i+1][j+1]=X[i][j]+1
            Y[i+1][j+1]=0
        elif X[i+1][j]<X[i][j+1]:
            X[i+1][j+1]=X[i][j+1]
            Y[i+1][j+1]=+1
        else:
            X[i+1][j+1]=X[i+1][j]
            Y[i+1][j+1]=-1
c=[]
i=N;j=M
while(i>0 and j>0):
    if Y[i][j]>0:
        i-=1
    elif Y[i][j]<0:
        j-=1
    else:
        c.append(a[i-1])
        i-=1
        j-=1
print("".join([chr(i) for i in c[::-1]]))

Buggy python submission (verdict: Runtime Error):
#出典
#http://d.hatena.ne.jp/mzp/20100623/lcs
#ここから完全にコピペしました
def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y

table = { ("","") : "" }

def lcs(xs,ys):
    if (xs,ys) in table:
        return table[(xs,ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1],ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,
                    lcs(xs[:-1],ys),
                    lcs(xs,ys[:-1]))
    table[(xs,ys)] = ret
    return ret
S=input()
T=input()
print(lcs(S,T))


Fixed submission:
S=input()
T=input()
a=[ord(i) for i in S]
b=[ord(i) for i in T]
N=len(a);M=len(b)
X=[[0 for j in range(M+1)] for i in range(N+1)]
Y=[[0 for j in range(M+1)] for i in range(N+1)]
for i in range(N):
    for j in range(M):
        if a[i]==b[j]:
            X[i+1][j+1]=X[i][j]+1
            Y[i+1][j+1]=0
        elif X[i+1][j]<X[i][j+1]:
            X[i+1][j+1]=X[i][j+1]
            Y[i+1][j+1]=+1
        else:
            X[i+1][j+1]=X[i+1][j]
            Y[i+1][j+1]=-1
c=[]
i=N;j=M
while(i>0 and j>0):
    if Y[i][j]>0:
        i-=1
    elif Y[i][j]<0:
        j-=1
    else:
        c.append(a[i-1])
        i-=1
        j-=1
print("".join([chr(i) for i in c[::-1]]))
Buggy python submission (verdict: Time Limit Exceeded):
N,P=map(int,input().split())
if N==1:
    print(P)
elif 2**N>P:
    print(1)
else:
    index=1
    ans=1
    while(index**N<=P):
        if P%(index**N)==0:
            ans=index
        index+=1
    print(ans)


Fixed submission:
N,P=map(int,input().split())
D=dict()
k=2
Q=P
while(True):
    if k*k>P:
        break
    if Q%k==0:
        if k in D:
            D[k]+=1
        else:
            D[k]=1
        Q=Q//k
    else:
        k+=1
if Q in D:
    D[Q]+=1
else:
    D[Q]=1
ans=1
for p in D:
    ans=ans*(p**(D[p]//N))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,P=map(int,input().split())
if N==1:
    print(P)
else:
    index=1
    ans=1
    while(index**N<=P):
        if P%(index**N)==0:
            ans=index
        index+=1
    print(ans)


Fixed submission:
N,P=map(int,input().split())
D=dict()
k=2
Q=P
while(True):
    if k*k>P:
        break
    if Q%k==0:
        if k in D:
            D[k]+=1
        else:
            D[k]=1
        Q=Q//k
    else:
        k+=1
if Q in D:
    D[Q]+=1
else:
    D[Q]=1
ans=1
for p in D:
    ans=ans*(p**(D[p]//N))
print(ans)
Buggy python submission (verdict: Runtime Error):
#include <iostream>
using namespace std;
int main(void){
    int X,Y;
    cin >> X >> Y;
    cout << X+Y/2 << endl;
    return 0;
}


Fixed submission:
X,Y=map(int,input().split())
print(X+Y//2)
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x,y):
    a=max(x,y)
    b=min(x,y)
    if a%b==0:
        return b
    else:
        return gcd(a%b,b)
def lcm(x,y):
    return (x*y)//gcd(x,y)
N,M=map(int,input().split())
S=input()
T=input()
X=lcm(N,M)
U=["" for i in range(X)]
A=X//N
B=X//M
for i in range(N):
    U[i*A]=S[i]
for i in range(M):
    if U[i*B]!="" and U[i*B]!=T[i]:
        print(-1)
        exit()
    else:
        U[i*B]=T[i]
print(X)



Fixed submission:
def gcd(x,y):
    a=max(x,y)
    b=min(x,y)
    if a%b==0:
        return b
    else:
        return gcd(a%b,b)
def lcm(x,y):
    return (x*y)//gcd(x,y)
N,M=map(int,input().split())
S=input()
T=input()
X=lcm(N,M)
Y=gcd(N,M)
A=N//Y
B=M//Y
for i in range(Y):
    if S[i*A]!=T[i*B]:
        print(-1)
        exit()
print(X)
Buggy python submission (verdict: Runtime Error):
def E(i,y):
    if i==1:
        return 5*y
    else:
        return (2*i+1)*y

N,X=map(int,input().split())
x=[int(i) for i in input().split()]
a=[0]
for i in range(N):
    a.append(a[-1]+x[i])
ans=10**50
for k in range(1,N+1):
    tmp=(N+k)*X
    for i in range(N//k):
        tmp+=E(i+1,a[N-i*k]-a[N-i*k-k])
        #print(k,i,tmp)
    if N%k!=0:
        tmp+=E(N//k+1,a[N-(N//k)*k])
    #print(tmp)
    if ans>tmp:
        ans=tmp
print(ans)

Fixed submission:
N=int(input())
A=[int(i) for i in input().split()]
P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]%P
Q=[0 for i in range(N)]
I=[inv(i) for i in range(1,N+2)]
U=[0 for i in range(N+2)]
Fact=[0 for i in range(N+1)]
Fact[0]=1
for i in range(N):
    Fact[i+1]=((i+1)*Fact[i])%P
for i in range(N+1):
    U[i+1]=(U[i]+I[i])%P
for j in range(N):
    Q[j]=(U[j+1]+U[N-j]-1)%P
ans=0
for j in range(N):
    ans+=A[j]*Q[j]
    ans=ans%P
print((ans*Fact[N])%P)
Buggy python submission (verdict: Time Limit Exceeded):
def E(i,y):
    if i==1:
        return 5*y
    else:
        return (2*i+1)*y

N,X=map(int,input().split())
x=[int(i) for i in input().split()]
a=[0]
for i in range(N):
    a.append(a[-1]+x[i])
ans=10**50
for k in range(1,N+1):
    tmp=(N+k)*X
    for i in range(N//k):
        tmp+=E(i+1,a[N-i*k]-a[N-i*k-k])
        #print(k,i,tmp)
    if N%k!=0:
        tmp+=E(N//k+1,a[N-(N//k)*k])
    #print(tmp)
    if ans>tmp:
        ans=tmp
print(ans)


Fixed submission:
def E(i,y):
    if i==1:
        return 5*y
    else:
        return (2*i+1)*y

def ceil(a,b):
    return -((-a)//b)
N,X=map(int,input().split())
x=[int(i) for i in input().split()]
a=[0]
for i in range(N):
    a.append(a[-1]+x[i])
ans=10**50
for k in range(1,N+1):
    tmp=(N+k)*X
    for i in range(N//k):
        tmp+=E(i+1,a[N-i*k]-a[N-i*k-k])
        #print(k,i,tmp)
    if N%k!=0:
        tmp+=E(N//k+1,a[N-(N//k)*k])
    #print(tmp)
    if ans>tmp:
        ans=tmp
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def E(i,y):
    if i==1:
        return 5*y
    else:
        return (2*i+1)*y

def ceil(a,b):
    return -((-a)//b)
N,X=map(int,input().split())
x=[int(i) for i in input().split()]
a=[0]
for i in range(N):
    a.append(a[-1]+x[i])
ans=10**50
for k in range(1,N+1):
    tmp=(N+k)*X
    for i in range(N//k):
        tmp+=E(i+1,a[N-i*k]-a[N-i*k-k])
        #print(k,i,tmp)
    if N%k!=0:
        tmp+=E(N//k+1,a[N-(N//k)*k])
    #print(tmp)
    if ans>tmp:
        ans=tmp
print(ans)

Fixed submission:
def E(i,y):
    if i==1:
        return 5*y
    else:
        return (2*i+1)*y

def ceil(a,b):
    return -((-a)//b)
N,X=map(int,input().split())
x=[int(i) for i in input().split()]
a=[0]
for i in range(N):
    a.append(a[-1]+x[i])
ans=10**50
for k in range(1,N+1):
    tmp=(N+k)*X
    for i in range(N//k):
        tmp+=E(i+1,a[N-i*k]-a[N-i*k-k])
        #print(k,i,tmp)
    if N%k!=0:
        tmp+=E(N//k+1,a[N-(N//k)*k])
    #print(tmp)
    if ans>tmp:
        ans=tmp
print(ans)
Buggy python submission (verdict: Runtime Error):
def g(a,b):x=max([a,b]);y=min([a,b]);return g(y,x%y) if x%y else y
N,X=map(int,input().split());a=[abs(int(i)-X) for i in input().split()];ans=a[0]
for i in range(1,N):ans=g(ans,y[i])
print(ans)

Fixed submission:
def gcd(a,b):
    x=max([a,b])
    y=min([a,b])
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)
N,X=map(int,input().split())
x=[int(i) for i in input().split()]
y=[abs(x[i]-X) for i in range(N)]
if N==1:
    print(y[0])
    exit()
ans=gcd(y[0],y[1])
for i in range(2,N):
    ans=gcd(ans,y[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
import itertools
D,G=map(int,input().split())
p=[0 for i in range(D)]
c=[0 for i in range(D)]
for i in range(D):
    p[i],c[i]=map(int,input().split())

S=list(itertools.product(range(2),repeat=D))
ans=sum(p)
for seq in S:
    score=0
    prove=0
    for i in range(D):
        if seq[i]==1:
            score+=(p[i]*100*(i+1)+c[i])
            prove+=p[i]
    if score>G:
        continue
    j=-1
    for i in range(D):
        if seq[i]==0:
            j=i
    if (p[j]*100*(j+1)+c[j]+score<G):
        continue
    if (p[j]*100*(j+1)+score<G):
        continue
    k=(score-G)//(-(j+1)*100)
    prove+=k
    score+=k*100*(j+1)
    if ans>prove:
        ans=prove
print(ans)


Fixed submission:
import itertools
D,G=map(int,input().split())
p=[0 for i in range(D)]
c=[0 for i in range(D)]
for i in range(D):
    p[i],c[i]=map(int,input().split())

S=list(itertools.product(range(2),repeat=D))
ans=sum(p)
for seq in S:
    score=0
    prove=0
    for i in range(D):
        if seq[i]==1:
            score+=(p[i]*100*(i+1)+c[i])
            prove+=p[i]
    if score>=G:
        if ans>prove:
            ans=prove
        continue
    j=-1
    for i in range(D):
        if seq[i]==0:
            j=i
    for k in range(p[j]):
        prove+=1
        score+=100*(j+1)
        if G<=score:
            break
    if G>score:
        continue
    if ans>prove:
        ans=prove
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1.54)
print(ans)


Fixed submission:
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1.5)
print(ans)


Fixed submission:
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(i) for i in input().split()]
B=[[A[i],-10**15] for i in range(2**N)]
for i in range(N):
    for b in range(2**N):
        if ((1&(b>>i))==1):
            merge=B[b]+B[b^(1<<i)]
            merge.sort(reverse=True)
            B[b]=merge[:2]
ans=-10**15
for i in range(1,2**N):
    ans=max([ans,sum(B[i])])
    print(ans)


Fixed submission:
N=int(input())
A=[int(i) for i in input().split()]
B=[[A[i],-10**15] for i in range(2**N)]
for i in range(N):
    for b in range(2**N):
        if ((1&(b>>i))==1):
            merge=B[b]+B[b^(1<<i)]
            merge.sort(reverse=True)
            B[b]=merge[:2]
ans=-10**15
for i in range(1,2**N):
    ans=max([ans,sum(B[i])])
    print(ans)
Buggy python submission (verdict: Runtime Error):
import itertools
N,M=map(int,input().split())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
z=[0 for i in range(N)]
for i in range(N):
    x[i],y[i],z[i]=map(int,input().split())
w=[[0 for i in range(N)] for i in range(8)]
S=list(itertools.product([-1,1],repeat=3))
def num(inp):
    res=0
    for i in range(3):
        res+=2*i(inp[i]+1)//2
    return res
for sg in S:
    for i in range(N):
        w[num(sg)][i]=x[i]sg[0]+y[i]sg[1]+z[i]*sg[2]
tmp=[0 for i in range(8)]
for sg in S:
    w[num(sg)].sort(reverse=True)
    for i in range(M):
        tmp[num(sg)]+=w[num(sg)][i]
print(max(tmp))

Fixed submission:
import itertools
N,M=map(int,input().split())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
z=[0 for i in range(N)]
for i in range(N):
    x[i],y[i],z[i]=map(int,input().split())
w=[[0 for i in range(N)] for i in range(8)]
S=list(itertools.product([-1,1],repeat=3))
def num(inp):
    res=0
    for i in range(3):
        res+=2**i*(inp[i]+1)//2
    return res
for sg in S:
    for i in range(N):
        w[num(sg)][i]=x[i]*sg[0]+y[i]*sg[1]+z[i]*sg[2]
tmp=[0 for i in range(8)]
for sg in S:
    w[num(sg)].sort(reverse=True)
    for i in range(M):
        tmp[num(sg)]+=w[num(sg)][i]
print(max(tmp))
Buggy python submission (verdict: Time Limit Exceeded):
P=998244353
MAX_N=3*10**5+1
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(MAX_N+1)]
Finv=[0 for i in range(MAX_N+1)]
Fact[0]=1
Finv[0]=1
for i in range(MAX_N):
    Fact[i+1]=(Fact[i]*(i+1))%P
    Finv[i+1]=inv(Fact[i+1])%P
def C(n,k):
    return (Fact[n]*(Finv[k]*Finv[n-k])%P)%P
N,A,B,K=map(int,input().split())
L=[]
for i in range(K//A+1):
    if (K-A*i)%B==0:
        j=(K-A*i)//B
        if 0<=i<=N and 0<=j<=N:
            L.append((i,j))
ans=0
for x,y in L:
    ans+=C(N,x)*C(N,y)
    ans%=P
print(ans)



Fixed submission:
N,A,B,K=map(int,input().split())
P=998244353
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1
Finv[0]=1
for i in range(1,N+1):
    Fact[i]=(i*Fact[i-1])%P
    Finv[i]=(Finv[i-1]*inv(i))%P
def NC(k):
    tmp=(Finv[k]*Finv[N-k])%P
    return (Fact[N]*tmp)%P
ans=0
for s in range(N+1):
    t=(K-s*A)//B
    if s*A+t*B==K and 0<=t<=N:
        ans+=(NC(s)*NC(t))%P
print(ans%P)
Buggy python submission (verdict: Runtime Error):
X=int(input())
L=[]
for i in range(2,32):
  k=2
  while(True):
    if (i**k<=X):
      L.append(i**k)
    else:
      break
    k+=1
print(max(L))


Fixed submission:
X=int(input())
L=[1]
for i in range(2,32):
  k=2
  while(True):
    if (i**k<=X):
      L.append(i**k)
    else:
      break
    k+=1
print(max(L))