Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=[int(i) for i in input().split()]
ans=0
a.sort()
a.reverse()
if n%2==0:
    p=n//2
else:
    p=n//2+1
c=1
lp=[]
lm=[]
for i in a:
    if i>0 and c<=p:
        ans+=i
        lp.append(i)
    else:
        ans-=i
        lm.append(i)
    c+=1
print(ans)
llp=len(lp)
llm=len(lm)
q=lm[0]
i=0
j=0
k=0
o=0

for i in range(llp-1):
    print(q,lp[i])
    q=q-lp[i]
print(lp[-1],q)
q=lp[-1]-q
for i in range(1,llm):
    print(q,lm[i])
    q=q-lm[i]

Fixed submission:
n=int(input())
a=[int(j) for j in input().split()]
a.sort()
ans=[]
p=a[0]
q=a[-1]
for i in a[1:-1]:
    if i<0:
        ans.append([q,i])
        q-=i
    else:
        ans.append([p,i])
        p-=i
ans.append([q,p])
print(q-p)
for i,j in ans:
    print(i,j)

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=[int(i) for i in input().split()]
ans=0
a.sort()
a.reverse()
if n%2==0:
    p=n//2
else:
    p=n//2+1
c=1
lp=[]
lm=[]
for i in a:
    if i>0 and c<=p:
        ans+=i
        lp.append(i)
    else:
        ans-=i
        lm.append(i)
    c+=1
print(ans)
llp=len(lp)
llm=len(lm)
q=[]
i=0
j=0
k=0
o=0
while o==0:
    if llp>llm:
        if lp!=[] and lm!=[]:
            lm.append(-lp[0]+lm[0])
            print(lm[0],lp[0])
            del lp[0]
            del lm[0]
        elif lm!=[]:
            print(lm[0],lm[-1])
            del lm[0]
            del lm[-1]
        else:
            o=1
    else:
        if lp!=[] and lm!=[]:
            lp.append(lp[0]-lm[0])
            print(lp[0],lm[0])
            del lp[0]
            del lm[0]
        elif lp!=[]:
            print(lp[0],lp[-1])
            del lp[0]
            del lp[-1]
        else:
            o=1
            
            
        
        
        
    
        





 

Fixed submission:
n=int(input())
a=[int(j) for j in input().split()]
a.sort()
ans=[]
p=a[0]
q=a[-1]
for i in a[1:-1]:
    if i<0:
        ans.append([q,i])
        q-=i
    else:
        ans.append([p,i])
        p-=i
ans.append([q,p])
print(q-p)
for i,j in ans:
    print(i,j)
Buggy python submission (verdict: Time Limit Exceeded):
l=input()
n=len(l)
s=list(l)
i=0
ans=0
while i<n-2:
    if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
        s[i]="B"
        s[i+1]="C"
        s[i+2]="A"
        i=max(0,i-1)
        ans+=1
    else:
        i+=1

print(ans)

Fixed submission:
l=input()
n=len(l)
s=list(l)
i=0
ans=0
p=0
while i<n-2:
    if s[i]=="A":
        p+=1
    else:
        p=0
    if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
        ans+=p
        i+=2
        s[i]="A"
        p-=1
    else:
        i+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
l=input()
n=len(l)
s=list(l)
i=0
ans=0
while i<n-2:
    if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
        s[i]="B"
        s[i+1]="C"
        s[i+2]="A"
        i=max(0,i-1)
        ans+=1
    else:
        i+=1

print(ans)

Fixed submission:
l=input()
n=len(l)
s=list(l)
i=0
ans=0
p=0
while i<n-2:
    if s[i]=="A":
        p+=1
    else:
        p=0
    if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
        ans+=p
        i+=2
        s[i]="A"
        p-=1
    else:
        i+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
v=[int(i) for i in input().split()]
ans=[]

for i in range(min(n,k)+1):
    for j in range(min(n,k)-i+1):
        d=k-i-j
        l=v[0:i]
        r=v[n-j:n]
        p=r+l
        q=[]
        s=sum(p)
        for x in p:
            if x<0:
                q.append(x)
        q.sort()
        for x in range(d):
            s-=q[x]
        ans.append(s)
        
print(max(ans))






Fixed submission:
n,k=map(int,input().split())
v=[int(i) for i in input().split()]
ans=[]

for i in range(min(n,k)+1):
    for j in range(min(n,k)-i+1):
        d=k-i-j
        l=v[0:i]
        r=v[n-j:n]
        p=r+l
        q=[]
        s=sum(p)
        for x in p:
            if x<0:
                q.append(x)
        q.sort()
        for x in range(min(len(q),d)):
            s-=q[x]
        ans.append(s)
        
print(max(ans))
Buggy python submission (verdict: Time Limit Exceeded):
r,g,b,n=map(int,input().split())
ans=0
for i in range(n+1):
    for j in range(n+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            ans+=1
print(ans)

Fixed submission:
r,g,b,n=map(int,input().split())
ans=0
for i in range(n+1):
    for j in range(n+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            ans+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[int(i) for i in input().split()]
a.sort()

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

l=make_divisors(a[0])
l2=make_divisors(a[1])
le=len(l)
le2=len(l2)         
an=[0]*le
an2=[0]*le2
for i in range(n):
    for j in range(le):
        if a[i]%l[j]==0:
            an[j]+=1
    for j in range(le2):
        if a[i]%l2[j]==0:
            an2[j]+=1
ans=1
ans2=1
for i in range(le):
    if an[i]>=n-1:
        ans=max(ans,l[i])
for i in range(le2):
    if an2[i]>=n-1:
        ans2=max(ans2,l2[i])

print(max(ans,ans2))




Fixed submission:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

l=make_divisors(a[0])
l2=make_divisors(a[1])
le=len(l)
le2=len(l2)         
an=[0]*le
an2=[0]*le2
for i in range(n):
    for j in range(le):
        if a[i]%l[j]==0:
            an[j]+=1
    for j in range(le2):
        if a[i]%l2[j]==0:
            an2[j]+=1
ans=1
ans2=1
for i in range(le):
    if an[i]>=n-1:
        ans=max(ans,l[i])
for i in range(le2):
    if an2[i]>=n-1:
        ans2=max(ans2,l2[i])

print(max(ans,ans2))
Buggy python submission (verdict: Time Limit Exceeded):
x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]


ab=[]

for i in a:
    for j in b:
        ab.append(i+j)
ab.sort()
ab.reverse()
ans=[]
for i in range(min(k,len(ab))):
    for j in c:
        ans.append(ab[i]+j)
ans.sort()
ans.reverse()

for i in range(k):
    print(ans[i])



Fixed submission:
x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]


ab=[]

for i in a:
    for j in b:
        ab.append(i+j)
ab.sort()
ab.reverse()
ans=[]
for i in range(min(k,len(ab))):
    for j in c:
        ans.append(ab[i]+j)
ans.sort()
ans.reverse()

for i in range(k):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
if a==b:
    print(a)
    import sys
    sys.exit()

def f(a):
    l=""
    a+=1
    i=1
    while i<a:
        if a%(i*2)>i:
            if a%(i*2)%2==0:
                l="0"+l
            else:
                l="1"+l
        else:
            l="0"+l
        i*=2
    return l

a=int(f(a-1),2)
b=int(f(b),2)
print(a^b+1)


Fixed submission:
a,b=map(int,input().split())

def f(n):
    p=0
    if n%2==1:
        p=(n+1)//2
        if p%2==0:
            return 0
        else:
            return 1
    else:
        p=n//2
        if p%2==0:
            return n^0
        else:
            return n^1

print(f(a-1)^f(b))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
cost=[2,2,5,5,4,5,6,3,7,6]

dp=["" for i in range(n+1)]

for i in range(1,n+1):
    p=0
    for j in a:
        if i-cost[j]>=0 and dp[i-cost[j]]!="0":
            p=max(p,int(dp[i-cost[j]]+str(j)))
    dp[i]=str(p)

print(dp[n])

Fixed submission:
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
cost=[2,2,5,5,4,5,6,3,7,6]

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

for i in range(1,n+1):
    p=0
    for j in a:
        if i-cost[j]>=0 and (dp[i-cost[j]]!=0 or i-cost[j]==0):
            p=max(p,int(dp[i-cost[j]]*10+j))
    dp[i]=p

print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
cost=[2,2,5,5,4,5,6,3,7,6]

dp=["" for i in range(n+1)]

for i in range(1,n+1):
    p=0
    for j in a:
        if i-cost[j]>=0 and dp[i-cost[j]]!="0":
            p=max(p,int(dp[i-cost[j]]+str(j)))
    dp[i]=str(p)

print(dp[n])

Fixed submission:
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
cost=[2,2,5,5,4,5,6,3,7,6]

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

for i in range(1,n+1):
    p=0
    for j in a:
        if i-cost[j]>=0 and (dp[i-cost[j]]!=0 or i-cost[j]==0):
            p=max(p,int(dp[i-cost[j]]*10+j))
    dp[i]=p

print(dp[n])

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=[int(i) for i in input().split()]

c=[0,2,5,5,4,5,6,3,7,6]

dp=["" for i in range(n+10)]
for i in a:
    dp[c[i]]=str(i)

for i in range(n):
    for j in a:
        if dp[i]!="":
            dp[i+c[j]]=str(max(int(float(dp[i]+str(j))),int(float("0"+dp[i+c[j]]))))

print(int(dp[n]))







Fixed submission:
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
cost=[2,2,5,5,4,5,6,3,7,6]

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

for i in range(1,n+1):
    p=0
    for j in a:
        if i-cost[j]>=0 and (dp[i-cost[j]]!=0 or i-cost[j]==0):
            p=max(p,int(dp[i-cost[j]]*10+j))
    dp[i]=p

print(dp[n])
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
x=[int(i) for i in input().split()]
x.sort()

if n>=m:
    print(0)
    import sys
    sys.quit()
l=[]
ans=x[-1]-x[0]
for i in range(m-1):
    l.append(abs(x[i]-x[i+1]))
l.sort()
l.reverse()
for i in range(n-1):
    ans-=l[i]
if ans>=0:
    print(ans)
else:
    print(0)

Fixed submission:
n,m=map(int,input().split())
x=[int(i) for i in input().split()]
x.sort()

if n>=m:
    print(0)
    import sys
    sys.exit()
l=[]
ans=x[-1]-x[0]
for i in range(m-1):
    l.append(abs(x[i]-x[i+1]))
l.sort()
l.reverse()
for i in range(n-1):
    ans-=l[i]
if ans>=0:
    print(ans)
else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
h=[int(i) for i in input().split()]

l=[0]+[100000000000000000000000000000 for i in range(n-1)]

for i in range(n-1):
    if i<n-k:
        for j in range(k):
            l[i+j+1]=min(l[i+j+1],abs(h[i]-h[i+j+1])+l[i])
    else:
        for j in range(n-i-1):
            l[i+j+1]=min(l[i+j+1],abs(h[i]-h[i+j+1])+l[i])

print(l[-1])
        




Fixed submission:
n,k=map(int,input().split())
h=[int(i) for i in input().split()]

l=[0]+[100000000000000000000000000000 for i in range(n-1)]

for i in range(n-1):
    if i<n-k:
        for j in range(k):
            l[i+j+1]=min(l[i+j+1],abs(h[i]-h[i+j+1])+l[i])
    else:
        for j in range(n-i-1):
            l[i+j+1]=min(l[i+j+1],abs(h[i]-h[i+j+1])+l[i])

print(l[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,W=map(int,input().split())
w=[]
v=[]

dp=[[-1 for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    a=[int(j) for j in input().split()]
    w.append(a[0])
    v.append(a[1])

def dfs(i,j):
    if dp[i][j]!=-1:
        return dp[i][j]
    if i==n:
        dp[i][j]=0
        return 0
    elif j<w[i]:
        dp[i][j]=dfs(i+1,j)
        return dfs(i+1,j)
    else:
        dp[i][j]=max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])
        return max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])

print(dfs(0,W))



Fixed submission:
n,w=map(int,input().split())
wv=[]
dp=[[0 for i in range(100010)]for j in range(110)]
for i in range(n):
    a=[int(j) for j in input().split()]
    wv.append(a)

from operator import itemgetter
wv.sort(key=itemgetter(0))

for i in range(n):
    for j in range(w+1):
        if j>=wv[i][0]:
            dp[i+1][j]=max(dp[i][j],dp[i][j-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][j]=dp[i][j]


print(dp[n][w])

Buggy python submission (verdict: Time Limit Exceeded):
n,W=map(int,input().split())
w=[]
v=[]

for i in range(n):
    a=[int(j) for j in input().split()]
    w.append(a[0])
    v.append(a[1])

def dfs(i,j):
    if i==n:
        return 0
    elif j<w[i]:
        return dfs(i+1,j)
    else:
        return max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])

print(dfs(0,W))



Fixed submission:
n,w=map(int,input().split())
wv=[]
dp=[[0 for i in range(100010)]for j in range(110)]
for i in range(n):
    a=[int(j) for j in input().split()]
    wv.append(a)

from operator import itemgetter
wv.sort(key=itemgetter(0))

for i in range(n):
    for j in range(w+1):
        if j>=wv[i][0]:
            dp[i+1][j]=max(dp[i][j],dp[i][j-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][j]=dp[i][j]


print(dp[n][w])

Buggy python submission (verdict: Time Limit Exceeded):
n,W=map(int,input().split())
w=[]
v=[]

for i in range(n):
    a=[int(j) for j in input().split()]
    w.append(a[0])
    v.append(a[1])

def dfs(i,j):
    if i==n:
        return 0
    elif j<w[i]:
        return dfs(i+1,j)
    else:
        return max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])

print(dfs(0,W))



Fixed submission:
n,w=map(int,input().split())
wv=[]
dp=[[0 for i in range(100010)]for j in range(110)]
for i in range(n):
    a=[int(j) for j in input().split()]
    wv.append(a)

from operator import itemgetter
wv.sort(key=itemgetter(0))

for i in range(n):
    for j in range(w+1):
        if j>=wv[i][0]:
            dp[i+1][j]=max(dp[i][j],dp[i][j-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][j]=dp[i][j]


print(dp[n][w])
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
t=input()
n,m=len(s),len(t)
dp=[[0]*(m+1) for i in range(n+1)]
dp[0][0]=1

for i in range(n+1):
    for j in range(m+1):
        dp[i][j]=max(dp[i][j-1],dp[i-1][j])
        if i*j!=0 and s[i-1]==t[j-1]:
            dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j])

ans=""
i,j=n,m
while 0<i and 0<j:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans+=s[i-1]
        i-=1
        j-=1

print(ans[::-1])





Fixed submission:
s=input()
t=input()

dp=[[0 for j in range(len(t)+1)] for i in range(len(s)+1)]

for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i][j-1],dp[i-1][j])
            
i=len(s)
j=len(t)
ans=""

while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=s[i-1]+ans
        i-=1
        j-=1
        
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=[float(i) for i in input().split()]
dp=[[0 for j in range(n+1)] for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        dp[i][j]=dp[i-1][j-1]*p[i-1]+dp[i-1][j]*(1-p[i-1])
ans=0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)


Fixed submission:
n=int(input())
p=[float(i) for i in input().split()]
dp=[[0 for j in range(n+1)] for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        dp[i][j]=dp[i-1][j-1]*p[i-1]+dp[i-1][j]*(1-p[i-1])
ans=0
for i in range(n//2+1,n+1):
    ans+=dp[n][i]
print(ans)
Buggy python submission (verdict: Runtime Error):
import subprocess as sp
import sys
code = r"""
n=int(input())
a=[int(j) for j in input().split()]
dp=[[0]*(n+1) for i in range(n+1)]

for i in range(n)[::-1]:
    for j in range(i,n):
        if (n+i-j-1)%2==0:
            dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j])
        else:
            dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j])
print(dp[0][n-1])

"""
with open("A.py","w") as f:
	f.write(code)
sp.Popen(['pypy','-std=pypy','-O2',"A.py"]).communicate()
sp.Popen(['./a.out'],stdin=sys.stdin,stdout=sys.stdout).communicate()


Fixed submission:
n=int(input())
a=[int(j) for j in input().split()]
dp=[[0]*(n+1) for i in range(n+1)]

for i in range(n)[::-1]:
    for j in range(i,n):
        if (n+i-j-1)%2==0:
            dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j])
        else:
            dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j])
print(dp[0][n-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n=int(input())
a=[int(j) for j in input().split()]
dp=[[0]*(n+1) for i in range(n+1)]

for i in range(n)[::-1]:
    for j in range(i,n):
        if (n+i-j-1)%2==0:
            dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j])
        else:
            dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j])
print(dp[0][n-1])



Fixed submission:
n=int(input())
a=[int(j) for j in input().split()]
dp=[[0]*(n+1) for i in range(n+1)]

for i in range(n)[::-1]:
    for j in range(i,n):
        if (n+i-j-1)%2==0:
            dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j])
        else:
            dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j])
print(dp[0][n-1])
Buggy python submission (verdict: Runtime Error):
from subprocess import*
with open('Main.cpp','w')as f:f.write(r"""
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int add(int x,int y){return(x+=y)<mod?x:x-mod;}
int sub(int x,int y){return(x-=y)>= 0?x:x+mod;}
int dp[1<<21];
int n,a[21][21];
int main(){
  scanf("%d",&n);
  for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      scanf("%d",&a[i][j]);
    }
  }
  dp[0]=1;
  for(int b=1;b<(1<<n);++b){
    int bc=__builtin_popcount(b)-1;
    for(int i=0;i<n;++i){
      if((b>>i&1)&&a[bc][i]){
        dp[b]=add(dp[b],dp[b^(1<<i)]);
      }
    }
  }
  printf("%d\n",dp[(1<<n)-1]);
}
""")
call(('g++','Main.cpp'))
call(('./a'))


Fixed submission:
import subprocess as sp
import sys
 
code = r"""
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int add(int x,int y){return(x+=y)<mod?x:x-mod;}
int sub(int x,int y){return(x-=y)>= 0?x:x+mod;}
int dp[1<<21];
int n,a[21][21];
int main(){
  scanf("%d",&n);
  for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      scanf("%d",&a[i][j]);
    }
  }
  dp[0]=1;
  for(int b=1;b<(1<<n);++b){
    int bc=__builtin_popcount(b)-1;
    for(int i=0;i<n;++i){
      if((b>>i&1)&&a[bc][i]){
        dp[b]=add(dp[b],dp[b^(1<<i)]);
      }
    }
  }
  printf("%d\n",dp[(1<<n)-1]);
}
"""
 
with open("A.cpp","w") as f:
	f.write(code)
    
sp.Popen(['g++','-std=c++11','-O2',"A.cpp"]).communicate()
sp.Popen(['./a.out'],stdin=sys.stdin,stdout=sys.stdout).communicate()
Buggy python submission (verdict: Runtime Error):
n=int(input())
mod=10**9+7
l=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    l[a].append(b)
    l[b].append(a)
def dp(x,par):
    res_w,res_t=1,1
    for y in l[x]:
        if y==par:
            continue
        w,t=dp(y,x)
        res_w=(res_w*w)%mod
        res_t=(res_t*t)%mod
    w,t=res_t,(res_t+res_w)%mod
    return w,t
print(dp(1,0)[1])

Fixed submission:
import sys
input=sys.stdin.readline
mod=10**9+7

n=int(input())
e=[[] for i in range(n)]
dp=[[0,0] for i in range(n)]
for i in range(n-1):
    a,b=[int(j)-1 for j in input().split()]
    e[a].append(b)
    e[b].append(a)

par=[-1]*(n)
l=[]
from collections import deque
q=deque([0])
while q:
    p=q.pop()
    l.append(p)
    for i in e[p]:
        if i==par[p]:
            continue
        par[i]=p
        q.append(i)

dpw=[1]*(n+1)
dpb=[1]*(n+1)

for i in l[::-1]:
    w=dpw[i]
    b=dpb[i]
    p=par[i]
    dpw[p]*=(b+w)
    dpw[p]%=mod
    dpb[p]*=w
    dpb[p]%=mod

print((dpw[0]+dpb[0])%mod)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
n,m=map(int,input().split())
s=input()
t=input()

def gcd(a, b):

	while b>0:

		a, b = b, a % b

	return a

def lcm(a, b):

	return a * b // gcd (a, b)


l=(lcm(n,m))

a=["A" for i in range(l)]

for i in range(n):
    a[int(l/n)*i]=s[i]

for i in range(m):
    if a[int(l/m)*i]!="A" and a[int(l/m)*i]!=t[i]:
        print(-1)
        sys.exit()
    
print(l)


Fixed submission:
n,m=map(int,input().split())
s=input()
t=input()

#最大公約数
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)

l=lcm(n,m)

a=l//n
b=l//m
ln=[]
lm=[]
i=0
while i<n:
    ln.append(i)
    i+=b
i=0
while i<m:
    lm.append(i)
    i+=a

p=0
for i in range(len(ln)):
    if s[ln[i]]!=t[lm[i]]:
        p=1
if p==0:
    print(l)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
n,m=map(int,input().split())
s=input()
t=input()

def gcd(a, b):

	while b:

		a, b = b, a % b

	return a

def lcm(a, b):

	return a * b // gcd (a, b)


l=(lcm(n,m))

a=["A" for i in range(l)]

for i in range(n):
    a[int(l/n)*i]=s[i]

for i in range(m):
    if a[int(l/m)*i]!="A" and a[int(l/m)*i]!=t[i]:
        print(-1)
        sys.exit()
    
print(l)


Fixed submission:
n,m=map(int,input().split())
s=input()
t=input()

#最大公約数
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)

l=lcm(n,m)

a=l//n
b=l//m
ln=[]
lm=[]
i=0
while i<n:
    ln.append(i)
    i+=b
i=0
while i<m:
    lm.append(i)
    i+=a

p=0
for i in range(len(ln)):
    if s[ln[i]]!=t[lm[i]]:
        p=1
if p==0:
    print(l)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
n=int(input())
xyh=[]
h0=[]
for i in range(n):
    a=[int(j) for j in input().split()]
    xyh.append(a)

for x in range(101):
    for y in range(101):
        p=0
        l=max(0,xyh[0][2]+abs(x-xyh[0][0])+abs(y-xyh[0][1]))
        for i in range(n):
            if xyh[i][2]==0:
                if l>abs(x-xyh[i][0])+abs(y-xyh[i][1]:
                    p=1
                    break
                else:
                    continue
            if l==max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1])):
                l=max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1]))
            else:
                p=1
                break
        if p==0:
            print(x,y,l)
            import sys
            sys.exit()
            



Fixed submission:
n=int(input())
xyh=[]
h0=[]
for i in range(n):
    a=[int(j) for j in input().split()]
    xyh.append(a)

from operator import itemgetter
xyh.sort(key=itemgetter(2))
xyh.reverse()

for x in range(101):
    for y in range(101):
        p=0
        l=max(0,xyh[0][2]+abs(x-xyh[0][0])+abs(y-xyh[0][1]))
        for i in range(n):
            if xyh[i][2]==0:
                if l>abs(x-xyh[i][0])+abs(y-xyh[i][1]):
                    p=1
                    break
                else:
                    continue
            if l==max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1])):
                l=max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1]))
            else:
                p=1
                break
        if p==0:
            print(x,y,l)
            import sys
            sys.exit()

Buggy python submission (verdict: Runtime Error):
n=int(input())
xyh=[]
for i in range(n):
    a=[int(j) for j in input().split()]
    if a[2]!=0:
        xyh.append(a)

for x in range(101):
    for y in range(101):
        p=0
        l=max(0,xyh[0][2]+abs(x-xyh[0][0])+abs(y-xyh[0][1]))
        for i in range(n):
            if l==max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1])):
                l=max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1]))
            else:
                p=1
                break
        if p==0:
            print(x,y,l)
            import sys
            sys.exit()
            



Fixed submission:
n=int(input())
xyh=[]
h0=[]
for i in range(n):
    a=[int(j) for j in input().split()]
    xyh.append(a)

from operator import itemgetter
xyh.sort(key=itemgetter(2))
xyh.reverse()

for x in range(101):
    for y in range(101):
        p=0
        l=max(0,xyh[0][2]+abs(x-xyh[0][0])+abs(y-xyh[0][1]))
        for i in range(n):
            if xyh[i][2]==0:
                if l>abs(x-xyh[i][0])+abs(y-xyh[i][1]):
                    p=1
                    break
                else:
                    continue
            if l==max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1])):
                l=max(0,xyh[i][2]+abs(x-xyh[i][0])+abs(y-xyh[i][1]))
            else:
                p=1
                break
        if p==0:
            print(x,y,l)
            import sys
            sys.exit()