Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N,Q=[int(i) for i in input().rstrip().split()]
S = input().strip()
lr_list=[[int(j) for j in input().split()] for i in range(Q)]

calc_cnt=[]
for i in range(len(S)):
    sub_str = S[:(i+1)]
    cnt = sub_str.count("AC")
    calc_cnt += [cnt]

for l,r in lr_list:
    ans = calc_cnt[r-1] - calc_cnt[l-1]
    print(ans)


### FIXED CODE ###

N,Q=[int(i) for i in input().rstrip().split()]
S = input().strip()
lr_list=[[int(j) for j in input().split()] for i in range(Q)]

calc_cnt=[0]
for i in range(1,len(S)):
    sub_str = S[(i-1):(i+1)]
    
    if sub_str == "AC":
        calc_cnt += [calc_cnt[i-1] + 1]
    else:
        calc_cnt += [calc_cnt[i-1]]
        

for l,r in lr_list:
    ans = calc_cnt[r-1] - calc_cnt[l-1]
    print(ans)
### BUGGY CODE ###

import numpy as np
n, m = [int(i) for i in input().split()]
a =[]
d = 1000000007

for i in range(m):
    a1=int(input())
    a.append(a1)

a.append(n+1)
a = np.array(a)
#print(a)

if 1 in a[1:]-a[:-1]:
    print(0)

else:
    dp = [0]*1000001
    dp[1]=1
    dp[2]=1
    for i in range(3,len(dp)):
        dp[i]=dp[i-1]+dp[i-2]
        #dp[i]=dp[i]%d

    ans = []
    pre = 0
    for i in range(len(a)):
        if i == 0:
            ans.append(a[i]-pre)
        else:
            ans.append(a[i]-pre-1)
        pre = a[i]

    #print(ans)
    x = 1
    for i in ans:
        x = x*dp[i]%d
    print(x)

### FIXED CODE ###

import numpy as np
n, m = [int(i) for i in input().split()]
a =[]
d = 1000000007

for i in range(m):
    a1=int(input())
    a.append(a1)

a.append(n+1)
a = np.array(a)
#print(a)

if 1 in a[1:]-a[:-1]:
    print(0)

else:
    dp = [0]*110000
    dp[1]=1
    dp[2]=1
    for i in range(3,len(dp)):
        dp[i]=dp[i-1]+dp[i-2]
        dp[i]=dp[i]%d

    ans = []
    pre = 0
    for i in range(len(a)):
        if i == 0:
            ans.append(a[i]-pre)
        else:
            ans.append(a[i]-pre-1)
        pre = a[i]

    #print(ans)

    if m == 0:
        print(dp[n+1])
    else:
        x = 1
        for i in ans:
            x = x*dp[i]%d
        print(x)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))

b=[]
offset=0
if n%2==1:
    offset=1
for i in range(n):
    if (i+offset)%2==0:
        b.append(a[i])
    else:
        b.insert(0,a[i])
for i in b:
    print(i,end=" ")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))

b1=[]
b2=[]
offset=0
if n%2==1:
    offset=1
for i in range(n):
    if (i+offset)%2==0:
        b1.append(a[i])
    else:
        b2.append(a[i])
b2=list(reversed(b2))
b=b2+b1
for i in b:
    print(i,end=" ")
### BUGGY CODE ###

N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]

start = []
goal = []

import sys

for i in range(M):
    if ab[i][0] == 1:
        start.append(ab[i])
    if ab[i][1] == N:
        goal.append(ab[i])
        
for i in range(len(start)):
    for j in range(len(goal)):
        if len(set(start[i]) | set(goal[j])) == 3:
            print('POSSIBLE')
            sys.exit()
            
print('IMPOSSIBLE')

### FIXED CODE ###

N, M = map(int, input().split())
edges = [[] for i in range(N)]
 
for i in range(M):
    a, b = map(int, input().split())
    edges[a].append(b)
    
#スタートは1なのでedges[1]をみる
for i in edges[1]:
    #edges[1]のつながり先にNがあるかどうか
    if N in edges[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

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

#print(A)
No=[]
for i in range(1,N+1):
  a=str(A.index(i)+1)
  No.append(a)

#print(No)
print(' '.join(No))

### FIXED CODE ###

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

dic={}
for i,a in enumerate(A):
  dic[a]=str(i+1)

for k,v in sorted(dic.items()) :
  print(v)
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    ans = 0

    for i in range(n-1):
        for j in range(i+1,n):
            for cnt in range(min(j-i,n-j)):
                if s[i+cnt] == s[j+cnt]:
                    continue
                else:
                    cnt -= 1
                    break
            ans = max(ans,cnt+1)
    print(ans)

main()


### FIXED CODE ###

def main():
    n = int(input())
    s = input()
    dp = [[0]*(n+1) for i in range(n+1)]
    ans = 0
    for i in range(n-1)[::-1]:
        for j in range(i+1,n)[::-1]:
            if s[i] == s[j]:
                dp[i][j] = max(dp[i][j], dp[i+1][j+1] + 1)
                ans = max(ans, min(dp[i][j],j-i))
    print(ans)
main()
### BUGGY CODE ###

inf = float('inf')

n = int(input())
a = tuple(int(input()) for _ in range(n))

c = [inf]

for aa in a:
    push_to = -1
    target = -1
    for i, cc in enumerate(c):
        if target < cc < aa:
            push_to = i
            target = cc
    if push_to != -1:
        c[push_to] = aa
    else:
        c.append(aa)
    # print(c)
print(len(c) - 1)


### FIXED CODE ###

from bisect import bisect_left
from collections import deque

n = int(input())
a = tuple(int(input()) for _ in range(n))

d = deque()

for ai in a:
    p = bisect_left(d, ai)  # aa以上の最小値のindex
    if p == 0:
        d.appendleft(ai)
    else:
        d[p - 1] = ai
ans = len(d)
print(ans)
### BUGGY CODE ###



def p(k,w,maxP):
    count = 1
    tmpList = []
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
        else:
            count += 1
            tmpList = []
            tmpList.append(x)
    
    if count > k :
        result = False
    else:
        result = True

    return result


def pout(k,w,maxP):
    tmpList = []
    mP = 0
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
        else:
            tmpList = []
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
    

    return mP


n,k = map(int,input().split())


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)

### FIXED CODE ###



def p(k,w,maxP):
    count = 1
    tmpWeight = 0
    for x in w:
        if tmpWeight+x <= maxP:
            tmpWeight += x
        else:
            count += 1
            if count > k :
                return False
            tmpWeight = x
    

    return True




n,k = map(int,input().split())


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)
### BUGGY CODE ###

# ABC063c
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
s = [int(input()) for _ in range(n)]


def dfs(i, su):
    if i == n:
        return su if su % 10 != 0 else 0
    return max(dfs(i+1, su+s[i]), dfs(i+1, su))


print(dfs(0, 0))


### FIXED CODE ###

# ABC063c
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
s = [int(input()) for _ in range(n)]

s.sort()
ans = sum(s)
if ans % 10 != 0:
    print(ans)
    exit(0)
for i in s:
    if i % 10 != 0:
        ans -= i
        print(ans)
        exit(0)
print(0)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(3*(10**5))


N, Q = map(int, input().split())
T = [[0, []] for _ in range(N+1)] #counter, nearest-children
E = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]
for e in E:
  T[e[0]][1].append(e[1])
for px in PX:
  T[px[0]][0] += px[1]
for t in T:
  for c in t[1]:
    T[c][0] += t[0]
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)



### FIXED CODE ###

import sys
sys.setrecursionlimit(3*(10**5))


N, Q = map(int, input().split())
T = [[0, []] for _ in range(N+1)] #counter, nearest-children
E = [list(map(int, input().split())) for _ in range(N-1)]
PX = [list(map(int, input().split())) for _ in range(Q)]
for e in E:
  T[e[0]][1].append(e[1])
for px in PX:
  T[px[0]][0] += px[1]
for t in T:
  for c in t[1]:
    T[c][0] += t[0]
ans_s = ""
for t in T[1:]:
  ans_s += "%d "%t[0]
print(ans_s)
### BUGGY CODE ###

s=input()
n=int(input())
for i in range(n):
  strlist=input()
  if strlist[0]=='1':
    s=s[::-1]
  elif strlist[0]=='2' and strlist[2] == '1':
    s = '{}{}'.format(strlist[4],s)
  else:
    s = '{}{}'.format(s,strlist[4])
print(s)

### FIXED CODE ###

from collections import deque
s=deque(input())
n=int(input())
r=0
for i in range(n):
    strlist=input()
    if strlist[0]=='1':
        r+=1
    elif strlist[0]=='2' and strlist[2] == '1':
        if r%2==0:
            s.appendleft(strlist[4])
        else:
            s.append(strlist[4])
    elif strlist[0]=='2' and strlist[2] =='2':
        if r%2==0:
            s.append(strlist[4])
        else:
            s.appendleft(strlist[4])
if r%2==0:
    for s_ in s:
        print(s_, end='')
else:
    s.reverse()
    for s_ in s:
        print(s_, end='')
### BUGGY CODE ###

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

ans = 1
for i in range(n):
    ans *= A[i]

if ans <= 10 ** 18:
    print(ans)
else:
    print('-1')


### FIXED CODE ###

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

if 0 in A:
    print('0')
else:
    ans = 1
    for i in range(n):
        ans *= A[i]
        if ans > 10 ** 18:
            print('-1')
            break
    if ans <= 10 ** 18:
        print(ans)
### BUGGY CODE ###

s = list(input())
q = int(input())
for i in range(1,q+1):
  queue = list(input().split())
  if queue[0] == '1':
    s.reverse()
  else:
    if queue[1] == '1':
      s.insert(0,queue[2])
    else:
      s.append(queue[2])
print(''.join(s))

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
ref=0
for i in range(Q):
    T=input().split()
    if T[0] == '2':
        if (T[1]=='1' and ref%2==0):
            S.appendleft(T[2])
        elif (T[1]=='2' and ref%2==0):
            S.append(T[2])
        elif (T[1]=='1' and ref%2==1):
            S.append(T[2])
        elif (T[1]=='2' and ref%2==1):
            S.appendleft(T[2])
    else:
        ref+=1
for i in range(len(S)):
    if ref%2==0:
        char=S.popleft()
        print(char,end='')
    else:
        char=S.pop()
        print(char,end='')
### BUGGY CODE ###

N,K,Q=map(int,input().split())
A=[int(input()) for _ in range(Q)]
Point=[K for _ in range(N)]
len_Point=len(Point)
for a in A:
    for i in range(len_Point):
        if i!=a-1:
            Point[i]=Point[i]-1
for p in Point:
    if p<=0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

N,K,Q=map(int,input().split())
# A=[int(input()) for _ in range(Q)]
point=[0]*N
for i in range(Q):
    point[int(input())-1]+=1
for i in range(N):
    ans=K-(Q-point[i])
    if ans>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

L,R = map(int,input().split())

x = R - L
L %= 2019
R = L + x

#print(L,R)

m = 2019
for i in range(L,R+1):
  for j in range(i+1,R+1):
    m = min(m,(i*j)%2019)
    if m == 0:
      break
print(m)
    



### FIXED CODE ###

L,R = map(int,input().split())

x = R - L
if x > 2018:
  ans = 0
else:
  ans = 2019
  for i in range(L,R+1):
   for j in range(i+1,R+1):
     ans = min(ans,(i*j)%2019)
     if ans == 0:
       break

print(ans)
    
#332701087 1753412895
### BUGGY CODE ###

# x1,x2=(0,0)とする
# x2*y3 - x3*y2 == S
# を満たす(x2,y2),(x3,y3)を求める

S=int(input())
# x3,y2のペアで探索してみよう
for x3 in range(1,10**9):
  for y2 in range(1,10**9):
    rest=x3*y2+S
    # restを構成する10**9以下の数値のペアが作れるか
    for x2 in range(1,int((10**9)**0.5)+1):
      if rest%x2==0:
        y3=rest//x2
        if y3>10**9:
          continue
        print(0,0,x2,y2,x3,y3)
        exit(0)

### FIXED CODE ###

# (0,0),(a,b),(c,d)
# (10**9, 1)(x,y)
# 10**9 * y - x == S
# S = 10**9 * a + bとおくと
# y = a + 1
# x = 10**9- b

S=int(input())
if S==10**18:
  print(0,0,10**9,0,0,10**9)
  exit(0)
DIV=10**9
a = S//DIV
b = S%DIV
x = 10**9-b
y = a + 1
if x>10**9:
  print(x)
if y>10**9:
  print(y)
print(0,0,10**9,1,x,y)
### BUGGY CODE ###

import math

N,K,*AF = map(int, open(0).read().split())
A = sorted(AF[:N])
F = sorted(AF[N:],reverse=True)
init = [A[i] * F[i] for i in range(N)]
left = 0
right = max(init)
while left != right:
    mid = (left+right) // 2
    temp = [max(A[i]-math.floor(mid/F[i]),0) for i in range(N)]
    if sum(temp) <= K:
        right = mid
    else:
        left = mid + 1
print(left)

### FIXED CODE ###

import math

N,K,*AF = map(int, open(0).read().split())
A = sorted(AF[:N])
F = sorted(AF[N:],reverse=True)
left = 0
right = max(A) * max(F)
while left != right:
    mid = (left+right) // 2
    temp = 0
    for i in range(N):
        temp += max(A[i]-math.floor(mid/F[i]),0)
        if temp > K:
            left = mid + 1
            break
    else:
        right = mid
print(left)
### BUGGY CODE ###

N = int(input())
s = []
count=0

def duplicates(list):
  seen=[]
  return [x for x in s if x not in seen and not seen.append(x)]

for i in range(N):
  a = list(input())
  a.sort()
  s.append(''.join(a))

duplicate_list = duplicates(s)

for i in range (len(duplicate_list)):
  for j in range (s.count(duplicate_list[i])):
    count += j

print(count)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
s = defaultdict(lambda:0)
count=0

for i in range(N):
  a = "".join(sorted(input()))
  s[a] +=1
  
  if s[a] >1:
    count += s[a]-1
print(count)
### BUGGY CODE ###

import numpy as np

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

count = [0]
sum = 0


for i in A:
    if max(count) > i:
        sum += max(count) -i
        count.append(i)
    else:
        count.append(i)

print(sum)

### FIXED CODE ###

n = input()
x = input().split()
m = 0
cnt = 0
 
for i in x:
    ii = int(i)
    if m < ii:
        m = ii
    elif m > ii:
        cnt += m - ii
 
print(cnt)
### BUGGY CODE ###

n,q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

#これはセグ木 * bisect
import bisect
inf = 10**9 + 100

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    seg[0] = 2**(num-1)
    return(seg)

def update(head, tail, x):
    # print('{} {} {}'.format(head, tail, x))
    head += seg[0]
    tail += seg[0]
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute(p):
    p += seg[0]
    tmp = seg[p]
    while(p > 0):
        p = p//2
        tmp = min(tmp, sep[p])
    return(tmp)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg = init(q, init_num = inf)

for i in range(n):
    left = bisect.bisect_left(d, stx[i][0] -stx[i][2])
    right = bisect.bisect_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    # print('{} {} {}'.format(left, right, stx[i][2]))

execute_all()

for i in seg[seg[0]: seg[0] + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,q = map(int, input().split())
# stx = [tuple(map(int, input().split())) for _ in range(n)]
stx = [0]*n
for i in range(n):
    stx[i] = tuple(map(int, input().split()))
# d = [int(input()) for _ in range(q)]
d = [0]*q
for i in range(q):
    d[i] = int(input())

#これはセグ木 * bisect
import bisect
inf = 10**9 + 100

# 定数倍高速化
b_left = bisect.bisect_left
b_right = bisect.bisect_right

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    # seg[0] = 2**(num-1)
    seg0 = 2**(num-1)
    return(seg,seg0)

def update(head, tail, x):
    # print('{} {} {}'.format(head, tail, x))
    head += seg0
    tail += seg0
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg,seg0 = init(q, init_num = inf)

for i in range(n):
    left = b_left(d, stx[i][0] -stx[i][2])
    right = b_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    # print('{} {} {}'.format(left, right, stx[i][2]))

execute_all()

for i in seg[seg0: seg0 + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)
### BUGGY CODE ###

#C問題
#考え方：平方根に近いところを探す。
#平方根を切り上げた値からスタート。割り切れた時点で終了。
import math
N = int(input())
sq_N = int(math.sqrt(N))
i = 0
while True:
    if N% (sq_N+i) ==0:
        A = sq_N+i
        B = int(N/A)
        break;
    else:
        i = i+1
print(A-1+B-1)
    
    

### FIXED CODE ###

#C問題
#考え方：平方根に近いところを探す。
#平方根を切り上げた値からスタート。割り切れた時点で終了。
#TLEになった。原因として考えられるのは何か？ものすごい大きな数の時にうまくいかない？
#素数の時に厳しい。
import math
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
import numpy as np


def getNearestValue(list, num):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]

N = int(input())
lis_1 = make_divisors(N)
A = getNearestValue(lis_1,math.sqrt(N))
B = int(N/A)

print(A+B-2)
### BUGGY CODE ###

n,s = map( int, input().split() )

count = 0
for i in range(n+1):
    if i == s:
        count += 1
        break
    for j in range(n+1):
        if i+j == s:
            count += 1
            break
        for k in range(n+1):
            if i+j+k == s:
                count += 1
                break


print(count)    


### FIXED CODE ###

n,s = map( int, input().split() )

count = 0
for i in range(n+1):
    for j in range(n+1):
        if s-i-j <= n and s-i-j >= 0:
            count += 1


print(count)
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp = [float("inf")]*N
dp[0]=0
for i in range(N-1):
    for j in range(1,min(K+1,N-i)):
        dp[i+j]=min(dp[i+j],dp[i]+abs(H[i+j]-H[i]))
print(dp[-1])

### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp = [float("inf")]*N
dp[0]=0
for i in range(N-1):
    for j in range(1,min(K+1,N-i)):
        dp[i+j]=min(dp[i+j],dp[i]+abs(H[i+j]-H[i]))
print(dp[-1])
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
def main():
    H,W = map(int,input().split())
    S = [list(input().rstrip()) for _ in range(H)]
    L = np.zeros((H,W))
    R = np.zeros((H,W))
    U = np.zeros((H,W))
    D = np.zeros((H,W))
    for i in range(H):
        for j in range(W):
            if j == 0:
                if S[i][j] == "#":
                    L[i,j] = -1
                continue
            if S[i][j] == ".":
                L[i,j] = L[i,j-1]+1
            else:
                L[i,j] = -1
        for j in reversed(range(W)):
            if j == W-1:
                if S[i][j] == "#":
                    R[i,j] = -1
                continue
            if S[i][j] == ".":
                R[i,j] = R[i,j+1]+1
            else:
                R[i,j] = -1
    for j in range(W):
        for i in range(H):
            if i == 0:
                if S[i][j] == "#":
                    U[i,j] = -1
                continue
            if S[i][j] == ".":
                U[i,j] = U[i-1,j]+1
            else:
                U[i,j] = -1
        for i in reversed(range(H)):
            if i == H-1:
                if S[i][j] == "#":
                    D[i,j] = -1
                continue
            if S[i][j] == ".":
                D[i,j] = D[i+1,j]+1
            else:
                D[i,j] = -1
    su = L+R+U+D
    #print(L,R,U,D,sep="\n")
    print(int(np.amax(su)+1))
if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
def main():
    H,W = map(int,input().split())
    S = np.array([list(input().rstrip()) for _ in range(H)]) == "."
    L = np.zeros((H,W),dtype=int)
    R = np.zeros((H,W),dtype=int)
    U = np.zeros((H,W),dtype=int)
    D = np.zeros((H,W),dtype=int)
    #[-1]はインデックス内(all 0)なのでエラーを吐かない！
    for i in range(H):
        U[i] = (U[i-1]+1)*S[i]
        D[-i-1] = (D[-i]+1)*S[-i-1]  
    for j in range(W):
        L[:,j] = (L[:,j-1]+1)*S[:,j]
        R[:,-j-1] = (R[:,-j]+1)*S[:,-j-1]

    su = L+R+U+D
    #print(L,R,U,D,sep="\n")
    print(np.amax(su)-3)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, Q = map(int, input().split())
S = str(input())
for i in range(Q):
    k =input().split()
    l=int(k[0])
    r=int(k[1])
    slice = S[l-1:r]
    print(slice.count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
wa=[0]*N
p=0
for j in range(1,N):
    if S[j-1]=="A" and S[j]=="C":
        p+=1
        wa[j]=p
    else:
        wa[j]=wa[j-1]
for i in range(Q):
    k =input().split()
    l=int(k[0])
    r=int(k[1])
    print(wa[r-1]-wa[l-1])
### BUGGY CODE ###

n,w = map(int, input().split())
wv = []
for _ in range(n):
    data = list(map(int,input().split()))
    wv.append(data)

def solve(i,j):
    if i>=n:
        return 0

    weight=wv[i][0]
    value =wv[i][1]

    if j<weight: # can't push this item
        val = solve(i+1,j)
    else:# push or not push
        val =  max(solve(i+1,j-weight)+value, solve(i+1,j))

    return val

print(solve(0,w))

### FIXED CODE ###

n,w = map(int, input().split())
wv = []
for _ in range(n):
    data = list(map(int,input().split()))
    wv.append(data)

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

for item in range(n):
    now_w=wv[item][0]
    now_v=wv[item][1]

    for weight in range(w+1):
        ans1=dp[item][weight]
        ans2=-1
        if weight - now_w >= 0:
            ans2=dp[item][weight-now_w]+now_v
        dp[item+1][weight] = max(ans1,ans2)

print(dp[n][w])
### BUGGY CODE ###

def is_symmetric(N, board):
    for i in range(N):
        for j in range(N):
            if board[i][j] != board[j][i]:
                return False
    return True


def generate_board(N, board, a, b):
    new = []
    for i in range(N):
        new.append([None for i in range(N)])

    for i in range(N):
        for j in range(N):
            new[(i + a) % N][(j + b) % N] = board[i][j]

    return new


def solve(N, board):
    ans = 0
    for i in range(2*N - 1):
        if i < N:
            if is_symmetric(N, generate_board(N, board, 0, i)):
                ans += i + 1
        else:
            if is_symmetric(N, generate_board(N, board, 0, i)):
                ans += 2*N - 1 - i
    return ans


N = int(input())
board = []
for i in range(N):
    board.append([j for j in input()])


print(int(solve(N, board)))

### FIXED CODE ###



def is_symmetric(board):
    for i in range(N):
        for j in range(i, N):
            if board(j, i) != board(i, j):
                return False
    return True


def translate(board, a, b):
    def get(i, j):
        return board[(i + a) % N][(j + b) % N]
    
    return get


def solve(board):
    ans = 0
    for a in range(N):
        if is_symmetric(translate(board, a, 0)):
            ans += N - a
    for b in range(N):
        if b == 0:
            continue
        if is_symmetric(translate(board, 0, b)):
            ans += N - b
    return ans


N = int(input())
board = []
for i in range(N):
    board.append(input())


print(solve(board))