Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
A,B,C,D=map(int,input().split())
mod=998244353
dp=[[0 for y in range(D-B+1)]for x in range(C-A+1)]
dp[0][0]=1
for x in range(C-A):
    dp[x+1][0]=(dp[x][0]*B)%mod
for y in range(D-B):
    dp[0][y+1]=(dp[0][y]*A)%mod
for x in range(C-A):
    for y in range(D-B):
        dp[x+1][y+1]=(dp[x+1][y]*(A+x))%mod
        dp[x+1][y+1]+=(dp[x][y+1]*(B+y))%mod
        dp[x+1][y+1]%=mod
        dp[x+1][y+1]-=(dp[x][y]*(A+x)*(B+y))%mod
        dp[x+1][y+1]%=mod
        dp[x+1][y+1]+=(dp[x+1][y]+dp[x][y+1])%mod
        dp[x+1][y+1]%=mod

print(dp[C-A][D-B])


Fixed submission:
A,B,C,D=map(int,input().split())
mod=998244353
dp=[[0 for y in range(D-B+1)]for x in range(C-A+1)]
dp[0][0]=1
for x in range(C-A):
    dp[x+1][0]=(dp[x][0]*B)%mod
for y in range(D-B):
    dp[0][y+1]=(dp[0][y]*A)%mod
for x in range(C-A):
    for y in range(D-B):
        dp[x+1][y+1]=(dp[x+1][y]*(A+x))%mod
        dp[x+1][y+1]+=(dp[x][y+1]*(B+y))%mod
        dp[x+1][y+1]%=mod
        dp[x+1][y+1]-=(dp[x][y]*(A+x)*(B+y))%mod
        dp[x+1][y+1]%=mod
        dp[x+1][y+1]+=(dp[x+1][y]+dp[x][y+1])%mod
        dp[x+1][y+1]%=mod

print(dp[C-A][D-B])
Buggy python submission (verdict: Time Limit Exceeded):
N,S=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
dp=[[0 for j in range(S+1)]for i in range(N+1)]
pow2N=pow(2,N,mod)
dp[0][0]=pow2N
inv2=pow(2,mod-2,mod)
for i in range(N):
    for j in range(S+1):
        if dp[i][j]!=0:
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod
            if j+A[i]<=S:
                dp[i+1][j+A[i]]+=(inv2*dp[i][j])%mod
                dp[i+1][j+A[i]]%=mod
print(dp[N][S])


Fixed submission:
N,S=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
dp=[[0 for j in range(S+1)]for i in range(N+1)]
pow2N=pow(2,N,mod)
dp[0][0]=pow2N
inv2=pow(2,mod-2,mod)
for i in range(N):
    for j in range(S+1):
        if dp[i][j]!=0:
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod
            if j+A[i]<=S:
                dp[i+1][j+A[i]]+=(inv2*dp[i][j])%mod
                dp[i+1][j+A[i]]%=mod
print(dp[N][S])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import heapq
T=int(input())
for testcase in range(T):
    N,A,B,C,D=map(int,input().split())
    dist=defaultdict(lambda:10**23)
    dist[N]=0
    q=[]
    heapq.heappush(q,(0,N,0))
    while(len(q)!=0):
        nowdist,num,onestreak=heapq.heappop(q)
        if dist[num]<nowdist:
            continue
        if dist[0]>dist[num]+num*D:
            dist[0]=dist[num]+num*D
            heapq.heappush(q,(dist[0],0,num*D))
        if num%2==0 and (dist[num//2]>dist[num]+A):
            dist[num//2]=dist[num]+A
            heapq.heappush(q,(dist[num//2],num//2,0))
        if num%3==0 and (dist[num//3]>dist[num]+B):
            dist[num//3]=dist[num]+B
            heapq.heappush(q,(dist[num//3],num//3,0))
        if num%5==0 and (dist[num//5]>dist[num]+C):
            dist[num//5]=dist[num]+C
            heapq.heappush(q,(dist[num//5],num//5,0))
        if onestreak<5 and (dist[num+1]>dist[num]+D):
            dist[num+1]=dist[num]+D
            heapq.heappush(q,(dist[num+1],num+1,onestreak+1))
        if onestreak<5 and num>=1 and (dist[num-1]>dist[num]+D):
            dist[num-1]=dist[num]+D
            heapq.heappush(q,(dist[num-1],num-1,onestreak+1))
    print(dist[0])

    
        
        

Fixed submission:
from collections import defaultdict
import heapq
T=int(input())
for testcase in range(T):
    N,A,B,C,D=map(int,input().split())
    dist=defaultdict(lambda:10**23)
    dist[N]=0
    q=[]
    heapq.heappush(q,(0,N,0))
    while(len(q)!=0):
        nowdist,num,onestreak=heapq.heappop(q)
        if dist[num]<nowdist:
            continue
        if dist[0]>dist[num]+num*D:
            dist[0]=dist[num]+num*D
            heapq.heappush(q,(dist[0],0,num*D))
        if num%2==0 and (dist[num//2]>dist[num]+A):
            dist[num//2]=dist[num]+A
            heapq.heappush(q,(dist[num//2],num//2,0))
        if num%3==0 and (dist[num//3]>dist[num]+B):
            dist[num//3]=dist[num]+B
            heapq.heappush(q,(dist[num//3],num//3,0))
        if num%5==0 and (dist[num//5]>dist[num]+C):
            dist[num//5]=dist[num]+C
            heapq.heappush(q,(dist[num//5],num//5,0))
        if onestreak<5 and (dist[num+1]>dist[num]+D):
            dist[num+1]=dist[num]+D
            heapq.heappush(q,(dist[num+1],num+1,onestreak+1))
        if onestreak<5 and num>=1 and (dist[num-1]>dist[num]+D):
            dist[num-1]=dist[num]+D
            heapq.heappush(q,(dist[num-1],num-1,onestreak+1))
    print(dist[0])
Buggy python submission (verdict: Runtime Error):
#差がC以下はダメ（Cもダメ）
N,K,C=map(int,input().split())
S=input()
X=[]
for i in range(N):
    if S[i]=="o":
        X.append(i+1)
M=len(X)
#例外処理（M=1のとき）
#ACしたので試験的にコメントアウト
'''
if M==1:
    #このときK==1
    print(X[0])
    exit()
'''
#X[i]日に働くとき、その直前or直後で働ける最も近い日のindex
L=[-1 for i in range(M)]
R=[-1 for i in range(M)]
j=1
for i in range(M-1):
    while(j<M):
        if X[j]-X[i]>=C+1:
            R[i]=j
            break
        else:
            j+=1
j=M-2
for i in range(M-1,0,-1):
    while(j>=0):
        if X[i]-X[j]>=C+1:
            L[i]=j
            break
        else:
            j-=1
LD=[-1 for i in range(M)]
RD=[-1 for i in range(M)]
def Ldfs(i):
    if LD[i]!=-1:
        return LD[i]
    if L[i]==-1:
        LD[i]=1
        return 1
    else:
        LD[i]=Ldfs(L[i])+1
        return Ldfs(L[i])+1
def Rdfs(i):
    if RD[i]!=-1:
        return RD[i]
    if R[i]==-1:
        RD[i]=1
        return 1
    else:
        RD[i]=Rdfs(R[i])+1
        return Rdfs(R[i])+1
for i in range(M):
    Ldfs(i)
    Rdfs(M-1-i)
Y=[0 for i in range(M)]
Y[0]=RD[1]
Y[-1]=LD[-2]
for i in range(1,M-1):
    Y[i]=LD[i-1]+RD[i+1]
for i in range(M):
    if Y[i]<K:
        print(X[i])


Fixed submission:
#差がC以下はダメ（Cもダメ）
N,K,C=map(int,input().split())
S=input()
X=[]
for i in range(N):
    if S[i]=="o":
        X.append(i+1)
M=len(X)
#例外処理（M=1のとき）
if M==1:
    #このときK==1
    print(X[0])
    exit()

#X[i]日に働くとき、その直前or直後で働ける最も近い日のindex
L=[-1 for i in range(M)]
R=[-1 for i in range(M)]
j=1
for i in range(M-1):
    while(j<M):
        if X[j]-X[i]>=C+1:
            R[i]=j
            break
        else:
            j+=1
j=M-2
for i in range(M-1,0,-1):
    while(j>=0):
        if X[i]-X[j]>=C+1:
            L[i]=j
            break
        else:
            j-=1
LD=[-1 for i in range(M)]
RD=[-1 for i in range(M)]
def Ldfs(i):
    if LD[i]!=-1:
        return LD[i]
    if L[i]==-1:
        LD[i]=1
        return 1
    else:
        LD[i]=Ldfs(L[i])+1
        return Ldfs(L[i])+1
def Rdfs(i):
    if RD[i]!=-1:
        return RD[i]
    if R[i]==-1:
        RD[i]=1
        return 1
    else:
        RD[i]=Rdfs(R[i])+1
        return Rdfs(R[i])+1
for i in range(M):
    Ldfs(i)
    Rdfs(M-1-i)
Y=[0 for i in range(M)]
Y[0]=RD[1]
Y[-1]=LD[-2]
for i in range(1,M-1):
    Y[i]=LD[i-1]+RD[i+1]
for i in range(M):
    if Y[i]<K:
        print(X[i])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
DN={N}
k=2
while(k*k<=N):
    if N%k==0:
        DN.add(k)
        DN.add(N//k)
    k+=1
DN1={N-1}
k=2
while(k*k<=(N-1)):
    if (N-1)%k==0:
        DN1.add(k)
        DN1.add((N-1)//k)
    k+=1
DN=sorted(list(DN))
DN1=sorted(list(DN1))
#print(DN)
#print(DN1)
ans=set()
for K in DN:
    tmp=N
    while(tmp>=K):
        if tmp%K==0:
            tmp//=K
        else:
            tmp%=K
    if tmp==1:
        ans.add(K)
for K in DN1:
    tmp=N
    while(tmp>=K):
        if tmp%K==0:
            tmp//=K
        else:
            tmp%=K
    if tmp==1:
        ans.add(K)


#print(ans)
print(len(ans))


Fixed submission:
N=int(input())
if N==2:
    print(1)
    exit()
DN={N}
k=2
while(k*k<=N):
    if N%k==0:
        DN.add(k)
        DN.add(N//k)
    k+=1
DN1={N-1}
k=2
while(k*k<=(N-1)):
    if (N-1)%k==0:
        DN1.add(k)
        DN1.add((N-1)//k)
    k+=1
DN1=len(DN1)
#print(DN)
#print(DN1)
ans=0
for K in DN:
    tmp=N
    while(tmp>=K):
        if tmp%K==0:
            tmp//=K
        else:
            tmp%=K
    if tmp==1:
        ans+=1

#print(ans)
print(DN1+ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
a=[int(i)-1 for i in list(input())]
def solve(seq):
    res=0
    for k in range(N):
        tmp=1
        if (N&k)==k:
            tmp=0
        res+=tmp*seq[k]
        res%=2
    if res%2==1:
        return 1
    if 1 in set(seq):
        return 0
    seq2=[seq[i]//2 for i in range(N)]
    return solve(seq2)*2
print(solve(a))

Fixed submission:
N=int(input())
a=[int(i)-1 for i in list(input())]
def solve(seq):
    if {0}==set(seq):
        return 0
    res=0
    for k in range(N):
        tmp=0
        if ((N-1)&k)==k:
            tmp=1
        #print(tmp)
        res+=tmp*seq[k]
        res%=2
    #print("#"*30)
    if res%2==1:
        return 1
    if 1 in set(seq):
        return 0
    seq2=[seq[i]//2 for i in range(N)]
    return solve(seq2)*2
print(solve(a))
Buggy python submission (verdict: Runtime Error):
from collections import deque
N=int(input())
X=[chr(i+97) for i in range(N)]
q=deque(["a"])
while(len(q)>0):
    r=q.popleft()
    k=len(set(r))
    for i in range(k+1):
        p=r+X[i]
        if len(p)==N:
            print(p)
        else:
            q.append(p)


Fixed submission:
from collections import deque
N=int(input())
if N==1:
    print("a")
    exit()
X=[chr(i+97) for i in range(N)]
#print(X)
Y=[]
q=deque(["a"])
while(len(q)>0):
    r=q.pop()
    k=len(set(r))
    for i in range(k+1):
        p=r+X[i]
        if len(p)==N:
            Y.append(p)
        else:
            q.append(p)
Y.sort()
for line in Y:
    print(line)
Buggy python submission (verdict: Runtime Error):
import math
N=int(input())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
p=[]
for i in range(N):
    x[i],y[i]=map(int,input().split())
    p.append((x[i],y[i]))
X,Y,R=0,0,0
def dist(p,q):
    a,b=p
    c,d=q
    return math.sqrt((a-c)**2+(b-d)**2)
if N==2:
    print(dist(p[0],p[1])/2)
    exit()
a=dist(p[1],p[2])
b=dist(p[2],p[0])
c=dist(p[0],p[1])
aa=a*a*(b*b+c*c-a*a)
bb=b*b*(c*c+a*a-b*b)
cc=c*c*(a*a+b*b-c*c)

X=(aa*p[0][0]+bb*p[1][0]+cc*p[2][0])/(aa+bb+cc)
Y=(aa*p[0][1]+bb*p[1][1]+cc*p[2][1])/(aa+bb+cc)
R=dist((X,Y),p[0])
#print(dist((X,Y),p[0]))
#print(dist((X,Y),p[1]))
#print(dist((X,Y),p[2]))
for i in range(3,N):
    if dist((X,Y),p[i])<=R:
        continue
    d=dist((X,Y),p[i])
    nX=(X*(R+d)+p[i][0]*(d-R))/(2*d)
    nY=(Y*(R+d)+p[i][1]*(d-R))/(2*d)
    nR=(R+d)/2
    X,Y,R=nX,nY,nR
print(R)

Fixed submission:
import math
N=int(input())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
p=[]
for i in range(N):
    x[i],y[i]=map(int,input().split())
    p.append((x[i],y[i]))
def dist(p,q):
    a,b=p
    c,d=q
    return math.sqrt((a-c)**2+(b-d)**2)
def check(R):
    Q=[]
    for i in range(N):
        for j in range(i+1,N):
            d=dist(p[i],p[j])/2
            if R<d:
                return False
            h=math.sqrt(R*R-d*d)
            #print(d,h,R)
            nx,ny=(x[j]-x[i],y[j]-y[i])
            nr=math.sqrt(nx**2+ny**2)
            dx,dy=h*nx/nr,h*ny/nr
            mx,my=(x[i]+x[j])/2,(y[i]+y[j])/2
            #print(mx,my)
            #print(dx,dy)
            Q.append((mx+dy,my-dx))
            Q.append((mx-dy,my+dx))
    #print(Q,R)
    for pa in Q:
        flag=1
        for i in range(N):
            #print(pa,i,dist(pa,p[i]),R)
            if dist(pa,p[i])>R+9e-7:
                flag=0
                break
        if flag==1:
            return True
    return False

low=0
high=2000
for line in range(50):
    mid=(low+high)/2
    if check(mid):
        high=mid
    else:
        low=mid
print(mid)
Buggy python submission (verdict: Runtime Error):
N=int(input())
s=["" for i in range(N)]
t=["" for i in range(N)]
for i in range(N):
  s[i],t[i]=input().split()
  t[i]=int(t[i])
X=int(input())
flag=0
ans=0
for i in range(N):
  if flag==1:
    ans+=t[i]
  else:
    if s[i]==X:
      flag=1
print(ans)


Fixed submission:
N=int(input())
s=["" for i in range(N)]
t=["" for i in range(N)]
for i in range(N):
    s[i],t[i]=input().split()
    t[i]=int(t[i])
X=input()
flag=0
ans=0
for i in range(N):
    if flag==1:
        ans+=t[i]
    else:
        if s[i]==X:
            flag=1
print(ans)
Buggy python submission (verdict: Runtime Error):
#T=(0,0,...,0)
#に変換するためのコストの2^N倍
N=int(input())
c=sorted([int(i) for i in input().split()])
mod=10**9+7
ans=0
for k in range(N):
    a1=pow(2,N-2,mod)
    a2=(N-k+1)
    tmp=(a1*a2)%mod
    ans+=(c[k]*tmp)%mod
    ans%=mod
    #print(k,tmp)
ans=ans*pow(2,N,mod)
ans%=mod
print(ans)


Fixed submission:
#T=(0,0,...,0)
#に変換するためのコストの2^N倍
N=int(input())
c=sorted([int(i) for i in input().split()])
mod=10**9+7
if N==1:
    print((2*c[0])%mod)
    exit()
ans=0
for k in range(N):
    a1=pow(2,N-2,mod)
    a2=(N-k+1)
    tmp=(a1*a2)%mod
    ans+=(c[k]*tmp)%mod
    ans%=mod
    #print(k,tmp)
ans=ans*pow(2,N,mod)
ans%=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import random
N=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
#N=2*10**5
#a=[random.randrange(2**30) for i in range(N)]
#b=[random.randrange(2**30) for i in range(N)]

for k in range(N):
    x=a[k]^b[0]
    flag=1
    for line in range(1000):
        i=random.randrange(N)
        if a[(k+i)%N]^b[i]!=x:
            flag=0
            break
    if flag==1:
        print(k,x)


Fixed submission:
#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + s[i]) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[a[i%N]^a[(i+1)%N] for i in range(2*N)]
d=[b[i]^b[(i+1)%N] for i in range(N)]
P=RollingHash(c,97,10**9+7)
Q=RollingHash(d,97,10**9+7)

for k in range(N):
    if P.get(k,k+N)==Q.get(0,N):
        x=b[0]^a[k]
        print(k,x)
Buggy python submission (verdict: Time Limit Exceeded):
N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()
#T r→P点
#T s→R点
#T p→S点
r=0;s=1;p=2;m=3
#dp[r,s,p][range(N)]:
#dp[i][j]:j番目まで見たとき、最後がiのときのmax
def calc(U):
    M=len(U)
    dp=[[0 for j in range(M+1)] for i in range(4)]
    j=0
    if U[j]=="r":
        dp[p][j+1]=dp[m][j]+P
    elif U[j]=="s":
        dp[r][j+1]=dp[m][j]+R
    else:
        dp[s][j+1]=dp[m][j]+S
    dp[m][j+1]=max(dp[r][j+1],dp[s][j+1],dp[p][j+1])
    for j in range(1,M):
        for i in range(3):
            dp[i][j+1]=max(dp[(i+1)%3][j],dp[(i+2)%3][j])
        #print(dp[0][j+1],dp[1][j+1],dp[2][j+1])
        if U[j]=="r":
            dp[p][j+1]+=P
        elif U[j]=="s":
            dp[r][j+1]+=R
        else:
            dp[s][j+1]+=S
        dp[m][j+1]=max(dp[r][j+1],dp[s][j+1],dp[p][j+1])
    #for line in dp:
    #    print(line)
    
    return dp[3][-1]
Y=["" for i in range(K)]
for i in range(N):
    Y[i%K]=Y[i%K]+T[i]
#print(Y)
ans=0
for t in Y:
    k=calc(t)
    #print(t,k)
    ans+=k
print(ans)


Fixed submission:
N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()
#T r→P点
#T s→R点
#T p→S点
r=0;s=1;p=2;m=3
#dp[r,s,p][range(N)]:
#dp[i][j]:j番目まで見たとき、最後がiのときのKおきの和のmax
dp=[[0 for j in range(N)] for i in range(4)]
for j in range(K):
    if T[j]=="r":
        dp[p][j]=P
    elif T[j]=="s":
        dp[r][j]=R
    else:
        dp[s][j]=S
    dp[m][j]=max(dp[r][j],dp[s][j],dp[p][j])
for j in range(K,N):
    for i in range(3):
        dp[i][j]=max(dp[(i+1)%3][j-K],dp[(i+2)%3][j-K])
    if T[j]=="r":
        dp[p][j]+=P
    elif T[j]=="s":
        dp[r][j]+=R
    else:
        dp[s][j]+=S
    dp[m][j]=max(dp[r][j],dp[s][j],dp[p][j])
ans=0
for i in range(K):
    ans+=dp[m][-i-1]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(i) for i in input().split()]
ans=0
mod=10**9+7
for k in range(60):
    X=0
    Y=0
    for i in range(N):
        if A[i]^(2**k)>A[i]:
            X+=1
        else:
            Y+=1
    #print(X,Y)
    ans+=pow(2,k,mod)*(X*Y)
    ans%=mod
print(ans)


Fixed submission:
N=int(input())
A=[int(i) for i in input().split()]
ans=0
mod=10**9+7
for k in range(60):
    X=0
    Y=0
    for i in range(N):
        if A[i]^(2**k)>A[i]:
            X+=1
        else:
            Y+=1
    #print(X,Y)
    ans+=pow(2,k,mod)*(X*Y)
    ans%=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def sign(x):
    if x==0:
        return 0
    else:
        return abs(x)//x
def flag(x,y):
    return sign(x)==sign(y)
T1,T2=map(int,input().split())
A1,A2=map(int,input().split())
B1,B2=map(int,input().split())
if A1*T1+A2*T2==B1*T1+B2*T2:
    print("infinity")
    exit()
ans=0
X=(B1-A1)*T1
Y=(B2-A2)*T2
tmp=0
while(1):
    if tmp==0:
        tmp+=X
    else:
        if not(flag(tmp,tmp+X)):
            ans+=1
            tmp+=X
    if tmp==0:
        tmp+=Y
    else:
        if not(flag(tmp,tmp+Y)):
            ans+=1
            tmp+=Y
    if flag(tmp,tmp+X) and flag(tmp+X,tmp+X+Y):
        break
print(ans)

Fixed submission:
T1,T2=map(int,input().split())
A1,A2=map(int,input().split())
B1,B2=map(int,input().split())
X=(B1-A1)*T1
Y=(B2-A2)*T2
if X>0:
    X=-X
    Y=-Y
if X+Y<0:
    print(0)
elif X+Y==0:
    print("infinity")
else:
    A=(-X)//(X+Y)
    B=(-X)%(X+Y)
    if B!=0:
        print(2*A+1)
    else:
        print(2*A)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
#abs(a-b)<c<a+b
N=int(input())
L=sorted([int(i) for i in input().split()])
ans=0
#print(L)
for i in range(N):
    for j in range(i+1,N):
        A=bisect.bisect_left(L,L[i]+L[j])
        B=bisect.bisect_right(L,abs(L[i]-L[j]))
        tmp=A-B
        if B<=i<A:
            tmp-=1
        if B<=j<A:
            tmp-=1
        ans+=tmp
        #print(i,j,A,B,tmp)
print(ans//3)
        


Fixed submission:
import bisect
#abs(a-b)<c<a+b
N=int(input())
L=sorted([int(i) for i in input().split()])
ans=0
#print(L)
for i in range(N):
    for j in range(i+1,N):
        A=bisect.bisect_left(L,L[i]+L[j])
        B=bisect.bisect_right(L,abs(L[i]-L[j]))
        tmp=A-B
        if B<=i<A:
            tmp-=1
        if B<=j<A:
            tmp-=1
        ans+=tmp
        #print(i,j,A,B,tmp)
print(ans//3)
Buggy python submission (verdict: Time Limit Exceeded):
N,M,L=map(int,input().split())
G=[[10**15 for i in range(N)] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j]=min(G[i][j],G[i][k]+G[k][j])
H=[[10**15 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j]<=L:
            H[i][j]=1
for k in range(N):
    for i in range(N):
        for j in range(N):
            H[i][j]=min(H[i][j],H[i][k]+H[k][j])
Q=int(input())
for line in range(Q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if H[s][t]==10**15:
        print(-1)
    else:
        print(H[s][t]-1)


Fixed submission:
N,M,L=map(int,input().split())
G=[[10**15 for i in range(N)] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j]=min(G[i][j],G[i][k]+G[k][j])
H=[[10**15 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j]<=L:
            H[i][j]=1
for k in range(N):
    for i in range(N):
        for j in range(N):
            H[i][j]=min(H[i][j],H[i][k]+H[k][j])
Q=int(input())
for line in range(Q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if H[s][t]==10**15:
        print(-1)
    else:
        print(H[s][t]-1)

Buggy python submission (verdict: Time Limit Exceeded):
N,M,L=map(int,input().split())
G=[[10**15 for i in range(N)] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j]=min(G[i][j],G[i][k]+G[k][j])
H=[[10**15 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j]<=L:
            H[i][j]=1
for k in range(N):
    for i in range(N):
        for j in range(N):
            H[i][j]=min(H[i][j],H[i][k]+H[k][j])
Q=int(input())
for line in range(Q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if H[s][t]==10**15:
        print(-1)
    else:
        print(H[s][t]-1)


Fixed submission:
N,M,L=map(int,input().split())
G=[[10**15 for i in range(N)] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j]=min(G[i][j],G[i][k]+G[k][j])
H=[[10**15 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j]<=L:
            H[i][j]=1
for k in range(N):
    for i in range(N):
        for j in range(N):
            H[i][j]=min(H[i][j],H[i][k]+H[k][j])
Q=int(input())
for line in range(Q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if H[s][t]==10**15:
        print(-1)
    else:
        print(H[s][t]-1)
Buggy python submission (verdict: Runtime Error):
def count(st):
    n=len(st)
    tmp=1
    res=[]
    for i in range(n-1):
        if st[i]==st[i+1]:
            tmp+=1
        else:
            res.append(tmp)
            tmp=1
    res.append(tmp)
    return res
S=input()
K=int(input())
T=S*3
N=len(S)

if K<=2:
    Y=count(S*K)
    ans=0
    for i in Y:
        ans+=i//2
    print(ans)
    exit()
X=[]
if S[0]==S[-1]:
    for j in range(1,N):
        if S[j-1]!=S[j]:
            break
    tmp=1
    for i in range(j,j+N-1):
        if T[i]==T[i+1]:
            tmp+=1
        else:
            X.append(tmp)
            tmp=1
    X.append(tmp)
else:
    X=count(S)

cnt=0
for i in X:
    cnt+=i//2
Y=count(T)
cnt2=0
for i in Y:
    cnt2+=i//2
print(cnt*(K-3)+cnt2)


Fixed submission:
def count(st):
    n=len(st)
    tmp=1
    res=[]
    for i in range(n-1):
        if st[i]==st[i+1]:
            tmp+=1
        else:
            res.append(tmp)
            tmp=1
    res.append(tmp)
    return res
S=input()
K=int(input())
T=S*3
N=len(S)
if N==1:
    print(K//2)
    exit()
if K<=2:
    Y=count(S*K)
    ans=0
    for i in Y:
        ans+=i//2
    print(ans)
    exit()
if S.count(S[0])==N:
    print((N*K)//2)
    exit()
X=[]
if S[0]==S[-1]:
    for j in range(1,N):
        if S[j-1]!=S[j]:
            break
    tmp=1
    for i in range(j,j+N-1):
        if T[i]==T[i+1]:
            tmp+=1
        else:
            X.append(tmp)
            tmp=1
    X.append(tmp)
else:
    X=count(S)

cnt=0
for i in X:
    cnt+=i//2
Y=count(T)
cnt2=0
for i in Y:
    cnt2+=i//2
print(cnt*(K-3)+cnt2)