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

from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    s = list(input().rstrip())
    grid.append(s)
dxdy = [[0, 1], [1,0], [-1, 0], [0, -1]]
visited = [[0]*w for _ in range(h)]
dist = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if grid[i][j]==".":
            y = i
            x = j
            break

que=deque()
que.append([x,y])
while que:
    v=que.popleft()
    x = v[0]
    y = v[1]
    visited[y][x]=1
    for i in dxdy:
        dx = i[0]
        dy = i[1]
        if((x+dx<w and y+dy<h) and ((x+dx)>-1)and(y+dy)>-1) and not visited[y+dy][x+dx]:
            dist[y+dy][x+dx]=dist[y][x]+1
            que.append([x+dx, y+dy])
max_dist = [0, []]
def max1(a,b):
    if a[0]>b[0]:
        return a
    else:
        return b
for i in range(h):
    for j in range(w):
        max_dist = max1(max_dist, [dist[i][j], i,j])
visited = [[0]*w for _ in range(h)]
dist = [[0]*w for _ in range(h)]

que2 = deque()
que2.append([max_dist[2], max_dist[1]])
while que2:
    v=que2.popleft()
    x = v[0]
    y = v[1]
    visited[y][x]=1
    for i in dxdy:
        dx = i[0]
        dy = i[1]
        if((x+dx<w and y+dy<h) and ((x+dx)>-1)and(y+dy)>-1) and not visited[y+dy][x+dx] and grid[y+dy][x+dx]==".":
            dist[y+dy][x+dx]=dist[y][x]+1
            que2.append([x+dx, y+dy])
for i in range(h):
    for j in range(w):
        max_dist = max1(max_dist, [dist[i][j], i,j])
print(max_dist[0])


### FIXED CODE ###

from collections import deque

h,w = map(int, input().split())
grid = []
for i in range(h):
    s = list(input().rstrip())
    grid.append(s)
dydx = [[0, 1], [1,0], [-1, 0], [0, -1]]

def find_longest_path(xy):
    visited = [[0]*w for _ in range(h)]
    dist = [[0]*w for _ in range(h)]
    visited[xy[1]][xy[0]]=1
    que = deque()
    que.append(xy)
    while que:
        v = que.popleft()
        x,y = v[0],v[1]
        for i in dydx:
            dx = i[0]
            dy = i[1]
            if ((x+dx<w and y+dy<h) and ((x+dx)>-1)and(y+dy)>-1) and not visited[y+dy][x+dx]:
                if(grid[y+dy][x+dx]=="."):
                    que.append([x+dx, y+dy])
                    visited[y+dy][x+dx]=1
                    dist[y+dy][x+dx]=dist[y][x]+1
                    u,k = x+dx, y+dy
                    r = dist[y+dy][x+dx]

    return r

def main():
    k=0
    for i in range(h):
        for j in range(w):
            if grid[i][j]==".":
                k = max(k, find_longest_path([j,i]))
    print(k)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
from collections import deque
readline = sys.stdin.readline

N = int(readline())
P = list(map(int, readline().split()))

geta = N+2
G = [0]*(geta*geta)

for v in range(-1-(-N//2), -1, -1):
    l = v+1
    r = N-v
    for i in range(geta):
        G[i*geta+l] = v
        G[i*geta+r] = v
        G[l*geta+i] = v
        G[r*geta+i] = v

for i in range(geta):
    G[i*geta] = -1
    G[i*geta + geta-1] = -1
    G[i] = -1
    G[geta*(geta-1)+i] = -1

Pn = []

for p in P:
    a, b = divmod(p-1, N)
    Pn.append((1+a)*geta+1+b)

DIREC = [1, -1, geta, -geta]
ans = 0
used = set()
for p in Pn:
    ans += G[p]
    Q = deque([p])
    res = G[p]
    for d in DIREC:
        res = min(res, G[p+d])
    if G[p] != res:
        G[p] = res
        while Q:
            vn = Q.pop()
            for d in DIREC:
                vf = vn + d
                if vf not in used and G[vf] > G[vn] + 1:
                    G[vf] = G[vn] + 1
                    Q.appendleft(vf)
                elif vf in used and G[vf] > G[vn]:
                    G[vf] = G[vn]
                    Q.appendleft(vf)
                    
    used.add(p)
print(ans)

### FIXED CODE ###

import sys
from collections import deque
readline = sys.stdin.readline

N = int(readline())
P = list(map(int, readline().split()))

geta = N+2
G = [0]*(geta*geta)

for v in range(-1-(-N//2), -1, -1):
    l = v+1
    r = N-v
    for i in range(geta):
        G[i*geta+l] = v
        G[i*geta+r] = v
        G[l*geta+i] = v
        G[r*geta+i] = v

for i in range(geta):
    G[i*geta] = -1
    G[i*geta + geta-1] = -1
    G[i] = -1
    G[geta*(geta-1)+i] = -1

Pn = []

for p in P:
    a, b = divmod(p-1, N)
    Pn.append((1+a)*geta+1+b)

DIREC = (1, -1, geta, -geta)
ans = 0
used = [False]*(geta*geta)
for p in Pn:
    ans += G[p]
    res = G[p]
    for d in DIREC:
        res = min(res, G[p+d])
    if G[p] != res:
        G[p] = res
        Q = [p]
        while Q:
            vn = Q.pop()
            for d in DIREC:
                vf = vn + d
                if not used[vf]:
                    if G[vf] > G[vn] + 1:
                        G[vf] = G[vn] + 1
                        Q.append(vf)
                else:
                    if G[vf] > G[vn]:
                        G[vf] = G[vn]
                        Q.append(vf)
                    
    used[p] = True
print(ans)
### BUGGY CODE ###

s = input()
K = int(input())

ss = sorted(list(set(s)))

def f(s, c):
    indexes = []
    # r = []
    st = set()
    for i, si in enumerate(s):
        if si == c:
            indexes.append(i)
    for i in indexes:
        for j in range(i, len(s)):
            x = s[i:j+1]
            # r.append(x)
            st.add(x)
    # return r
    return st

# print(f('abcab', 'a'))

st = set()
for ssi in ss:
    x =  f(s, ssi)
    st = st.union(x)
    if len(st) > 5:
        break

x = sorted(list(st))
ans = x[K-1]
print(ans)

### FIXED CODE ###

s = input()
K = int(input())

ss = sorted(list(set(s)))

def f(s, c):
    indexes = []
    st = set()
    for i, si in enumerate(s):
        if si == c:
            indexes.append(i)
    for i in indexes:
        cnt = 0
        for j in range(i, len(s)):
            x = s[i:j+1]
            st.add(x)
            cnt += 1
            # print('cnt', cnt)
            if cnt > 5:
                break
    return sorted(list(st))

r = []
for ssi in ss:
    x =  f(s, ssi)
    r += x
    if len(r) > 5:
        break


ans = r[K-1]
# print(r)
print(ans)
### BUGGY CODE ###

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

s = 1
for i in range(k):
    s *= a[i]
last = s
for i in range(k, n):
    s = s * a[i] // a[i-k]
    if last >= s:
        print('No')
    else:
        print('Yes')
    last = s

### FIXED CODE ###

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

for i in range(k, n):
    if a[i] <= a[i-k]:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

n, s = int(input()), str(input())

num1, num2, num3 = set([]), set([]), set([])
for i in range(n):
    if s[i] in num1:
        continue
    num1.add(s[i])
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            num3.add(s[i] + s[j] + s[k])
print(len(num3))


### FIXED CODE ###

n, s = int(input()), str(input())

num1, num2, num3 = set([]), set([]), set([])
for i in range(n):
    if s[i] in num1:
        continue
    num1.add(s[i])
    for j in range(i + 1, n):
        tmp2 = s[i] + s[j]
        if tmp2 in num2:
            continue
        num2.add(tmp2)
        for k in range(j + 1, n):
            tmp3 = tmp2 + s[k]
            if tmp3 in num3:
                continue
            num3.add(tmp3)
print(len(num3))
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
A = [j-i-1 for i,j in enumerate(A)]
top = max(A)
bottom = min(A)
def sad(b):
  ret=0
  for i in A:
    ret += abs(i-b)
  return ret
while top - bottom > 2:
  mid1 = (top + bottom*2)//3
  mid2 = (top*2 + bottom)//3
  if sad(mid1) < sad(mid2):
    top = mid2
  else:
    bottom = mid1
print(min(sad(bottom), sad((bottom+top)//2), sad(top)))


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
A = [j-i-1 for i,j in enumerate(A)]
top = max(A)
bottom = min(A)
def sad(b):
  ret=0
  for i in A:
    ret += abs(i-b)
  return ret
while top - bottom > 2:
  mid1 = (top + bottom*2)//3
  mid2 = (top*2 + bottom)//3
  if sad(mid1) < sad(mid2):
    top = mid2
  else:
    bottom = mid1
print(min(sad(bottom), sad((bottom+top)//2), sad(top)))
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    mod = 10**9 + 7
    b = [0] * 60
    for ai in a:
        for k in range(ai.bit_length()):
            b[k] += ai & 1
            ai //= 2
    c = 0
    for k in range(60):
        c = (c + b[k] * (n - b[k]) * pow(2, k, mod)) % mod
    print(c)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = max(a).bit_length()
    mod = 10**9 + 7
    c = 0
    for kk in range(k):
        h, l = 0, 0
        for ai in a:
            if ai // 2**kk % 2:
                h += 1
            else:
                l += 1
        kc = h * l * pow(2, kk, mod) % mod
        c = (c + kc) % mod
    print(c)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
l = []
r = []
for i in range(Q):
    li, ri = map(int, input().split())
    l += [li]
    r += [ri]

for ind in range(Q):
    substr = S[max(0, l[ind]-1) : min(r[ind], N)]
    print(substr.count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
l = []
r = []
for i in range(Q):
    li, ri = map(int, input().split())
    l += [li]
    r += [ri]

S_tf = [0]*(N+1)
for ind in range(N):
    S_tf[ind + 1] = S_tf[ind] + (1 if S[ind:ind+2] == "AC" else 0)
for ind in range(Q):
    print(S_tf[max(0, r[ind]-1)] - S_tf[min(l[ind]-1, N)])
### BUGGY CODE ###

n = int(input())
re_t = 0
re_a = 0
for i in range(n):
    t, a = map(int, input().split(' '))
    n = 1
    while n*t < re_t or n*a < re_a:
        n += 1
    re_t = n * t
    re_a = n * a
print(re_t + re_a)

### FIXED CODE ###

import math
n = int(input())
a,b = 1,1
for i in range(n):
    x,y = map(int, input().split(' '))
    tmp = max(-(-a//x), -(-b//y))
    a = x * tmp
    b = y * tmp
print(a+b)
### BUGGY CODE ###

import sys
from collections import deque


def solve(n, m, links):
    if m % 2 == 1:
        print(-1)
        return

    topological = [{} for _ in range(n)]
    parents = [-1] * n
    q = deque([0])
    while q:
        v = q.popleft()
        for u in links[v]:
            if v in topological[u]:
                continue
            topological[v][u] = 0
            if parents[u] == -1:
                parents[u] = v
            q.append(u)

    fixed = [len(l) % 2 == 0 for l in topological]

    def reverse_links(s, t):
        v = s
        while v != t:
            p = parents[v]
            topological[p][v] ^= 1
            v = p

    tmp_trace = set()
    tmp_pair = -1
    for v in range(n):
        if fixed[v]:
            continue
        if tmp_pair == -1:
            u = v
            while u != -1:
                tmp_trace.add(u)
                u = parents[u]
            tmp_pair = v
        else:
            u = v
            while u != -1:
                if u in tmp_trace:
                    reverse_links(v, u)
                    reverse_links(tmp_pair, u)
                    break
                u = parents[u]
            else:
                print(tmp_pair, v)
                print(tmp_trace)
                raise AssertionError
            fixed[v] = fixed[tmp_pair] = True
            tmp_trace.clear()
            tmp_pair = -1

        # print(v, tmp_trace, tmp_pair)

    assert tmp_pair == -1

    ans = []
    for v in range(n):
        for u, d in topological[v].items():
            if d == 0:
                ans.append('{} {}'.format(v + 1, u + 1))
            else:
                ans.append('{} {}'.format(u + 1, v + 1))
    print('\n'.join(ans))


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

links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

solve(n, m, links)


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 5)


def solve(n, m, links):
    if m % 2 == 1:
        print(-1)
        return

    tree = [set() for _ in range(n)]
    parents = [-1] * n
    q = deque([0])
    while q:
        v = q.popleft()
        for u in links[v]:
            if parents[u] == -1:
                tree[v].add(u)
                parents[u] = v
                q.append(u)
            links[u].remove(v)

    parities = [len(l) % 2 for l in links]

    # print(links)
    # print(tree)
    # print(parents)
    # print(parities)

    def dfs(v):
        b = parities[v]
        for u in tree[v]:
            c = dfs(u)
            b ^= c
        if b:
            p = parents[v]
            links[p].remove(v)
            links[v].add(p)
        return b

    dfs(0)

    ans = ['{} {}'.format(v + 1, u + 1) for v in range(n) for u in links[v]]
    print('\n'.join(ans))


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

links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

solve(n, m, links)
### BUGGY CODE ###

import numpy as np

def wa(n):
    if n<=1:
        return 1
    else:
        return wa(n-1)+n

if __name__ == "__main__":
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    b=[]
    for i in a:
        b.append((i+1)/2)
    max=0
    for i in range(len(b)-k+1):
        sum=0
        for j in range(i,i+k):
            sum+=b[j]
        if max<=sum:
            max=sum
    print(max)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
smax=0
for i in range(k-1,n):
    if i==k-1:
        sumnow=sum(a[:i+1])
    else:
        sumnow+=a[i]-a[i-k]
    smax=max(smax,sumnow)
print((smax+k)/2)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC110 D

import math
from collections import Counter
N,M = map(int,input().split())
mod = 10**9 + 7

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

def fast(x,n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return fast(x**2 % mod,n//2) % mod
    elif n % 2:
        return x*fast(x**2 % mod,n//2) % mod

cnt = list(Counter(factorize(M)).items())
ans = 1
for i,j in cnt:
    ans *= math.factorial(j+N-1)
    ans %= mod
    ans *= fast(math.factorial(j),mod-2)
    ans %= mod
    ans *= fast(math.factorial(N-1),mod-2)
    ans %= mod
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC110 D

import math
from collections import Counter
N,M = map(int,input().split())
mod = 10**9 + 7

def factorize(n):
    b = 2
    fct = []
    while b**2 <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b += 1
    if n > 1:
        fct.append(n)
    return fct

def fast(x,n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return fast(x**2 % mod,n//2) % mod
    elif n % 2:
        return x*fast(x**2 % mod,n//2) % mod
fact = [0]*(200001)
fact[0] = 1
for i in range(200000):
    fact[i+1] = fact[i]*(i+1)
    fact[i+1] %= mod

cnt = list(Counter(factorize(M)).items())
ans = 1
for i,j in cnt:
    ans *= fact[j+N-1]
    ans %= mod
    ans *= fast(fact[j],mod-2)
    ans %= mod
    ans *= fast(fact[N-1],mod-2)
    ans %= mod
print(ans)
### BUGGY CODE ###

import sys

s = sys.stdin.readline()
t = sys.stdin.readline()

s_len = len(s) - 1
t_len = len(t) - 1
dp = [[[0, ''] for x in range(t_len)] for y in range(s_len)]

for i in range(t_len):
    if s[0] == t[i]:
        dp[0][i][1] = s[0]
        dp[0][i][0] = 1
    else:
        dp[0][i][1] = dp[0][i-1][1] if i != 0 else ''
        dp[0][i][0] = dp[0][i-1][0] if i != 0 else 0


for i in range(s_len):
    if s[i] == t[0]:
        dp[i][0][1] = t[0]
        dp[i][0][0] = 1
    else:
        dp[i][0][1] = dp[i-1][0][1] if i != 0 else ''
        dp[i][0][0] = dp[i-1][0][0] if i != 0 else 0

for i in range(1, s_len):
    for j in range(1, t_len):
        if t[j] == s[i]:
            dp[i][j][1] = dp[i-1][j-1][1] + t[j]
            dp[i][j][0] = dp[i-1][j-1][0] + 1
        else:
            dp[i][j][1] = dp[i-1][j][1] if dp[i-1][j][0] > dp[i][j-1][0] else dp[i][j-1][1]
            dp[i][j][0] = dp[i-1][j][0] if dp[i-1][j][0] > dp[i][j-1][0] else dp[i][j-1][0]

print(dp[s_len-1][t_len-1][1])


### FIXED CODE ###

import sys

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

s_len = len(s)
t_len = len(t)
dp = [[0 for x in range(t_len + 1)] for y in range(s_len + 1)]


for i in range(1, s_len+1):
    for j in range(1, t_len+1):
        if t[j-1] == s[i-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

ans = ''
i = s_len
j = t_len

while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans += s[i - 1]
        i -= 1
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def dfs(v):
    seen[v] = 1
    ans[v] += counter[v]

    for next_v in graph[v]:
        if seen[next_v]: continue
        ans[next_v] += ans[v]
        dfs(next_v)

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

graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

counter = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x

seen = [0] * n
ans = [0] * n
dfs(0)

print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from queue import Queue

n, q = map(int, input().split())
nodes = [[] for _ in range(n)]  # 隣接ノード
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    nodes[a].append(b)
    nodes[b].append(a)

counts = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    counts[p-1] += x

ans = [0] * n
ans[0] = counts[0]
done = [0] * n
queue = Queue()
queue.put(0)
while True:
    node = queue.get()
    done[node] = 1
    next_nodes = nodes[node]
    for next_node in next_nodes:
        if not done[next_node]:
            queue.put(next_node)
            ans[next_node] = ans[node] + counts[next_node]
    if queue.empty():
        break

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

K = int(input())
import fractions
def multi_gcd(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = fractions.gcd(ans, a[i])
    #print(ans)
    return ans
sum_ = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            sum_ += multi_gcd([i, j, k])
print(sum_)

### FIXED CODE ###

import math
k = int(input())
ans = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        gcd1 = math.gcd(i, j)
        for l in range(1, k + 1):
            gcd2 = math.gcd(gcd1, l)
            ans += gcd2
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split(" "))
stores = []
for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    stock = 0
    unuse_idx = -1
    tg_idx = -1
    for idx, s in enumerate(stores):
        if stock <= M:
            stock += s[1]
        else:
            unuse_idx = idx
        if s[0] > Ai:
            if tg_idx == -1:
	            tg_idx = idx
    if unuse_idx != -1:
        stores = stores[:unuse_idx]
    if tg_idx != -1:
        stores.insert(tg_idx, (Ai, Bi))
    else:
        stores.append((Ai, Bi))

price = 0
for store in stores:
    if M <= store[1]:
        price += store[0] * M
        break
    else:
        price += store[0] * store[1]
        M -= store[1]
print(price)

### FIXED CODE ###

N, M = map(int, input().split(" "))
stores = []

for i in range(N):
    Ai, Bi = map(int, input().split(" "))
    stores.append((Ai, Bi))    

price = 0
for a, b in sorted(stores, key=lambda x: x[0]):
    if M <= b:
        price += a * M
        break
    else:
        price += a * b
        M -= b
print(price)
### BUGGY CODE ###

N = int(input())
S = input()
r = 999999999
for n in range(N):
    result = S[:n].count('W') + S[n + 1:].count('E')
    if result < r:
        r = result
print(r)

### FIXED CODE ###

N = int(input())
S = input()

i = S[1:].count('E')
ans = [i]

for n in range(N):
    if n == 0:
        continue

    if S[n] == 'E':
        i -= 1

    if S[n - 1] == 'W':
        i += 1
    ans.append(i)

print(min(ans))
### 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(1,n):
  for j in range(max(0,i-k),i):
    dp[i] = min(dp[i],dp[j]+abs(h[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(1,n):
  for j in range(max(0,i-k),i):
    dp[i] = min(dp[i],dp[j]+abs(h[j]-h[i]))
print(dp[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 61) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)

        for i, char in enumerate(string):
            self.hash[i + 1] = (self.hash[i] * self.BASE + ord(char)) % self.MOD
            self.pow[i + 1] = (self.pow[i] * self.BASE) % self.MOD

    def get_hash(self, l, r):
        """string[l:r]のハッシュ値を返す。O(1)"""
        res = (self.hash[r] - self.hash[l] * self.pow[r - l]) % self.MOD
        return res


n = int(input())
s = [input()[:-1] for i in range(n)]


s.sort(key=len)
str_set = set()
cnt = 0

for string in s:
    string = string[::-1]
    n = len(string)
    rh = RollingHash(string)

    for r in range(1, n + 1):
        if rh.get_hash(0, r) in str_set:
            cnt += 1

    set_char = set()
    for r in range(1, n + 1)[::-1]:
        set_char.add(string[r - 1])
        for char in set_char:
            if char == string[r - 1]:
                continue
            h = (rh.hash[r - 1] * rh.BASE + ord(char)) % rh.MOD
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 45) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)

        for i, char in enumerate(string):
            self.hash[i + 1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i + 1] = (self.pow[i] * self.BASE) % self.MOD

    def get_hash(self, l, r):
        """string[l:r]のハッシュ値を返す。O(1)"""
        res = (self.hash[r] - self.hash[l] * self.pow[r - l]) % self.MOD
        return res


n = int(input())
s = [input()[:-1] for i in range(n)]


s.sort(key=len)
str_set = set()
cnt = 0

for string in s:
    string = string[::-1]
    n = len(string)
    rh = RollingHash(string)

    for r in range(1, n + 1):
        if rh.get_hash(0, r) in str_set:
            cnt += 1

    set_char = set()
    for r in range(1, n + 1)[::-1]:
        set_char.add(string[r - 1])
        for char in set_char:
            if char == string[r - 1]:
                continue
            h = (rh.hash[r - 1] + ord(char)) * rh.BASE % rh.MOD
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)
### BUGGY CODE ###

n, w = map(int, input().split())
we,v = [0] * n, [0] * n
for i in range(n):
    we[i], v[i] = map(int, input().split())

dp = [[0] * (w + 1) for i in range(n + 1)]
for i in range(n):
    for j in range(w + 1):
        if j - we[i] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - we[i]] + v[i])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    
print(dp[n][w])

### FIXED CODE ###

n, ww = map(int, input().split())
w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (100100) for i in range(110)]

for i in range(n):
    for j in range(ww + 1):
        if j - w[i] >= 0:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])

        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print(dp[n][ww])