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

N = int(input())
a = [int(input()) for i in range(N)]
for i in range(N):
  b = copy.deepcopy(a)
  del b[i]
  print(sorted(b, reverse=True)[0])


Fixed submission:
from heapq import *

N=int(input())
A=[int(input()) for i in range(N)]
h=[]
for i in A:
    heappush(h, -i)
maxh = -heappop(h)
secondh = -heappop(h)
for i in A:
    print(maxh if i != maxh else secondh)

Buggy python submission (verdict: Runtime Error):
N = int(input())
a = [int(input()) for i in range(N)]
for i in range(N):
  b = a
  del b[i]
  sorted(b)
  print(b[0])

Fixed submission:
from heapq import *

N=int(input())
A=[int(input()) for i in range(N)]
h=[]
for i in A:
    heappush(h, -i)
maxh = -heappop(h)
secondh = -heappop(h)
for i in A:
    print(maxh if i != maxh else secondh)
Buggy python submission (verdict: Runtime Error):
N=int(input())
b=list(map(int,input().split()))
a=[0]*N
for i in range(N):
    z = N-i-1
    while z <= N-1:
        a[N-1-i] += b[z]
        z=(z+1)*2-1
print(sum(a))
if sum(a) != 0:
    s = ''
    for i in a:
        s += str(i) + ' ' if i != 0 else ''
print(s.rstrip())


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    a=list(map(int,input().split()))
    l=[0]*N
    l2=[]
    ans=0
    for i,x in enumerate(reversed(a)):
        z=N-i
        c=0
        for j in range(2,N//z+1):
            c+=l[z*j-1]
        if c%2!=x:
            l[N-1-i]+=1
            ans+=1
            l2.append(N-i)
    print(ans)
    print(*l2)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
a = list(map(int,input().split()))
print(0 if x[0]<a[1] else 10)


Fixed submission:
a = list(map(int,input().split()))
print(0 if a[0]<a[1] else 10)

Buggy python submission (verdict: Runtime Error):
a = list(map(int,input().split()))
print(0 if x<a else 10)

Fixed submission:
a = list(map(int,input().split()))
print(0 if a[0]<a[1] else 10)
Buggy python submission (verdict: Runtime Error):
a = list(map(int,input().split()))
b = list(map(int,input().split()))
d = 0
count = 0
while d <= a[1]:
  count += 1
  d += b[count]
print(count)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,X=map(int,input().split())
    L=list(map(int,input().split()))
    ans=1
    D=0
    for i in L:
        D+=i
        if D<=X:
            ans+=1
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    W,H,x,y=map(int,input().split())
    S=W*H/2
    b=1 if x==W//2 and y==H//2 else 0
    print(f'%s %s' % (S, b))

if __name__ == '__main__':
    main()


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    W,H,x,y=map(int,input().split())
    S=W*H/2
    b=1 if x==W/2 and y==H/2 else 0
    print(str(S)+' '+str(b))

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    W,H,x,y=map(int,input().split())
    S=W*H/2
    b=1 if x==W//2 and y==H//2 else 0
    print(f'{S} {b}'.format(S=S, b=b))

if __name__ == '__main__':
    main()


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    W,H,x,y=map(int,input().split())
    S=W*H/2
    b=1 if x==W/2 and y==H/2 else 0
    print(str(S)+' '+str(b))

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    W,H,x,y=map(int,input().split())
    S=W*H/2
    b=1 if x==W//2 and y==H//2 else 0
    print(f'{S} {b}')

if __name__ == '__main__':
    main()


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    W,H,x,y=map(int,input().split())
    S=W*H/2
    b=1 if x==W/2 and y==H/2 else 0
    print(str(S)+' '+str(b))

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    S=tuple(map(int,input().split()))
    T=tuple(map(int,input().split()))
    dp=[[0]*(M+1) for _ in range(N+1)]
    SUM=[[0]*(M+2) for _ in range(N+2)]
    ans=1
    for s in range(N):
        for t in range(M):
            if S[s]==T[t]:
                dp[s+1][t+1]=SUM[s+1][t+1]+1
                ans+=dp[s+1][t+1]
                ans%=MOD
            else:
                dp[s+1][t+1]=0
            SUM[s+2][t+2]=SUM[s+1][t+2]+SUM[s+2][t+1]-SUM[s+1][t+1]+dp[s+1][t+1]
    print(ans)
    

if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    S=tuple(map(int,input().split()))
    T=tuple(map(int,input().split()))
    dp=[[0]*(M+1) for _ in range(N+1)]
    SUM=[[0]*(M+2) for _ in range(N+2)]
    ans=1
    for s in range(N):
        for t in range(M):
            if S[s]==T[t]:
                dp[s+1][t+1]=SUM[s+1][t+1]+1
                ans+=dp[s+1][t+1]
                ans%=MOD
            else:
                dp[s+1][t+1]=0
            SUM[s+2][t+2]=SUM[s+1][t+2]+SUM[s+2][t+1]-SUM[s+1][t+1]+dp[s+1][t+1]
            SUM[s+2][t+2]%=MOD
    print(ans)
    

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    L,A,B,M=map(int,input().split())
    S=lambda i:A+B*i
    sec=[]
    
    def nibutan(ok,ng,k):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid,k):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid,k):
        return len(str(S(mid)))<k
    
    left=L-1
    for k in range(19,0,-1):
        if len(str(S(left)))==k:
            right=nibutan(-1,left,k)
            sec.append((k,left,right))
            left=right
    
    def modinv(a, mod=M):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    ans=0
    c=0
    for k,left,right in sec:
        C=pow(10,k)
        n=left-right
        ans+=(S(left)*(pow(C,n)-1)-B*((n-1)*pow(C,n)-(pow(C,n)-1)//(C-1)+1))//(C-1)*pow(10,c)
        ans%=M
        c+=n*k
    print(ans)

if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import deque
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    L,A,B,M=map(int,input().split())
    S=lambda i:A+B*i
    sec=[]
    
    def nibutan(ok,ng,k):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid,k):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid,k):
        return len(str(S(mid)))<k
    
    left=L-1
    for k in range(19,0,-1):
        if len(str(S(left)))==k:
            right=nibutan(-1,left,k)
            sec.append((k,left,right))
            left=right
    
    X=np.array([0,A%M,1],dtype=np.int64)
    for k,left,right in sec[::-1]:
        n=left-right
        doubling=[np.array([[pow(10,k,M),0,0],[1,1,0],[0,B%M,1]],dtype=np.int64)]
        for i in range((10**18).bit_length()):
            doubling.append(np.dot(doubling[i],doubling[i])%M)
        n=left-right
        for i in range(len(doubling)):
            if n&1:
                X=np.dot(X,doubling[i])%M
            n>>=1
            if n==0:
                break
    print(X[0])

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from itertools import permutations
INF=10**9
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()

def main():
    M,K=map(int,input().split())
    if K!=0:
        raise Exception

if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    M,K=map(int,input().split())
    if K>2**M-1:
        print(-1)
    elif M==1:
        if K==0:
            print(0,0,1,1)
        else:
            print(-1)
    else:
        ans=[i for i in range(2**M) if i!=K]+[K]+[i for i in range(2**M-1,-1,-1) if i!=K]+[K]
        print(*ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF = 10**18


def input():
    return sys.stdin.readline().rstrip()


def main():
    N,K=map(int,input().split())
    S=list(map(int,list(input())))
    first=S[0]
    l=[]
    c=1
    for i in range(N-1):
        if S[i+1] == S[i]:
            c+=1
        else:
            l.append(c)
            c=1
    l.append(c)
    if K%2==1:
        if len(l) > K*2:
            ans = sum(l[:K*2])
            op=ans
            for i in range(len(l)-K*2):
                op = op-l[i]+l[K*2+i]
                ans=max(ans,op)
        else:
            ans = sum(l)
    else:
        if len(l) > K*2+1:
            ans=sum(l[:K*2+1])
            op=ans
            for i in range(not(first),len(l)-(K*2+1),2):
                op = op-(l[i]+l[i+1])+l[K*2+1+i]+l[K*2+1+i+1]
                ans = max(ans, op)
        else:
            ans=sum(l)
    print(ans)

if __name__ == '__main__':
    main()


Fixed submission:
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF = 10**18


def input():
    return sys.stdin.readline().rstrip()


def main():
    N,K=map(int,input().split())
    S=list(map(int,list(input())))
    f=S[0]
    left1=0
    for i,x in enumerate(S):
        if x==0:
            break
        else:
            left1+=1
    l=[left1]
    tmp=0
    pre=1
    for i,x in enumerate(S[left1:]):
        if pre!=x:
                l.append(tmp)
                tmp=0
        tmp+=1
        pre=x
    l.append(tmp)
    A=[0]*(len(l)+1)
    for i in range(len(l)):
        A[i+1]=A[i]+l[i]
    ans=0
    for i in range(len(l)+1):
        if i%2:
            ans=max(ans,A[i]-A[max(0,i-K*2)])
        else:
            ans=max(ans,A[i]-A[max(0,i-K*2-1)])
    print(ans)
    

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    S=input()
    T=input()
    dp=[[0]*(len(T)+1) for _ in range(len(S)+1)]
    dp2=[[()]*(len(T)+1) for _ in range(len(S)+1)]
    for s in range(len(S)):
        for t in range(len(T)):
            if S[s]==T[t]:
                dp[s+1][t+1]=dp[s][t]+1
                dp2[s+1][t+1]=(s,t)
            else:
                if dp[s+1][t]>dp[s][t+1]:
                    dp[s+1][t+1]=dp[s+1][t]
                    dp2[s+1][t+1]=dp2[s+1][t]
                else:
                    dp[s+1][t+1]=dp[s][t+1]
                    dp2[s+1][t+1]=dp2[s][t+1]
    tmp=dp2[len(S)][len(T)]
    ans=deque()
    ans.appendleft(S[tmp[0]])
    for _ in range(dp[len(S)][len(T)]-1):
        tmp=dp2[tmp[0]][tmp[1]]
        ans.appendleft(S[tmp[0]])
    print(''.join(ans))

if __name__ == '__main__':
    main()


Fixed submission:
S=list(input())
T=list(input())

dp = [[0]*(len(T)+1) for i in (range(len(S)+1))]

for s in range(len(S)):
    for t in range(len(T)):
        if S[s] == T[t]:
            dp[s+1][t+1] = max(dp[s][t]+1,dp[s][t+1],dp[s+1][t])
        else:
            dp[s+1][t+1] = max(dp[s][t+1],dp[s+1][t])

def checkdpn(x,y):
    if dp[x][y] == dp[x-1][y] + 1 and dp[x][y] == dp[x][y-1] + 1:
        return True
    else:
        return False

x = len(S)
y = len(T)
str = ''

while(True):
    if checkdpn(x,y):
        str = S[x-1] + str
        x -= 1
    else:
        if dp[x][y] == dp[x][y-1] + 1:
            x -= 1
        else:
            y -= 1
    if dp[x][y] == 0:
        break
print(str)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    S=input()
    T=input()
    dp=[['']*(len(T)+1) for _ in range(len(S)+1)]
    for s in range(len(S)):
        for t in range(len(T)):
            if S[s]==T[t]:
                dp[s+1][t+1]=dp[s][t]+S[s]
            else:
                if len(dp[s+1][t])>len(dp[s][t+1]):
                    dp[s+1][t+1]=dp[s+1][t]
                else:
                    dp[s+1][t+1]=dp[s][t+1]
    print(dp[len(S)][len(T)])

if __name__ == '__main__':
    main()


Fixed submission:
S=list(input())
T=list(input())

dp = [[0]*(len(T)+1) for i in (range(len(S)+1))]

for s in range(len(S)):
    for t in range(len(T)):
        if S[s] == T[t]:
            dp[s+1][t+1] = max(dp[s][t]+1,dp[s][t+1],dp[s+1][t])
        else:
            dp[s+1][t+1] = max(dp[s][t+1],dp[s+1][t])

def checkdpn(x,y):
    if dp[x][y] == dp[x-1][y] + 1 and dp[x][y] == dp[x][y-1] + 1:
        return True
    else:
        return False

x = len(S)
y = len(T)
str = ''

while(True):
    if checkdpn(x,y):
        str = S[x-1] + str
        x -= 1
    else:
        if dp[x][y] == dp[x][y-1] + 1:
            x -= 1
        else:
            y -= 1
    if dp[x][y] == 0:
        break
print(str)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    s=set(range(N))
    for _ in range(M):
        x,y=map(lambda x: int(x)-1,input().split())
        edge[x].append(y)
        try:
            s.remove(y)
        except:
            pass
    que=deque(s)
    memo=[0]*N
    ans=0
    while que:
        v=que.popleft()
        for nv in edge[v]:
            memo[nv]=max(memo[nv],memo[v]+1)
            ans=max(ans,memo[nv])
            que.append(nv)
    print(ans)
    
    

if __name__ == '__main__':
    main()


Fixed submission:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    s=set(range(N))
    for _ in range(M):
        x,y=map(lambda x: int(x)-1,input().split())
        edge[x].append(y)
        try:
            s.remove(y)
        except:
            pass
    que=list(s)
    memo=[0]*N
    def saiki(v):
        if memo[v]:
            return memo[v]
        tmp=0
        for nv in edge[v]:
            memo[v]=max(memo[v],saiki(nv)+1)
            tmp=max(tmp,memo[v])
        return tmp
    ans=0
    for v in que:
        ans=max(ans,saiki(v))
    print(ans)
    
    

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    d=defaultdict(int)
    x=2
    while M>1:
        if M%x==0:
            d[x]+=1
            M//=x
        else:
            x+=1
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+1)):
            fac[i]=fac[i-1]*i%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(N*2,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=1
    for v in d.values():
        ans*=COM(N-1+v,v,MOD)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    d=defaultdict(int)
    x=2
    while M>1:
        if M%x==0:
            d[x]+=1
            M//=x
        else:
            x+=1
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+1)):
            fac[i]=fac[i-1]*i%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(10**6,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=1
    for v in d.values():
        ans*=COM(N-1+v,v,MOD)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    S=list(input())
    A,C,Q=[0]*(len(S)+1),[0]*(len(S)+1),[0]*(len(S)+1)
    l_B=[]
    l_Q=[]
    q=0
    for i in range(len(S)):
        A[i+1]=A[i]+(S[i]=='A')
        C[i+1]=C[i]+(S[i]=='C')
        Q[i+1]=Q[i]+(S[i]=='?')
        if S[i]=='?':
            q+=1
            l_Q.append(i)
        if S[i]=='B':
            l_B.append(i)
    ans=0
    pow3q=pow(3,q,MOD)
    pow3q_1=pow(3,q-1,MOD)
    pow3q_2=pow(3,q-2,MOD)
    pow3q_3=pow(3,q-3,MOD)
    
    for x in l_B:
        ans+=A[x]*(C[len(S)]-C[x+1])*pow3q
        ans+=Q[x]*(C[len(S)]-C[x+1])*pow3q_1
        ans+=A[x]*(Q[len(S)]-Q[x+1])*pow3q_1
        ans+=Q[x]*(Q[len(S)]-Q[x+1])*pow3q_2
        ans%=MOD
    for x in l_Q:
        ans+=A[x]*(C[len(S)]-C[x+1])*pow3q_1
        ans+=Q[x]*(C[len(S)]-C[x+1])*pow3q_2
        ans+=A[x]*(Q[len(S)]-Q[x+1])*pow3q_2
        ans+=Q[x]*(Q[len(S)]-Q[x+1])*pow3q_3
        ans%=MOD        
    print(ans)
    

if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    S=list(input())
    A,C,Q=[0]*(len(S)+1),[0]*(len(S)+1),[0]*(len(S)+1)
    l_B=[]
    l_Q=[]
    q=0
    for i in range(len(S)):
        A[i+1]=A[i]+(S[i]=='A')
        C[i+1]=C[i]+(S[i]=='C')
        Q[i+1]=Q[i]+(S[i]=='?')
        if S[i]=='?':
            q+=1
            l_Q.append(i)
        if S[i]=='B':
            l_B.append(i)
    ans=0
    pow3q=pow(3,q,MOD)
    if q-1>=0:
        pow3q_1=pow(3,q-1,MOD)
    else:
        pow3q_1=0
    if q-2>=0:
        pow3q_2=pow(3,q-2,MOD)
    else:
        pow3q_2=0
    if q-3>=0:
        pow3q_3=pow(3,q-3,MOD)
    else:
        pow3q_3=0
    
    for x in l_B:
        ans+=A[x]*(C[len(S)]-C[x+1])*pow3q
        ans+=Q[x]*(C[len(S)]-C[x+1])*pow3q_1
        ans+=A[x]*(Q[len(S)]-Q[x+1])*pow3q_1
        ans+=Q[x]*(Q[len(S)]-Q[x+1])*pow3q_2
        ans%=MOD
    for x in l_Q:
        ans+=A[x]*(C[len(S)]-C[x+1])*pow3q_1
        ans+=Q[x]*(C[len(S)]-C[x+1])*pow3q_2
        ans+=A[x]*(Q[len(S)]-Q[x+1])*pow3q_2
        ans+=Q[x]*(Q[len(S)]-Q[x+1])*pow3q_3
        ans%=MOD        
    print(ans)
    

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    p=list(map(int1,input().split()))
    edge=[[] for _ in range(N)]
    for _ in range(M):
        x,y=map(int1,input().split())
        edge[x].append((0,y))
        edge[y].append((0,x))
    from heapq import heappop,heappush
    def dijkstra(start,n,edges):
        d=[INF]*n
        used=[False]*n
        d[start]=0
        used[start]=True
        edgelist=[]
        for edge in edges[start]:
            heappush(edgelist,edge)
        while edgelist:
            minedge=heappop(edgelist)
            if used[minedge[1]]:
                continue
            v=minedge[1]
            d[v]=minedge[0]
            used[v]=True
            for edge in edges[v]:
                if not used[edge[1]]:
                    heappush(edgelist,(edge[0]+d[v],edge[1]))
        return d
    ans=0
    for i in range(N):
        d=dijkstra(i,N,edge)
        if d[p[i]]==0:
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    p=list(map(int1,input().split()))
    class UnionFind:
        def __init__(self,n):
            self.par=[i for i in range(n)]
            self.siz=[1]*n
            
        def root(self,x):
            while self.par[x]!=x:
                self.par[x]=self.par[self.par[x]]
                x=self.par[x]
            return x
        
        def unite(self,x,y):
            x=self.root(x)
            y=self.root(y)
            if x==y:
                return False
            if self.siz[x]<self.siz[y]:
                x,y=y,x
            self.siz[x]+=self.siz[y]
            self.par[y]=x
            return True
        
        def is_same(self,x,y):
            return self.root(x)==self.root(y)
        
        def size(self,x):
            return self.siz[self.root(x)]
    
    u=UnionFind(N)
    for _ in range(M):
        x,y=map(int1,input().split())
        u.unite(x,y)
    ans=0
    for i in range(N):
        if u.is_same(i,p[i]):
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()