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

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1
mod = 998244353
for i in range(n):
    for j in range(s+1):
        dp[i+1][j] = dp[i][j]*2
        if a[i]<=j: dp[i+1][j] += dp[i][j-a[i]]
        dp[i+1][j] %= mod
print(dp[n][s])

### FIXED CODE ###

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1
mod = 998244353
for i in range(n):
    for j in range(s+1):
        dp[i+1][j] = dp[i][j]*2%mod
        if a[i]<=j: dp[i+1][j] = (dp[i+1][j]+dp[i][j-a[i]])%mod
        dp[i+1][j] %= mod
print(dp[n][s])
### BUGGY CODE ###

import queue
height,width=map(int,input().split())

graph=[]
for _ in range(height):
    s_row = input()
    row = []
    for s in s_row:
        row.append(s)
    graph.append(row)

diff=[[0,-1],[0,1],[-1,0],[1,0]]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = []
        for _ in range(height):
            route.append([-1]*width)

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            now = q.get()

            route[now[1]][now[0]] = now[2]

            for dx,dy in diff:
                next_w = now[0]+dx
                next_h = now[1]+dy
                if   width<=next_w \
                  or height<=next_h \
                  or next_w < 0 \
                  or next_h < 0 \
                  or graph[next_h][next_w]=='#' \
                  or route[next_h][next_w]>-1:
                    continue
                q.put([next_w, next_h, now[2]+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))

### FIXED CODE ###

import queue
height,width=map(int,input().split())

graph=[input() for _ in range(height)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = [[-1]*width for _ in range(height)]
        route[h][w] = 0

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()

            for dx,dy in zip(dxs, dys):
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='#' \
                  or route[y][x]!=-1:
                    continue
                route[y][x] = nn + 1
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
m=max(l)

prime=[True]*(m+1)
prime[0]=False
prime[1]=False
d=[0]*(m+1)
for i in range(2,int(m**0.5)+1):
  if prime[i]:
    for j in range(i*2,m+1,i):
      prime[j]=False
      d[j]=i
s=[i for i in range(m+1) if prime[i]]
for ss in s:
  d[ss]=ss

div=[[] for _ in range(n)]
for i in range(n):
  ll=l[i]
  while ll>1:
    div[i].append(d[ll])
    ll//=d[ll]

cnt=[]
for i in range(n):
  div[i]=set(div[i])
  div[i]=list(div[i])
  cnt+=div[i]

if len(cnt)==len(set(cnt)):
  print('pairwise coprime')
  exit()

from math import gcd
g=gcd(l[0],l[1])
for i in range(2,n):
  g=gcd(g,l[i])
if g==1:
  print('setwise coprime')
  exit()
print('not coprime')

### FIXED CODE ###

n=int(input())
import copy
a= [int(x) for x in input().split()]
MAX_A = 10 ** 6 + 1
histogram = [0] * MAX_A
for x in a:
  histogram[int(x)] += 1
for divider in range(2, MAX_A):
  count = 0
  for counted in histogram[divider::divider]:
    count += counted
  if count > 1:
    break
else:
  print('pairwise coprime')
  exit()
from math import gcd
g=gcd(a[0],a[1])
if n==2:
  print('setwise coprime' if g==1 else 'not coprime')
  exit()
for i in range(2,n):
  g=gcd(g,a[i])
if g==1:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

N, A, B = input().split()
N = int(N)
A = int(A)
B = int(B)

L = []
i = 0
k = 0
j = 0

for k in range(10**100):
    for i in range(A):
        L.append('b')
        if len(L) >= N:
            L = L[0:N]
            print(L.count('b'))
            exit()
    
    for j in range(B):
        L.append('r')
        if len(L) >= N:
            L = L[0:N]
            print(L.count('b'))
            exit()

### FIXED CODE ###

N, A, B = map(int , input().split())
 
L = []
i = 0
k = 0
j = 0
P = N // (A + B)
Q = N % (A + B)

if A > Q:
    print((P * A) + Q)
else:
    print((P * A) + A)
### BUGGY CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
N, M, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(K)]

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

uf = UnionFind(N+1)
friends = [[0]*(N+1) for _ in range(N+1)]
blocks = [[0]*(N+1) for _ in range(N+1)]
ans = [0]*(N+1)
roots = defaultdict(int)
ad = [0]*(N+1)
for a, b in ab:
  uf.Unite(a, b)
  friends[a][b] = 1
  friends[b][a] = 1
  ad[a] += 1
  ad[b] += 1

for i in range(1, N+1):
  roots[uf.Find_Root(i)] += 1

for c, d in cd:
  if uf.isSameGroup(c, d):
    ad[c] += 1
    ad[d] += 1

for i in range(1, N+1):
  ans[i] = roots[uf.Find_Root(i)]

for i in range(1, N+1):
  print(ans[i]-ad[i]-1, end=" ")

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

uf = UnionFind(N+1)
roots = {i:0 for i in range(1, N+1)}
each_root = [0]*(N+1)
ad = [0]*(N+1)

for _ in range(M):
  a, b = map(int, input().split())
  uf.Unite(a, b)
  ad[a] += 1
  ad[b] += 1

for i in range(1, N+1):
  r = uf.Find_Root(i)
  roots[r] += 1
  each_root[i] = r

for _ in range(K):
  c, d = map(int, input().split())
  if each_root[c] == each_root[d]:
    ad[c] += 1
    ad[d] += 1

for i in range(1, N+1):
  print(roots[each_root[i]]-ad[i]-1, end=" ")
### BUGGY CODE ###

N=input()
P=list(map(int,input().split()))
t=0
while len(P)>0:
    A=P[0]
    P=[i for i in P if i<A]
    t=t+1
print(t)

### FIXED CODE ###

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

ans = 0
n_min = 0
for i in range(0,n):
    if i == 0:
        ans += 1
        n_min = p[i]
        continue
    if p[i] <= n_min:
        ans += 1
        n_min = p[i]
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
B = [[] for _ in range(m+1)]
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m: B[a] += [b]
C = []
s = 0
for i in range(m+1):
    C += B[i]
    C = sorted(C, reverse = True)
    if C: s += C.pop(0)
print(s)

### FIXED CODE ###

from heapq import heappush, heappop
n, m = map(int, input().split())
B = [[] for _ in range(m+1)]
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m: B[a] += [-b]
C = []
s = 0
for i in range(m+1):
    for b in B[i]: heappush(C, b)
    if C: s += heappop(C)
print(-s)
### BUGGY CODE ###

n = int(input())
nums = list(map(int, input().split(" ")))
before = []
ans = 0
for n in nums:
    nextNums = []
    if n == 0:
        ans += 1
    nextNums.append(n)
    for bNum in before:
        if bNum + n == 0:
            ans += 1
        nextNums.append(bNum + n)
    before = nextNums
print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split(" ")))
S = [0, ]
now = 0
for n in A:
    now += n
    S.append(now)
Scounter = Counter(S)
ans = 0
for c, n in Scounter.most_common():
    if n >= 2:
        ans += n*(n-1)//2
    else:
        break
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 逆から、人1が多かったらその時点で駄目、人0が人1の数を覆い尽くす必要がある
T = ir()

def solve():
    N = ir()
    A = lr()
    S = sr()
    dp = [set()] * (N+1)
    dp[N] = {0}
    for i in range(N-1, -1, -1):
        if S[i] == '0':
            dp[i] = dp[i+1].copy()
            for element in dp[i+1]:
                dp[i].add(element ^ A[i])
        elif S[i] == '1':
            if A[i] not in dp[i+1]:
                return 1
            else:
                dp[i] = dp[i+1].copy()
    return 0
    
for _ in range(T):
    print(solve())

### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 逆から, zero_cardsに数を貯めて行き、bitで0に出来るか
T = ir()
for _ in range(T):
    N = ir()
    A = lr()
    S = sr()
    zero_cards = []
    for a, person in zip(A[::-1], S[::-1]):
        for z in zero_cards:
            a = min(a, a^z)
        if a:
            if person == '1':
                print(1)
                break
            zero_cards.append(a)
    else:
        print(0)
### BUGGY CODE ###

import math
n = int(input())
lst = list(map(int, input().split()))
ans = 0
a,b = 0,0
lst2=[0]
for i in range(n):
    lst2.append(sum(lst[:i+1]))

temp = []
for i in range(n):
    if lst2.count(i) > 1 and i not in temp:
        temp.append(i)
        ans += lst2.count(i)*(lst2.count(i)-1)//2
print(ans)


"""
6
1 3 -4 2 2 -2


7
1 -1 1 -1 1 -1 1

5
1 -2 3 -4 5


0 0 0 0 0
"""

### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
ans = 0
a,b = 0,0
lst2=[0]
d = {0:1}
for i in range(n):
    s = lst2[-1]+lst[i]
    lst2.append(s)
    if s not in d:
        d[s] = 1
    else:
        d[s] += 1

temp = set()

for i in d:
    l = d[i]
    if l > 1 and i not in temp:
        temp.add(i)
        ans += l*(l-1)//2
print(ans)


"""
6
1 3 -4 2 2 -2


7
1 -1 1 -1 1 -1 1

5
1 -2 3 -4 5


0 0 0 0 0
"""
### BUGGY CODE ###


n = int(input())
ans = 1
mod = 10**9 + 7

for i in range(1,n+1):
    ans *= i

print(ans % mod)


### FIXED CODE ###


n = int(input())
ans = 1

for i in range(1,n+1):
    ans *= i
    ans = ans % (10**9 + 7)

print(ans)
### BUGGY CODE ###

import numpy as np
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
W = H + max(A for (A, B) in AB)
dp = np.full(W+1, INF, dtype = np.int64)
dp[0] = 0
for i, (A, B) in enumerate(AB):
    for j in range(A, W+1):
        dp[j] = np.minimum(dp[j], dp[j-A] + B)
print(np.min(dp[H:]))

### FIXED CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])
### BUGGY CODE ###

from bisect import bisect_left
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + sorted([int(input()) for _ in range(A)]) + [BIG*2]
T = [-BIG] + sorted([int(input()) for _ in range(B)]) + [BIG*2]
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_left(S, x)
  shrine_l = S[shrine_b-1]
  shrine_r = S[shrine_b]
  dsl = x-shrine_l
  dsr = shrine_r-x

  temple_b = bisect_left(T, x)
  temple_l = T[temple_b-1]
  temple_r = T[temple_b]
  dtl = x-temple_l
  dtr = temple_r-x

  print(min(
    dsl if shrine_l < temple_l else dtl,
    dsr if shrine_r > temple_r else dtr,
    dsl * 2 + dtr,
    dsl + dtr * 2,
    dsr * 2 + dtl,
    dsr + dtl * 2
  ))

### FIXED CODE ###

from bisect import bisect_right
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + [int(input()) for _ in range(A)] + [BIG*2]
T = [-BIG] + [int(input()) for _ in range(B)] + [BIG*2]
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_right(S, x)
  dsl = x-S[shrine_b-1]
  dsr = S[shrine_b]-x
  temple_b = bisect_right(T, x)
  dtl = x-T[temple_b-1]
  dtr = T[temple_b]-x

  print(min(
    dsl if dsl > dtl else dtl,
    dsr if dsr > dtr else dtr,
    dsl * 2 + dtr,
    dsl + dtr * 2,
    dsr * 2 + dtl,
    dsr + dtl * 2
  ))
### BUGGY CODE ###


import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

class BIT:
    def __init__(self, n=0):
        self.n = n
        self.d = [0] * (n+1)
    
    def add(self, i, x=1):
        i = int(i+1) # index begin 1
        while i <= self.n:
            self.d[i] += x
            i += i&-i # add LSB
    
    def sum(self, i=None):
        x = 0
        i = int( i+1 if not (i is None) else self.n )
        while i > 0:
            x += self.d[i]
            i -= i&-i # sub LSB
        return x

n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
dprint("n, q =", n, q)
dprint("c =", c)

# check colors pair index (s,t)
st = [0] * (n+1)
col_last = [0] * (n+1)
for i in range(n):
    t = i + 1
    col = c[i]
    s = col_last[col]
    if s > 0:
        st[s] = t
    col_last[col] = t
dprint("st =", st)

# input querys (l,r)
lr = [None] * n
qs = list()
sorted_qs = list()
for i in range(q):
    l, r = list(map(int, input().split()))
    qs.append((i,l,r)) 
sorted_qs = sorted(qs, key=lambda q: q[1], reverse=True)
dprint("qs =", qs)
dprint("sorted_qs =", sorted_qs)

i_qs = 0
x = n
d = BIT(n+1)
qs_ans = [0] * len(qs)
for i_qs in range(len(sorted_qs)):
    i, l, r = sorted_qs[i_qs]
    dprint("i, l, r", i, l, r)
    while (x >= l):
        if st[x] > 0:
            d.add(st[x])
            dprint("add x(s), t =", x, st[x])
        x -= 1
    qs_ans[i] = (r-l+1)-d.sum(r)

for ans in qs_ans:
    print(ans)


### FIXED CODE ###


import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

class BIT:
    def __init__(self, n=0):
        self.n = n
        self.d = [0] * (n+1)
    
    def add(self, i, x=1):
        i = int(i+1) # index begin 1
        while i <= self.n:
            self.d[i] += x
            i += i&-i # add LSB
    
    def sum(self, i=None):
        x = 0
        i = int( i+1 if not (i is None) else self.n )
        while i > 0:
            x += self.d[i]
            i -= i&-i # sub LSB
        return x

n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
dprint("n, q =", n, q)
dprint("c =", c)

# check colors pair index (s,t)
st = [0] * (n+1)
col_last = [0] * (n+1)
for i in range(n):
    t = i + 1
    col = c[i]
    s = col_last[col]
    if s > 0:
        st[s] = t
    col_last[col] = t
dprint("st =", st)

# input querys (l,r)
lr = [None] * n
qs = list()
sorted_qs = list()
for i in range(q):
    l, r = list(map(int, input().split()))
    qs.append((i,l,r)) 
sorted_qs = sorted(qs, key=lambda q: q[1], reverse=True)
dprint("qs =", qs)
dprint("sorted_qs =", sorted_qs)

i_qs = 0
x = n
d = BIT(n+1)
qs_ans = [0] * len(qs)
for i_qs in range(len(sorted_qs)):
    i, l, r = sorted_qs[i_qs]
    dprint("i, l, r", i, l, r)
    while (x >= l):
        if st[x] > 0:
            d.add(st[x])
            dprint("add x(s), t =", x, st[x])
        x -= 1
    qs_ans[i] = (r-l+1)-d.sum(r)

for ans in qs_ans:
    print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
a=list(map(int,input().split()))
grundy=[0]*(K+1)
for j in range(K+1):
    s=set()
    for i in range(N):
        if a[i]<=j:
            s.add(grundy[j-a[i]])
        g=0
        while g in s:g+=1
        grundy[j]=g
if grundy[K]:print("First")
else:print("Second")

### FIXED CODE ###

#入力を受け取る
N,K=map(int,input().split())
a=list(map(int,input().split()))
#DPの配列(少し余裕を持たせる)、Falseで初期化
DP=[False]*(K+10)
for i in range(1,K+1):
    for j in range(N):
        if i-a[j]>=0:
            DP[i] |= ~DP[i-a[j]] # ~は否定の意味(ビット反転)
            #ORなので, 一つでもFalseがあればTrueがはいる
if DP[K]:print("First")
else: print("Second")
### BUGGY CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    k=int(readline())
    #ss=readline().rstrip()
    #yn(1)
    ans=0
    for a in range(1,k+1):
        for b in range(1,k+1):
            for c in range(1,k+1):
                ans+=gcd(a,b,c)
    print(ans)



    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    k=int(readline())
    #ss=readline().rstrip()
    #yn(1)
    ans=0
    for a in range(1,k+1):
        for b in range(1,k+1):
            for c in range(1,k+1):
                ans+=gcd(a,b,c)
    print(ans)



    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------
### BUGGY CODE ###

N = int(input())

A_list = list(map(int, input().split())) # case1 : [7, 6, 8]

def gcd(a, b):
    while b != 0:
        a, b = b, int(a%b)
    return a

ans = 0

for i in range(N):
    left_gcd = 0
    right_gcd = 0

    for j in range(0, i):
        left_gcd = gcd(A_list[j], left_gcd)

    for k in range(i+1, N):
        right_gcd = gcd(A_list[k], right_gcd)

    i_gcd = gcd(left_gcd, right_gcd)

    if ans < i_gcd:
        ans = i_gcd

print(ans)

### FIXED CODE ###

N = int(input())

A_list = list(map(int, input().split())) # case1 : [7, 6, 8]

def gcd(a, b):
    while b != 0:
        a, b = b, int(a%b)
    return a

left_gcd = [0] * (N+1)
right_gcd = [0] * (N+1)
for i in range(N):
    left_gcd[i+1] = gcd(A_list[i], left_gcd[i])
for i in range(N-1, 0, -1):
    right_gcd[i] = gcd(A_list[i], right_gcd[i+1])

ans = 0

for i in range(N):
    i_gcd = gcd(left_gcd[i], right_gcd[i+1])
    if ans < i_gcd:
        ans = i_gcd

print(ans)
### BUGGY CODE ###

import numpy as np 

N, K, Q = map(int, input().split())
A = np.array([K]*N)

for i in range(Q):
  a = int(input())-1
  correct = A[a]
  A = A-1
  A[a] = correct
for ans in A:
  if ans < 1:
    print("No")
  else:
    print("Yes")
  



### FIXED CODE ###

import numpy as np 
from collections import Counter

N, K, Q = map(int, input().split())
A = np.array([K]*N)-Q

correct = Counter([int(input())-1 for _ in range(Q)])
#correct = sorted(correct.;items(), key:lambda x: x[0])

for i in range(N):
  if i in correct.keys():
    A[i] += correct[i]
  print("No" if A[i] < 1 else "Yes")
### BUGGY CODE ###

n,m = map(int,input().split())
a = [input().rstrip() for i in range(n)]
b = list(zip(*a))
for i in range(m):
  b[i] = "".join(b[i])
ans = 0
ct1 = [[0 for k in range(n-j+1)] for j in range(n+1)]
ct2 = [[0 for k in range(n-j+1)] for j in range(n+1)]
for i in range(m-1):
  b1 = b[i]
  b2 = b[i+1]
  for j in range(n+1):
    ct1[j][0] = 0
    ct2[j][0] = 0
    for k in range(n-j):
      ct1[j][k+1] = ct1[j][k]
      ct2[j][k+1] = ct2[j][k]
      if b1[k+j] == b2[k]:
        ct1[j][k+1] += 1
      if b2[k+j] == b1[k]:
        ct2[j][k+1] += 1
  dp = [[10**6 for i in range(n+1)] for j in range(n+1)]
  dp[0][0] = 0
  for i in range(n+1):
    for j in range(n+1):
      if i <= j:
        cost = ct2[j-i][n-j]
      else:
        cost = ct1[i-j][n-i]
      if i < n:
        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+cost)
      if j < n:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+cost)
  ans += dp[-1][-1]
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
a = [input().rstrip() for i in range(n)]
b = list(zip(*a))
for i in range(m):
  b[i] = "".join(b[i])
ans = 0
ct1 = [[0 for k in range(n-j+1)] for j in range(n+1)]
ct2 = [[0 for k in range(n-j+1)] for j in range(n+1)]
dp = [[10**5 for i in range(n+1)] for j in range(n+1)]
for i in range(m-1):
  b1 = b[i]
  b2 = b[i+1]
  for j in range(n+1):
    ct1[j][0] = 0
    ct2[j][0] = 0
    for k in range(n-j):
      ct1[j][k+1] = ct1[j][k]
      ct2[j][k+1] = ct2[j][k]
      if b1[k+j] == b2[k]:
        ct1[j][k+1] += 1
      if b2[k+j] == b1[k]:
        ct2[j][k+1] += 1
  dp[0][0] = 0
  for i in range(n+1):
    if i < n:
      dp[i+1][0] = 10**6
    for j in range(n+1):
      if i == 0 and j < n:
        dp[i][j+1] = 10**6
      if i <= j:
        cost = ct2[j-i][n-j]
      else:
        cost = ct1[i-j][n-i]
      if j < n:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+cost)
      if i < n:
        dp[i+1][j] = dp[i][j]+cost
  ans += dp[-1][-1]
print(ans)
### BUGGY CODE ###

q = int(input())
ans = []
for _ in range(q):
    x = input()
    y = input()
    m = len(x)
    n = len(y)
    c = [0] * (n + 1)
    for i in range(m):
        tmp = x[i]
        c_ = c[:]
        for j in range(n):
            if tmp == y[j]:
                c[j + 1] = c_[j] + 1
            elif c[j + 1] < c[j]:
                c[j + 1] = c[j]
    ans.append(c[-1])

print(*ans, sep="\n")


### FIXED CODE ###

def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [0] * (n + 1)
    for i in range(m):
        tmp = x[i]
        c_ = c[:]
        for j in range(n):
            if tmp == y[j]:
                c[j + 1] = c_[j] + 1
            elif c[j + 1] < c[j]:
                c[j + 1] = c[j]
    return c[-1]


q = int(input())
ans = []
for _ in range(q):
    x = input()
    y = input()
    ans.append(lcs(x, y))

print(*ans, sep="\n")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ca = [0] * (len(a) + 1)
for i in range(n):
    ca[i + 1] = ca[i] + a[i]

ans = 0
for i in range(n):
    # print(a[i], ca[i], ca, ca[i + 1:], ca[i + 1:].count(ca[i]))
    ans += ca[i + 1:].count(ca[i])
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ca = [0] * (len(a) + 1)
for i in range(n):
    ca[i + 1] = ca[i] + a[i]


# TLE
# ans = 0
# for i in range(n):
#     # print(a[i], ca[i], ca, ca[i + 1:], ca[i + 1:].count(ca[i]))
#     ans += ca[i + 1:].count(ca[i])
# print(ans)

from collections import Counter

ans = 0
cac = Counter(ca)
# print(cac)
# ca.sort()
for v, c in cac.items():
    if c >= 2:
        ans += c * (c - 1) // 2
print(ans)