Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().rstrip()
Query = []
for _ in range(Q):
    Alp, LR = map(str, input().rstrip().split())
    Query.append((Alp, LR))

left = 0
for Alp, LR in reversed(Query):
    if S[left] == Alp and LR == "L":
        left += 1
right = 0
for Alp, LR in reversed(Query):
    if S[N-1-right] == Alp and LR == "R":
        right += 1
print(max(0, N-left-right))

Fixed submission:
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
S = input().rstrip()
TD = [list(map(str, input().split())) for _ in range(Q)]

l = 0
r = N
while r - l > 1:
    m = (l+r)//2
    right_over = False
    pl = m
    for t, d in TD:
        if S[pl] == t:
            if d == 'L':
                pl -= 1
                if pl == -1:
                    break
            else:
                pl += 1
                if pl == N:
                    right_over = True
                    break
    if right_over:
        r = m
    else:
        l = m

right = l

l = 0
r = N
while r - l > 1:
    m = (l+r)//2
    left_over = False
    pl = m
    for t, d in TD:
        if S[pl] == t:
            if d == 'L':
                pl -= 1
                if pl == -1:
                    left_over = True
                    break
            else:
                pl += 1
                if pl == N:
                    break
    if left_over:
        l = m
    else:
        r = m

left = l

print(right-left)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
mod = 10**9+7

def main():
    N, X = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    L = max(A[-1], X)

    dp = [[0]*N for _ in range(L+1)]
    a = A[0]
    for x in range(L+1):
        dp[x][0] = x%a

    dp1 = [[0]*N for _ in range(L+1)] #累積和見たいな
    for n in range(1, N):
        a = A[n]
        for x in range(L+1):
            dp1[x][n] = ((n-1) * dp1[x][n-1] + dp[x][n-1]) % mod
        for x in range(L+1):
            dp[x][n] = dp1[x%a][n]

    ans = 0
    t = 1
    for n in reversed(range(N)):
        ans = (ans + dp[X][n]*t) % mod
        t = t * n % mod

    print(ans)


if __name__ == "__main__":
    main()

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

def main():
    N, X = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    L = max(A[-1], X)

    dp = [[0]*N for _ in range(L+1)]
    a = A[0]
    for x in range(L+1):
        dp[x][0] = x%a

    dp1 = [0 for _ in range(L+1)] #累積和見たいな
    for n in range(1, N):
        a = A[n]
        for x in range(L+1):
            dp1[x] = ((n-1) * dp1[x] + dp[x][n-1]) % mod
            dp[x][n] = dp1[x%a]

    ans = 0
    t = 1
    for n in reversed(range(N)):
        ans = (ans + dp[X][n]*t) % mod
        t = t * n % mod

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 2*10**5 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# 足す時は0~iまで一律に足し、返すのはi番目の値
class imosBIT():
    def __init__(self, N):
        self.N = N+1
        self.bit = [0 for _ in range(self.N+1)]
    
    def __str__(self):
        ret = []
        for i in range(1, self.N+1):
            ret.append(self.__getitem__(i))
        return "[" + ", ".join([str(a) for a in ret]) + "]"

    def __getitem__(self, i):
        i += 1
        s = 0
        while i <= self.N:
            s = (s + self.bit[i]) % mod
            i += i & -i
        return s

    def add(self, i, x):
        i += 1
        while i > 0:
            self.bit[i] = (self.bit[i] + x) % mod
            i -= i & -i
    
    # (i, N]に全てたす
    def addover(self, i, x):
        self.add(self.N-1, x)
        self.add(i, -x)

B, W = map(int, input().split())
N = B+W
Abit = imosBIT(N+1)
Bbit = imosBIT(N+1)
inv2 = pow(2, mod-2, mod)
t = inv2
for i in range(N):
    if i+1 >= W:
        Abit.addover(i, t*cmb(i, W-1)%mod)
    if i+1 >= B:
        Bbit.addover(i, t*cmb(i, B-1)%mod)
    t = t*inv2 % mod

for i in range(N):
    ans = (1 + Abit[i] - Bbit[i]) * inv2 % mod
    print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

mod = 10**9+7
def cmb(n, r, mod=mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NN = 2*10**5 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# 足す時は0~iまで一律に足し、返すのはi番目の値
class imosBIT():
    def __init__(self, N):
        self.N = N+1
        self.bit = [0 for _ in range(self.N+1)]
    
    def __str__(self):
        ret = []
        for i in range(1, self.N+1):
            ret.append(self.__getitem__(i))
        return "[" + ", ".join([str(a) for a in ret]) + "]"

    def __getitem__(self, i):
        i += 1
        s = 0
        while i <= self.N:
            s = (s + self.bit[i]) % mod
            i += i & -i
        return s

    def add(self, i, x):
        i += 1
        while i > 0:
            self.bit[i] = (self.bit[i] + x) % mod
            i -= i & -i
    
    # (i, N]に全てたす
    def addover(self, i, x):
        self.add(self.N-1, x)
        self.add(i, -x)

B, W = map(int, input().split())
N = B+W
Abit = imosBIT(N+1)
Bbit = imosBIT(N+1)
inv2 = pow(2, mod-2, mod)
t = inv2
for i in range(N):
    if i+1 >= W:
        Abit.addover(i, t*cmb(i, W-1)%mod)
    if i+1 >= B:
        Bbit.addover(i, t*cmb(i, B-1)%mod)
    t = t*inv2 % mod

for i in range(N):
    ans = (1 + Abit[i] - Bbit[i]) * inv2 % mod
    print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))

S = sum(A)
d = 10**14
for i, a in enumerate(A):
  if abs(a*N-S) < d:
    d = abs(a*N-S)
    ind = i
    
print(ind)

Fixed submission:
n = int(input())
A = list(map(int, input().split()))

S = sum(A)
d = 10**14
for i, a in enumerate(A):
  if abs(a*n-S) < d:
    d = abs(a*n-S)
    ind = i
    
print(ind)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right

N = int(input().rstrip())
S = input()
Q = int(input())
Ks = list(map(int, input().split()))

for K in Ks:
    # [D, M, DM, DMC]
    dp = [[0]*4 for _ in range(N+1)]
    for i in range(N):
        if i-K >= 0:
            sk = S[i-K]
            if sk == 'D':
                dp[i][0] -= 1
                dp[i][2] -= dp[i][1]
            elif sk == "M":
                dp[i][1] -= 1
        s = S[i]
        if s == "D":
            dp[i+1][0] = dp[i][0] + 1
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]
            dp[i+1][3] = dp[i][3]
        elif s == 'M':
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1] + 1
            dp[i+1][2] = dp[i][2] + dp[i+1][0]
            dp[i+1][3] = dp[i][3]
        elif s == 'C':
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]
            dp[i+1][3] = dp[i][3] + dp[i][2]
        else:
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]
            dp[i+1][3] = dp[i][3]
    
    print(dp[N][3])

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    N = int(input().rstrip())
    S = input()
    Q = int(input())
    Ks = list(map(int, input().split()))

    for K in Ks:
        # [D, M, DM, DMC]
        dp = [0]*4
        for i in range(N):
            if i-K >= 0:
                sk = S[i-K]
                if sk == 'D':
                    dp[0] -= 1
                    dp[2] -= dp[1]
                elif sk == "M":
                    dp[1] -= 1
            s = S[i]
            if s == "D":
                dp[0] += 1
            elif s == 'M':
                dp[1] += 1
                dp[2] += dp[0]
            elif s == 'C':
                dp[3] += dp[2]
        
        print(dp[3])
    

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N, M, Q = map(int, input().split())
Left = [0 for _ in range(N)]
Right = [0 for _ in range(N)]
V = [[] for _ in range(N)]
for _ in range(M):
    l, r = map(int, input().split())
    Left[l-1] += 1
    Right[r-1] += 1
    V[r-1].append(l-1)

PQ = [list(map(int, input().split())) for _ in range(Q)]

T = [[0 for _ in range(N)] for _ in range(N)]
a = M
nextl = 0
for l in range(N):
    b = a - nextl
    nextl = Left[l]
    nextr = 0
    for r in range(N-1, l-1, -1):
        T[l][r] = max(b - nextr, 0)
        nextr += Right[r]
        for li in V[r]:
            if li < l:
                nextr -= 1
    a = b


for p, q in PQ:
    print(T[p-1][q-1]) 

Fixed submission:
N, M, Q = map(int, input().split())
Left = [0 for _ in range(N)]
Right = [0 for _ in range(N)]
V = [[] for _ in range(N)]
for _ in range(M):
    l, r = map(int, input().split())
    Left[l-1] += 1
    Right[r-1] += 1
    V[r-1].append(l-1)

PQ = [list(map(int, input().split())) for _ in range(Q)]

T = [[0 for _ in range(N)] for _ in range(N)]
a = M
nextl = 0
for l in range(N):
    b = a - nextl
    nextl = Left[l]
    nextr = 0
    for r in range(N-1, l-1, -1):
        T[l][r] = max(b - nextr, 0)
        nextr += Right[r]
        for li in V[r]:
            if li < l:
                nextr -= 1
    a = b


for p, q in PQ:
    print(T[p-1][q-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import numpy as np

N, M, S, G = map(int, input().split())
ABCD = np.array([list(map(int, input().split())) for _ in range(M)])
A = ABCD[:, 0]
B = ABCD[:, 1]
C = ABCD[:, 2]
D = ABCD[:, 3]

graph_y = csr_matrix((C, (A, B)), (N+1, N+1))
graph_s = csr_matrix((D, (A, B)), (N+1, N+1))

Ds = dijkstra(graph_y, directed=False, indices=S).astype('int64')
Dg = dijkstra(graph_s, directed=False, indices=G).astype('int64')

ans = Ds + Dg
for i in reversed(range(1, N)):
    ans[i] = min(ans[i+1], ans[i])

for n in range(1, N+1):
    print(10**15-ans[n])

Fixed submission:
import sys
input = sys.stdin.readline

import heapq as hp

N, M, S, G = map(int, input().split())
graph_y = [[] for _ in range(N)]
graph_s = [[] for _ in range(N)]
for _ in range(M):
    a, b, c, d = map(int, input().split())
    graph_y[a-1].append((c, b-1))
    graph_y[b-1].append((c, a-1))
    graph_s[a-1].append((d, b-1))
    graph_s[b-1].append((d, a-1))

INF = 10**18

def dijkstra(graph, s):
    D = [INF for _ in range(N)] # 頂点iへの最短距離がD[i]
    D[s] = 0 
    q = [] # しまっていく優先度付きキュー
    hp.heappush(q, (0, s))

    while q:
        nd, np = hp.heappop(q) # 一番距離が近いものを取ってくる
        if D[np] < nd: # 追加した後の残骸は見ない
            continue
        for d, p in graph[np]:
            if D[p] > D[np] + d: # 隣接するやつの中で今よりも近くなれるなら更新
                D[p] = D[np] + d
                hp.heappush(q, (D[p], p))
    
    return D

Ds = dijkstra(graph_y, S-1)
Dg = dijkstra(graph_s, G-1)

ans = [None]*N
ans[N-1] = Ds[N-1] + Dg[N-1]
for n in reversed(range(N-1)):
    ans[n] = min(ans[n+1], Ds[n]+Dg[n])

for a in ans:
    print(10**15-a)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from operator import itemgetter

N = int(input())
A = list(map(int, input().split()))

Max = [[(0, A[0])]]
ans = 0
for bit in range(1, (1<<N)):
    dic = {}
    for i in range(N):
        if bit&(1<<i) != 0:
            for ind, val in Max[bit-(1<<i)]:
                dic[ind] = val
    com = [(bit, A[bit])]
    for ind, val in dic.items():
        com.append((ind, val))
    com.sort(reverse=True, key=itemgetter(1))
    Max.append(com[:2])
    tmp = com[0][1] + com[1][1]
    if tmp > ans:
        ans = tmp
    print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

Max = [[(0, A[0])]]
ans = 0
for bit in range(1, (1<<N)):
    dic = {bit: A[bit]}
    for i in range(N):
        if bit&(1<<i) != 0:
            for ind, val in Max[bit-(1<<i)]:
                dic[ind] = val
    com = []
    for ind, val in dic.items():
        if len(com) < 2:
            com.append((ind, val))
        else:
            if com[0][1] < com[1][1]:
                if com[0][1] < val:
                    com[0] = (ind, val)
                elif com[1][1] < val:
                    com[1] = (ind, val)
            else:
                if com[1][1] < val:
                    com[1] = (ind, val)
                elif com[0][1] < val:
                    com[0] = (ind, val)               
    Max.append(com)
    tmp = com[0][1] + com[1][1]
    if tmp > ans:
        ans = tmp
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from operator import itemgetter

N = int(input())
A = list(map(int, input().split()))

Max = [[(0, A[0])]]
ans = 0
for bit in range(1, (1<<N)):
    dic = {}
    for i in range(N):
        if bit&(1<<i) != 0:
            for ind, val in Max[bit-(1<<i)]:
                dic[ind] = val
    com = [(bit, A[bit])]
    for ind, val in dic.items():
        com.append((ind, val))
    com.sort(reverse=True, key=itemgetter(1))
    Max.append(com[:2])
    tmp = com[0][1] + com[1][1]
    if tmp > ans:
        ans = tmp
    print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

Max = [[(0, A[0])]]
ans = 0
for bit in range(1, (1<<N)):
    dic = {bit: A[bit]}
    for i in range(N):
        if bit&(1<<i) != 0:
            for ind, val in Max[bit-(1<<i)]:
                dic[ind] = val
    com = []
    for ind, val in dic.items():
        if len(com) < 2:
            com.append((ind, val))
        else:
            if com[0][1] < com[1][1]:
                if com[0][1] < val:
                    com[0] = (ind, val)
                elif com[1][1] < val:
                    com[1] = (ind, val)
            else:
                if com[1][1] < val:
                    com[1] = (ind, val)
                elif com[0][1] < val:
                    com[0] = (ind, val)               
    Max.append(com)
    tmp = com[0][1] + com[1][1]
    if tmp > ans:
        ans = tmp
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())

P = [n for n in range(1, 10)]
Q = [n for n in range(1, 10)]
for d in range(20):
    if d < 8:
        for m in range(10, 100):
            P.append(int(str(m)+"9"*d))
            Q.append(m//10+m%10+9*d)
    else:
        for m in range(100, 1000):
            P.append(int(str(m)+"9"*(d-1)))
            Q.append(sum([int(s) for s in str(m)])+9*(d-1))

L = len(P)
c = 0
for i, (p, q) in enumerate(zip(P, Q)):
    ok = True
    for j in range(i+1, L):
        np, nq = P[j], Q[j]
        if np*q < nq*p:
            ok = False
            break
    if ok:
        print(p)
        c += 1
    if c == K:
        break


"""
import matplotlib.pyplot as plt

A = []
B = []
for n in range(-1+10**10, 10**15, 10**10):
    m = sum([int(s) for s in str(n)])
    A.append(n)
    B.append(n/m)


plt.plot(A, B)
plt.show()
"""

Fixed submission:
K = int(input())

P = [n for n in range(1, 10)]
Q = [n for n in range(1, 10)]
for d in range(20):
    if d < 12:
        for m in range(10, 100):
            P.append(int(str(m)+"9"*d))
            Q.append(m//10+m%10+9*d)
    else:
        for m in range(100, 1000):
            P.append(int(str(m)+"9"*(d-1)))
            Q.append(sum([int(s) for s in str(m)])+9*(d-1))

L = len(P)
c = 0
for i, (p, q) in enumerate(zip(P, Q)):
    ok = True
    for j in range(i+1, L):
        np, nq = P[j], Q[j]
        if np*q < nq*p:
            ok = False
            break
    if ok:
        print(p)
        c += 1
    if c == K:
        break


"""
import matplotlib.pyplot as plt

A = []
B = []
for n in range(-1+10**10, 10**14, 10**10):
    m = sum([int(s) for s in str(n)])
    A.append(n)
    B.append(n/m)


plt.plot(A, B)
plt.show()
"""
Buggy python submission (verdict: Runtime Error):
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
grid = [list(map(int, input().split())) for _ in range(N)]

def main():
    state = [[0 for _ in range(C)] for _ in range(3)]
    for c in range(C):
        for w in range(N):
            for h in range(N):
                cost = D[grid[h][w]-1][c]
                state[(h+w)%3][c] += cost

    for c1 in range(C):
        for c2 in range(C):
            if c1 == c2:
                continue
            for c3 in range(C):
                if c3 == c1 or c3 == c2:
                    continue
                cost = state[0][c1] + state[1][c2] + state[2][c3]
                if c1 == 0 and c2 == 1 and c3 == 2:
                    ans = cost
                    continue
                ans = min(cost, ans)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
N = int(input())

if N < 1000:
    print('ABC')
else:
    print('ABD')
Buggy python submission (verdict: Time Limit Exceeded):
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
grid = [list(map(int, input().split())) for _ in range(N)]

state = [[0 for _ in range(C)] for _ in range(3)]
for c in range(C):
    for w in range(N):
        for h in range(N):
            cost = D[grid[h][w]-1][c]
            state[(h+w)%3][c] += cost

for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c3 == c1 or c3 == c2:
                continue
            cost = state[0][c1] + state[1][c2] + state[2][c3]
            if c1 == 0 and c2 == 1 and c3 == 2:
                ans = cost
                continue
            ans = min(cost, ans)
print(ans)

Fixed submission:
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
grid = [list(map(int, input().split())) for _ in range(N)]

def main():
    state = [[0 for _ in range(C)] for _ in range(3)]
    for c in range(C):
        for w in range(N):
            for h in range(N):
                cost = D[grid[h][w]-1][c]
                state[(h+w)%3][c] += cost

    for c1 in range(C):
        for c2 in range(C):
            if c1 == c2:
                continue
            for c3 in range(C):
                if c3 == c1 or c3 == c2:
                    continue
                cost = state[0][c1] + state[1][c2] + state[2][c3]
                if c1 == 0 and c2 == 1 and c3 == 2:
                    ans = cost
                    continue
                ans = min(cost, ans)
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N = int(input())
S = np.array([0 if a == 'E' else 1 for a in input()])

ans = N
for i in range(N):
    ans = min(ans, np.count_nonzero(S[:i]) + np.count_nonzero(S[i+1:]-1))

print(ans)

Fixed submission:
N = int(input())
S = [0 if a == 'E' else 1 for a in input()]
Sp = [S[0]]
for i in range(1, N):
    Sp.append(Sp[-1]+S[i])

max = Sp[-1]
ans = N - max
for i in range(1, N):
    ans = min(abs(Sp[i-1]) + abs(N-(i+1)-max+Sp[i]), ans)

print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
N = len(S)
K = int(input())

S1 = {}
for i, s in enumerate(S):
    if not s in S1.keys():
        S1[s] = [i]
    else:
        S1[s].append(i)
alp = sorted(list(S1.keys()))

c = 0
for a in alp:
    aset = set()
    inds = S1[a]
    for d in inds:
        for i in range(N-d+1):
            aset.add(S[d:d+i])
    if len(aset)-1 >= K-c:
        break
    c += len(aset)-1


for _ in range(5):
    for i, a in enumerate(aset):
        if i == 0:
            min = a
            continue
        if a < min:
            min = a
    aset.discard(min)
    if min == '':
        continue
    c += 1
    if c >= K:
        ans = min
        break

print(ans)


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

if abs(c-a) <= d or (abs(b-a) <= d and abs(c-b) <= d):
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())
state = [[1 if a == '#' else 0 for a in list(input()+'.')] for _ in range(H)]
state.extend([[0]*(W+1)])

ans = 'Yes'
for h in range(H):
    for w in range(W):
        if state[h][w] == 0:
            continue
        nexts = [[h+1, w], [h-1, w], [h, w+1], [h, w-1]]
        ok = False
        for n in nexts:
            if state[n[0]][n[1]] == 1:
                ok = True
        if not ok:
            ans = 'No'
            break
    if not ok:
        break

print(ans)


Fixed submission:
H, W = map(int, input().split())
state = [[1 if a == '#' else 0 for a in list(input()+'.')] for _ in range(H)]
state.extend([[0]*(W+1)])


ans = 'Yes'
for h in range(H):
    for w in range(W):
        if state[h][w] == 0:
            continue
        nexts = [[h+1, w], [h-1, w], [h, w+1], [h, w-1]]
        ok = False
        for n in nexts:
            if state[n[0]][n[1]] == 1:
                ok = True
        if not ok:
            ans = 'No'
            break
    if ans == 'No':
        break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    state = [list(input()) for _ in range(N)]

    ans = 0
    for i in range(N):
        ok = True
        for x in range(N):
            for y in range(N):
                if state[(x+i)%N][y] != state[(i+y)%N][x]:
                    ok = False
                    break
        if ok:
            ans += N
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    state = [list(input()) for _ in range(N)]

    ans = 0
    for i in range(N):
        ok = True
        for x in range(N):
            for y in range(N):
                if state[(x+i)%N][y] != state[(i+y)%N][x]:
                    ok = False
                    break
        if ok:
            ans += N
    print(ans)

if __name__ == "__main__":
    main()