Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(100005)
mod=1000000007
# https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2

def dfs(v,a):
    w=b=1
    for u in links[v]:
        if u==a:
            continue
        cw,cb=dfs(u,v)
        w*=cw+cb
        b*=cw
        w%=mod
        b%=mod
    return w,b


n=int(input())
links=[set() for i in range(n)]

for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].add(y)
    links[y].add(x)

print(sum(dfs(0,None))%mod)

Fixed submission:

import sys
sys.setrecursionlimit(100005)
mod=1000000007
# https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2

def dfs(v,a):
    w=b=1
    for u in links[v]:
        if u==a:
            continue
        cw,cb=dfs(u,v)
        w*=cw+cb
        b*=cw
        w%=mod
        b%=mod
    return w,b


n=int(input())
links=[set() for i in range(n)]

for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].add(y)
    links[y].add(x)

print(sum(dfs(0,None))%mod)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100005)
mod=1000000007
# https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2

def dfs(v,a):
    w,b=,1,1
    for u in links[v]:
        if u==a:
            continue
        cw,cb=dfs(u,v)
        w*=cw*cb
        b*=cw
        w%=mod
        b%=mod
    return w,b


n=int(input())
links=[set() for i in range(n)]

for line in sys.stdin.readlines():
    x,y=map(int, input().split())
    x-=1
    y-=1
    links[x].add(y)
    links[y].add(x)

print(sum(dfs(0,None)%mod))


Fixed submission:

import sys
sys.setrecursionlimit(100005)
mod=1000000007
# https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2

def dfs(v,a):
    w=b=1
    for u in links[v]:
        if u==a:
            continue
        cw,cb=dfs(u,v)
        w*=cw+cb
        b*=cw
        w%=mod
        b%=mod
    return w,b


n=int(input())
links=[set() for i in range(n)]

for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].add(y)
    links[y].add(x)

print(sum(dfs(0,None))%mod)
Buggy python submission (verdict: Runtime Error):
#from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_3
from  itertools import accumulate
mod=1000000007
n=int(input())
s=input()
dp=[1]*n
for i in range(n-1):
    if s[i]==">":
        dp.reverese()
        dp=list(accumulate(dp[:-1]))
        dp.reverse()
    else:
        dp=list(accumulate(dp[:-1]))
    for j in range(len(dp)):
        dp[j]%=mod
print(dp[0])

Fixed submission:
#from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_3
from  itertools import accumulate
mod=1000000007
n=int(input())
s=input()
dp=[1]*n
for i in range(n-1):
    if s[i]==">":
        dp.reverse()
        dp=list(accumulate(dp[:-1]))
        dp.reverse()
    else:
        dp=list(accumulate(dp[:-1]))
    for j in range(len(dp)):
        dp[j]%=mod
print(dp[0])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(100000)

def dfs1(v,p):
    val=1
    pre_mul=[1]
    rev_mul=[]
    for c in links[v]:
        if c==p:
            pre_mul.append(val)
            rev_mul.append(1)
            continue
        res=1+dfs1(c,v)
        val*=res
        val%=m
        pre_mul.append(val)
        rev_mul.append(res)
    dp[v]=val
    for i in range(len(rev_mul)-2,-1,-1):
        rev_mul[i]*=rev_mul[i+1]
        rev_mul[i]%=m
    rev_mul.append(1)
    pre_muls[v]=[pre_mul,rev_mul]
    return val

def dfs2(v,p,a):
    dp[v]=dp[v]*a%m
    pmv=pre_muls[v]
    for i,c in enumerate(links[v]):
        if c==p:
            continue
        pmc=pmv[0][i]*pmv[1][i+1]%m
        pmc=pmc*a%m
        dfs2(c,v,pmc+1)


n,m=map(int,input().split())
links=[[] for i in range(n)]
dp=[0 for i in range(n)]
pre_muls=[None for i in range(n)]
for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].append(y)
    links[y].append(x)

dfs1(0,None)
dfs2(0,None,1)
print('\n'.join(map(str,dp)))

Fixed submission:
import sys
sys.setrecursionlimit(100000)

def dfs1(v,p):
    val=1
    pre_mul=[1]
    rev_mul=[]
    for c in links[v]:
        if c==p:
            pre_mul.append(val)
            rev_mul.append(1)
            continue
        res=1+dfs1(c,v)
        val*=res
        val%=m
        pre_mul.append(val)
        rev_mul.append(res)
    dp[v]=val
    for i in range(len(rev_mul)-2,-1,-1):
        rev_mul[i]*=rev_mul[i+1]
        rev_mul[i]%=m
    rev_mul.append(1)
    pre_muls[v]=[pre_mul,rev_mul]
    return val

def dfs2(v,p,a):
    dp[v]=dp[v]*a%m
    pmv=pre_muls[v]
    for i,c in enumerate(links[v]):
        if c==p:
            continue
        pmc=pmv[0][i]*pmv[1][i+1]%m
        pmc=pmc*a%m
        dfs2(c,v,pmc+1)

n,m=map(int,input().split())
links=[[] for _ in range(n)]
dp=[0 for _ in range(n)]
pre_muls=[None for _ in range(n)]
for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].append(y)
    links[y].append(x)
dfs1(0,None)
dfs2(0,None,1)
print('\n'.join(map(str,dp)))
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        if "1" not in bin(t)[3:]:
            ans+=1
print(len(ans))


Fixed submission:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
p=max(a)*2
chk=[pow(2,i) for i in range(1,32) if pow(2,i)<=p]
ans=0
for i in a[::-1]:
    if d[i]>0:
        d[i]-=1
        for j in chk[::-1]:
            if j-i in d and d[j-i]>0:
                d[j-i]-=1
                ans+=1
                break
print(ans)

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
for i in range(n-1):
    for j in range(i+1,n):
        if "1" not in bin(t)[3:]:
            ans+=1
print(len(ans))


Fixed submission:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
p=max(a)*2
chk=[pow(2,i) for i in range(1,32) if pow(2,i)<=p]
ans=0
for i in a[::-1]:
    if d[i]>0:
        d[i]-=1
        for j in chk[::-1]:
            if j-i in d and d[j-i]>0:
                d[j-i]-=1
                ans+=1
                break
print(ans)
Buggy python submission (verdict: Runtime Error):
def f(a,b):
#a=7,5,3  b=0-7
#no=0, 3=1, 5=2, 7=4, all=7
    if a==7 and b>=4: return b
    if a==7 and b<4: return b+4
    if a==5 and b in (2,3,6,7): return b
    if a==5 and b not in (2,3,6,7): return b+2
    if a==3 and b in (1,3,5,7): return b
    if a==3 and b not in (1,3,5,7): return b+1

n=input()

#a,b=map(int, input().split())
#print(f(a,b))
l=[int(i) for i in "0"+n]
dp=[[[0]*9,[0]*9] for _ in "ww"]
dp[0][0][0]=1

chk=(7,5,3)
for i,j in enumerate(l):
    if i==0: continue
    elif i==1:
        if j in chk: dp[i%2][0][f(j,0)]=1
        if j not in chk: dp[i%2][0][0]=1
        if j>7: dp[i%2][1][4]+=1
        if j>5: dp[i%2][1][2]+=1
        if j>3: dp[i%2][1][1]+=1
        dp[i%2][1][0]=1
    else:
        dp[i%2][1][0]=1
        dp[i%2][1][4]+=1
        dp[i%2][1][2]+=1
        dp[i%2][1][1]+=1
        for k in range(8):
            if dp[i%2-1][0][k] and (k==0 or j not in chk): dp[i%2][0][0]=1
            elif dp[i%2-1][0][k] and j in chk: dp[i%2][0][f(j,k)]=1

            if dp[i%2-1][0][k] and k!=0:
                if j>7: dp[i%2][1][f(7,k)]+=1
                if j>5: dp[i%2][1][f(5,k)]+=1
                if j>3: dp[i%2][1][f(3,k)]+=1
            if dp[i%2-1][1][k] and k!=0:
                dp[i%2][1][f(7,k)]+=dp[i%2-1][1][k]
                dp[i%2][1][f(5,k)]+=dp[i%2-1][1][k]
                dp[i%2][1][f(3,k)]+=dp[i%2-1][1][k]
    for k in range(9):
        dp[i%2-1][0][k]=0
        dp[i%2-1][1][k]=0

print(dp[0][0][7]+dp[0][1][7]+dp[1][0][7]+dp[1][1][7]

Fixed submission:
t=["0","3","5","7"]
s=["3","5","7"]
n=int(input())
ans=chk=0
for a in t:
    for b in t:
        for c in t:
            for d in t:
                for e in t:
                    for f in t:
                        for g in s:
                            for h in s:
                                for i in s:
                                    x=str(int(a+b+c+d+e+f+g+h+i))
                                    y=set(list(x))
                                    if ("0" not in y) and (len(y)==3) and (int(x)<=n):
                                        ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
s=input()
t=input()
a,b={},{}
cnt=1

for i in range(len(s)):
    if s[i] not in a and t[i] not in b:
        a[s[i]]=cnt
        b[t[i]]=cnt
        ant+=1
    elif s[i] in a and t[i] in b and (a[s[i]]==b[t[i]]):
        pass
    else
        print("No")
        exit()
print("Yes")

Fixed submission:
s=input()
t=input()
a,b={},{}
cnt=1
for i in s:
    if i not in a:
        a[i]=cnt
        cnt+=1
cnt=1
for i in t:
    if i not in b:
        b[i]=cnt
        cnt+=1

for i in range(len(s)):
    if a[s[i]]!=b[t[i]]:
        print("No")
        exit()
print("Yes")
Buggy python submission (verdict: Runtime Error):
import math

a,b=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
s=abs(x[-1]-b)
d=set()
for i in range(a-1):
    s=min(s,abs(x[i]-b))
    d.add(x[i+1]-x[i])
if a==1:
    print(abs(b-x[0]))
    exit()
ans=s
while d:
    ans=math.gcd(ans,d.pop())
print(ans)


Fixed submission:
import fractions
a,b=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
s=abs(x[-1]-b)
d=set()
for i in range(a-1):
    s=min(s,abs(x[i]-b))
    d.add(x[i+1]-x[i])
if a==1:
    print(abs(b-x[0]))
    exit()
ans=s
while d:
    ans=fractions.gcd(ans,d.pop())
print(ans)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
o=n//k
p=0
if (k%2==0) p=(n+(k//2))//k
print(o**3+p**3)


Fixed submission:
n,k=map(int,input().split())
o=n//k
p=0
if (k%2==0): p=(n+(k//2))//k
print(o**3+p**3)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
x=[int(i) for i in input().split()]
l,r=[],[]
for i in range(n):
    if x[i]<0 and i+1<n: l.append(abs(x[i]-min(x[i+1],0)))
    elif x[i]<0: l.append(-x[i])
    if x[i]>=0 and i>0: r.append(x[i]-max(0,x[i-1]))
    elif x[i]>=0: r.append(x[i])

l=l[::-1]
l=l[:k]
r=r[:k]
ll=len(l)
rr=len(r)

ans=sum(l)*2+sum(r)*2
for i in range(ll):
    if k-1==i: ans=min(ans,sum(l))
    elif i+rr+1>=k: ans=min(ans,sum(l[:i+1])*2+sum(r[:k-i-1]))

for i in range(rr):
    if k-1==i: ans=min(ans,sum(r))
    elif i+ll+1>=k: ans=min(ans,sum(r[:i+1])*2+sum(l[:k-i-1]))
print(ans)


Fixed submission:
n,k=map(int,input().split())
x=[int(i) for i in input().split()]
l,r=[],[]
for i in range(n):
    if x[i]<0 and i+1<n: l.append(abs(x[i]-min(x[i+1],0)))
    elif x[i]<0: l.append(-x[i])
    if x[i]>=0 and i>0: r.append(x[i]-max(0,x[i-1]))
    elif x[i]>=0: r.append(x[i])

l=l[::-1]
l=l[:k]
r=r[:k]

ll=len(l)
rr=len(r)
lx=sum(l)
rx=sum(r)

if ll<k: lx=lx*2+sum(r[:(k-ll)])
if rr<k: rx=rx*2+sum(l[:(k-rr)])
ans=min(lx,rx)
o=[ll,[0,k-ll][ll<k]]
p=[rr,[0,k-rr][rr<k]]


for i in range(1,k):
    if o[1]==0: lx*=2
    if p[1]==0: rx*=2
    if o[1]+1<=rr and o[0]>0:
        lx-=l[o[0]-1]*2
        lx+=r[o[1]]
        o[0]-=1
        o[1]+=1
        ans=min(ans,lx)
    if p[1]+1<=ll and p[0]>0:
        rx-=r[p[0]-1]*2
        rx+=l[p[1]]
        p[0]-=1
        p[1]+=1
        ans=min(ans,rx)
print(ans)
Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
for a,i in enumerate(s):
    if i!="1":
        x=a
        y=i
        break

if x+1<=k: print(y)
else: print(1)

Fixed submission:
s=input()
k=int(input())
x=-1
y=""
for a,i in enumerate(s):
    if i!="1":
        x=a
        y=i
        break

if x!=-1 and x+1<=k: print(y)
else: print(1)

Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
for a,i in enumerate(s):
    if i!="1":
        x=a
        y=i
        break

if x<=k: print(y)
else: print(1)


Fixed submission:
s=input()
k=int(input())
x=-1
y=""
for a,i in enumerate(s):
    if i!="1":
        x=a
        y=i
        break

if x!=-1 and x+1<=k: print(y)
else: print(1)

Buggy python submission (verdict: Runtime Error):
reina@v157-7-237-130:~/magic/kyogi/Atcoder/abc/b101_125/b106$ cat ./c1.py
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
p=5000000000000000
s=input()
n=int(input())

chk=1
ans=f=0
for i in s:
    chk=1
    if i=="1": 
        ans+=1
        continue
    for j in range(p-1):
        chk*=int(i)
        if ans+chk>=p:
            print(i)
            f=1
            break
    ans+=chk
    if f==1: break
if f==0: print(s[-1])

Fixed submission:
s=input()
k=int(input())
x=-1
y=""
for a,i in enumerate(s):
    if i!="1":
        x=a
        y=i
        break

if x!=-1 and x+1<=k: print(y)
else: print(1)

Buggy python submission (verdict: Runtime Error):
reina@v157-7-237-130:~/magic/kyogi/Atcoder/abc/b101_125/b106$ cat ./c1.py
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
p=5000000000000000
s=input()
n=int(input())

chk=1
ans=f=0
for i in s:
    chk=1
    if i=="1": 
        ans+=1
        continue
    for j in range(p-1):
        chk*=int(i)
        if ans+chk>=p:
            print(i)
            f=1
            break
    ans+=chk
    if f==1: break
if f==0: print(s[-1])
reina@v157-7-237-130:~/mag

Fixed submission:
s=input()
k=int(input())
x=-1
y=""
for a,i in enumerate(s):
    if i!="1":
        x=a
        y=i
        break

if x!=-1 and x+1<=k: print(y)
else: print(1)

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
p=5000000000000000
s=input()
n=int(input())

ans=chk=1
for i in s:
    chk=1
    for j in range(2,p):
        chk*=int(i)
        ans+=chk
        if ans>=p:
            print(i)
            exit()

Fixed submission:
s=input()
k=int(input())
x=-1
y=""
for a,i in enumerate(s):
    if i!="1":
        x=a
        y=i
        break

if x!=-1 and x+1<=k: print(y)
else: print(1)
Buggy python submission (verdict: Time Limit Exceeded):
l=[1,-2]

#for i in range(2,100):
for i in range(2,50):
    l.append(l[-1]*-2)
#print(l)
n=int(input())
for i in range(1000000):
    t=(bin(i)[2:])[::-1]
    chk=0
#    print(t)
    for j,k in enumerate(t):
#        print(k)
        if k=='1':
            chk+=l[j]
        if chk==n:
            print(t[::-1])
            exit()


Fixed submission:
n=int(input())
ans=""
while n!=0:
    if n%2!=0:
        n-=1
        ans="1"+ans
    else:
        ans="0"+ans
    n//=-2
print(ans if ans!="" else 0)
Buggy python submission (verdict: Runtime Error):
s=input()
x=len(s)
dp=[[0 for i in range(4)] for j in range(100005)]
for i in range(x,-1,-1):
    for j in range(3,-1,-1):
        if i==x:
            dp[i][j]=[0,1][j==3]
        else:
            dp[i][j]=dp[i+1][j]*([1,3][s[i]=="?"])
            if (j<3 and (s[i]=="?" or s[i]=="ABC"[j])):
                dp[i][j]+=dp[i+1][j+1]
            dp[i][j]%=mod
print(dp[0][0])

Fixed submission:
mod=1000000007

s=input()
x=len(s)
dp=[[0 for i in range(4)] for j in range(100005)]
for i in range(x,-1,-1):
    for j in range(3,-1,-1):
        if i==x:
            dp[i][j]=[0,1][j==3]
        else:
            dp[i][j]=dp[i+1][j]*([1,3][s[i]=="?"])
            if (j<3 and (s[i]=="?" or s[i]=="ABC"[j])):
                dp[i][j]+=dp[i+1][j+1]
            dp[i][j]%=mod
print(dp[0][0])
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
w=[]
if n<99:
    print(w[1])
for i in range(m):
    a,b=map(int,input().split())
    w.append((a,b))
w.sort(reverse=True)
d=[]
for i in range(m):
    a,b=w.pop()
    if i==0:
        d.append([a,b])
    else:
        if d[-1][1]<=a:
            d.append([a,b])
        elif d[-1][1]>b:
            d[-1][1]=b
print(len(d))


Fixed submission:
n,m=map(int,input().split())
w=[]
for i in range(m):
    a,b=map(int,input().split())
    w.append((a,b))
w.sort(reverse=True)
d=[]
for i in range(m):
    a,b=w.pop()
    if i==0:
        d.append([a,b])
    else:
        if d[-1][1]<=a:
            d.append([a,b])
        elif d[-1][1]>b:
            d[-1][1]=b
print(len(d))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
w=[]
if n>99:
    print(w[1])
for i in range(m):
    a,b=map(int,input().split())
    w.append((a,b))
w.sort(reverse=True)
d=[]
for i in range(m):
    a,b=w.pop()
    if i==0:
        d.append([a,b])
    else:
        if d[-1][1]<=a:
            d.append([a,b])
        elif d[-1][1]>b:
            d[-1][1]=b
print(len(d))


Fixed submission:
n,m=map(int,input().split())
w=[]
for i in range(m):
    a,b=map(int,input().split())
    w.append((a,b))
w.sort(reverse=True)
d=[]
for i in range(m):
    a,b=w.pop()
    if i==0:
        d.append([a,b])
    else:
        if d[-1][1]<=a:
            d.append([a,b])
        elif d[-1][1]>b:
            d[-1][1]=b
print(len(d))
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
ans=0
for i in range(1,n):
    ans=max(ans,len(set(s[:i])&set(si[:])))
print(ans)


Fixed submission:
n=int(input())
s=input()
ans=0
for i in range(1,n):
    ans=max(ans,len(set(s[:i])&set(s[i:])))
print(ans)
Buggy python submission (verdict: Runtime Error):
def sol():
    n=int(input())
    a=[int(i) for i in input().split()]
    ans=n
    p=0
    q=1
    while p<n-1:
        w=x=a[p]
        chk=0
        p+=1
        while p<n:
            w+=a[q]
            x^=a[q]
            q+=1
            if w!=x: break
            chk+=1
        p=q
        ans+=chk*(chk+1)//2
    print(ans)

if __name__=="__main__":
    sol()

Fixed submission:
def sol():
    n=int(input())+1
    a=[int(i) for i in input().split()]+[2**21-1]
    ans=0
    i=j=w=x=0
    while i<n-1:
        while j<n and w==x:
            w+=a[j]
            x^=a[j]
            j+=1
        ans+=(j-i-1)
        w-=a[i]
        x^=a[i]
        i+=1
    print(ans)

if __name__=="__main__":
    sol()

Buggy python submission (verdict: Time Limit Exceeded):
def sol():
    n=int(input())
    a=[int(i) for i in input().split()]
    ans=n
    for i in range(n-1):
        w=x=a[i]
        for j in range(i+1,n):
            w+=a[j]
            x^=a[j]
            if w!=x: break
            ans+=1
    print(ans)

if __name__=="__main__":
    sol()

Fixed submission:
def sol():
    n=int(input())+1
    a=[int(i) for i in input().split()]+[2**21-1]
    ans=0
    i=j=w=x=0
    while i<n-1:
        while j<n and w==x:
            w+=a[j]
            x^=a[j]
            j+=1
        ans+=(j-i-1)
        w-=a[i]
        x^=a[i]
        i+=1
    print(ans)

if __name__=="__main__":
    sol()

Buggy python submission (verdict: Time Limit Exceeded):
def sol():
    n=int(input())
    a=[int(i) for i in input().split()]
    ans=n
    for i in range(n-1):
        w=x=a[i]
        for j in range(i+1,n):
            w+=a[j]
            x^=a[j]
            if w!=x: break
            ans+=1
    print(ans)

if __name__=="__main__":
    sol()

Fixed submission:
def sol():
    n=int(input())+1
    a=[int(i) for i in input().split()]+[2**21-1]
    ans=0
    i=j=w=x=0
    while i<n-1:
        while j<n and w==x:
            w+=a[j]
            x^=a[j]
            j+=1
        ans+=(j-i-1)
        w-=a[i]
        x^=a[i]
        i+=1
    print(ans)

if __name__=="__main__":
    sol()

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[int(i) for i in input().split()]
ans=n
for i in range(n-1):
    w=x=a[i]
    for j in range(i+1,n):
        w+=a[j]
        x^=a[j]
        if w!=x: break
        ans+=1
print(ans)

Fixed submission:
def sol():
    n=int(input())+1
    a=[int(i) for i in input().split()]+[2**21-1]
    ans=0
    i=j=w=x=0
    while i<n-1:
        while j<n and w==x:
            w+=a[j]
            x^=a[j]
            j+=1
        ans+=(j-i-1)
        w-=a[i]
        x^=a[i]
        i+=1
    print(ans)

if __name__=="__main__":
    sol()
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
k=int(input())
n=len(s)
d=set()
#d={s[i:j+1] for j in range(i,n) for i in range(n)}
#d={s[i:j+1] for i in range(n) for j in range(i,n)}
for i in range(n):
    for j in range(i,max(n,i+5)):
        d.add(s[i:j+1])
ans=sorted(list(d))
print(ans[k-1])


Fixed submission:
s=input()
k=int(input())
n=len(s)
d=set()
#d={s[i:j+1] for j in range(i,n) for i in range(n)}
#d={s[i:j+1] for i in range(n) for j in range(i,n)}
for i in range(n):
    for j in range(i,min(n,i+5)):
        d.add(s[i:j+1])
ans=sorted(list(d))
print(ans[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
k=int(input())
n=len(s)
d=set()
#d={s[i:j+1] for j in range(i,n) for i in range(n)}
d={s[i:j+1] for i in range(n) for j in range(i,n)}
#for i in range(n):
#    for j in range(i,n):
#        d.add(s[i:j+1])
ans=sorted(list(d))
print(ans[k-1])


Fixed submission:
s=input()
k=int(input())
n=len(s)
d=set()
#d={s[i:j+1] for j in range(i,n) for i in range(n)}
#d={s[i:j+1] for i in range(n) for j in range(i,n)}
for i in range(n):
    for j in range(i,min(n,i+5)):
        d.add(s[i:j+1])
ans=sorted(list(d))
print(ans[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
k=int(input())
n=len(s)
d=set()
for i in range(n):
    for j in range(i,n):
        d.add(s[i:j+1])
ans=sorted(list(d))
print(ans[k-1])

Fixed submission:
s=input()
k=int(input())
n=len(s)
d=set()
#d={s[i:j+1] for j in range(i,n) for i in range(n)}
#d={s[i:j+1] for i in range(n) for j in range(i,n)}
for i in range(n):
    for j in range(i,min(n,i+5)):
        d.add(s[i:j+1])
ans=sorted(list(d))
print(ans[k-1])
Buggy python submission (verdict: Runtime Error):
xy=[(1,0),(-1,0),(0,1),(0,-1)]

h,w=map(int,input().split())
l=[]
for i in range(h):
    l.appned(input())
for i in range(h):
    for j in range(w):
        if l[i][j]=="#":
            f=0
            for x,y in xy:
                if 0<=(i+y)<h and 0<=(j+x)<w l[i+y][j+x]=="#": f=1
            if f==0:
                print("No")
                exit()
                

print("Yes")


Fixed submission:
xy=[(1,0),(-1,0),(0,1),(0,-1)]

h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(input())
for i in range(h):
    for j in range(w):
        if l[i][j]=="#":
            f=0
            for x,y in xy:
                if 0<=(i+y)<h and 0<=(j+x)<w and l[i+y][j+x]=="#": f=1
            if f==0:
                print("No")
                exit()
                

print("Yes")
Buggy python submission (verdict: Runtime Error):
d={}
n=int(input())
for i in range(n):
    s=input()
    if s in d: d[s]+=1
    else:      d[s] =1
n=int(input())
    s=input()
    if s in d: d[s]-=1
ans=chk=0
for i in d:
    ans=max(ans,d[i])
print(ans)

Fixed submission:
d={}
n=int(input())
for i in range(n):
    s=input()
    if s in d: d[s]+=1
    else:      d[s] =1
n=int(input())
for i in range(n):
    s=input()
    if s in d: d[s]-=1
ans=chk=0
for i in d:
    ans=max(ans,d[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
  1 #!/usr/bin/env python3
  2 # -*- coding: UTF-8 -*-
  3 n=int(input())
  4 l,r=[],[]
  5 for i in range(n):
  6     x,y=map(int,input().split())
  7     l.append((x,y))
  8 l.sort()
  9 for i in range(n):
 10     x,y=map(int,input().split())
 11     r.append((x,y))
 12 r.sort()
 13 ans=[0]*n
 14 t=-1
 15 for i,j in l:
 16     t+=1
 17     for x,y in r:
 18         if i<x and j<y:
 19             ans[t]+=1
 20         else:
 21             break
 22 chk=0
 23 for i in ans:
 24     if i-chk>0: chk+=1
 25 print(chk)


Fixed submission:
n=int(input())
l,r=[],[]
for i in range(n):
    x,y=map(int,input().split())
    l.append((x,y))
l.sort()
l.sort(key=lambda a: a[1],reverse=True)
for i in range(n):
    x,y=map(int,input().split())
    r.append((x,y))
r.sort()
ans=0
chk=[1]*n
for i in range(n):
    for j in range(n):
        if l[i][0]<r[j][0] and l[i][1]<r[j][1] and chk[j]:
            chk[j]=0
            ans+=1
            break
print(ans)