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

import copy
import numpy as np

N = int(input())
A = np.asarray([[int(Aij) for Aij in input().split()] for _ in range(N)])

def warshall_floyd(D):
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                D[j][k] = min(D[j][k], D[j][i] + D[i][k])
    return D

A2 = warshall_floyd(copy.deepcopy(A))

if np.any(A != A2):
    print(-1)
else:
    d = 0
    A += np.diag([2*10**9] * N)
    for i in range(N):
        for j in range(i + 1, N):
            if np.min(A[i] + A[j]) != A[i, j]:
                d += A[i, j]
    print(d)


### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N = int(input())
A = np.asarray([[int(Aij) for Aij in input().split()] for _ in range(N)])

A2 = floyd_warshall(A, directed=False)

if np.any(A != A2):
    print(-1)
else:
    d = 0
    A += np.diag([2*10**9] * N)
    for i in range(N):
        for j in range(i + 1, N):
            if np.min(A[i] + A[j]) != A[i, j]:
                d += A[i, j]
    print(d)
### BUGGY CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()

C_list = [0] * N
for i in range(M):
  [B, C] = list(map(int, input().split(' ')))
  if C_list[0] > C:
    continue
  else:
    for k in range(B):
      if C_list[k] < C:
        C_list[k] = C
      else:
        break
    C_list.sort()
  
C_list.sort()

ans = 0
count = 0
for i in range(N):
  if card_list[-1] > C_list[-1]:
    ans += card_list.pop()
    count += 1
  else:
    ans += C_list.pop()
    count += 1
    
  if C_list == []:
    for k in range(N - count):
      ans += card_list.pop()
    break
      
print(ans) 

### FIXED CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()
compare_list = []

for i in range(M):
  (B, C) = list(map(int, input().split(' ')))
  compare_list.append((C,B))
    
compare_list.sort()

ans = 0
for i in range(N):
  if compare_list == []:
    ans += sum(card_list[i:])
    break
  if card_list[-1] > compare_list[-1][0]:
    ans += card_list.pop()
  elif compare_list[-1][1] > 0:
    ans += compare_list[-1][0]
    tmp = compare_list.pop()
    a = tmp[0]
    b = tmp[1]
    if b != 1:
      compare_list.append((a,b-1)) 
      
print(ans)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    lr = [list(map(int, list(input().split()))) for i in range(M)]
    # N, M = 4, 2
    # lr = [[1, 3], [2, 4]]
    all_set = set(range(1, N + 1))
    for line in lr:
        all_set = all_set & set(range(line[0], line[1] + 1))
    print(len(all_set))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    lr = [list(map(int, list(input().split()))) for i in range(M)]
    # N, M = 4, 2
    # lr = [[1, 1], [3, 4]]
    ll = []
    rl = []
    for line in lr:
        ll.append(line[0])
        rl.append(line[1])
    diff = min(rl) - max(ll)
    if diff < 0:
        print(0)
        return
    print(diff + 1)


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

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [-1 for _ in range(h+1)]
dp[0] = 0
for i in range(1,h+1):
    dp[i] = min([dp[max(0, i-pw)]+ma for pw, ma in ab])
print(dp[h])

### FIXED CODE ###

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [10**5 for _ in range(h+1)]
dp[0] = 0
for i in range(1,h+1):
    dp[i] = min([dp[max(0, i-pw)]+ma for pw, ma in ab])
print(dp[h])
### BUGGY CODE ###

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

dp = [[[0]*(max(sum(x),N*A)+1) for k in range(N+1)] for l in range(N+1)]
# dp[i][j][k] := i番目まででj枚選んで和がkになる組み合わせの数
dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(sum(x)+1):
            dp[i+1][j][k] += dp[i][j][k]
            if k-x[i] >= 0:
                dp[i+1][j+1][k] += dp[i][j][k-x[i]]

ans = 0
for k in range(1,N+1):
    ans += dp[N][k][A*k]
print(ans)


### FIXED CODE ###

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

dp = [[[0]*(max(sum(x),N*A)+1) for k in range(N+1)] for l in range(N+1)]
# dp[i][j][k] := i番目まででj枚選んで和がkになる組み合わせの数
dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(sum(x)+1):
            dp[i+1][j][k] += dp[i][j][k]
            if k-x[i] >= 0:
                dp[i+1][j+1][k] += dp[i][j][k-x[i]]

ans = 0
for k in range(1,N+1):
    ans += dp[N][k][A*k]
print(ans)
### BUGGY CODE ###

# coding: utf-8

n = int(input())
a = [int(x) for x in input().split()]

count = 0

for i in range(0, n):
    for j in range(i, n):
        xor_result = 0
        sum_result = 0
        for x in a[i:j+1]:
            xor_result ^= x
            sum_result += x
        if xor_result == sum_result:
            count += 1

print(count)

### FIXED CODE ###

# coding: utf-8

n = int(input())
a = [int(x) for x in input().split()]

count = 0
xor_result = 0
sum_result = 0
r = 0

for l in range(0, n):
    while r < n:
        x = a[r]
        if sum_result & x != 0:
            break
        xor_result ^= x
        sum_result += x
        r += 1
    count += r - l
    xor_result ^= a[l]
    sum_result -= a[l]

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

n = int(input())
A = list(map(int, input().split()))
c = 0
while True:
  for i in A:
    if i%2:
      print(c)
      exit()
    i //= 2
    
  c += 1


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
c = 0
while True:
  for i in range(n):
    if A[i]%2:
      print(c)
      exit()
    A[i] //= 2
    
  c += 1
### BUGGY CODE ###

import bisect

N, M = [int(i) for i in input().split()]
alist = [int(i) for i in input().split()]
alist.sort()
inputs = [[int(i) for i in input().split()] for j in range(M)]
inputs.sort(key=lambda x:x[1], reverse=True)

for i in inputs:
    if alist[0] > i[1]:
        break
    elif alist[i[0]-1] < i[1]:
        alist = [i[1]] * i[0] + alist[i[0]:]
    else:
        limit=bisect.bisect_left(alist, i[1])
        alist = [i[1]] * limit + alist[limit:]
    alist.sort()

print(sum(alist))




### FIXED CODE ###

import bisect

N, M = [int(i) for i in input().split()]
alist = [int(i) for i in input().split()]
alist.sort()
inputs = [[int(i) for i in input().split()] for j in range(M)]
inputs.sort(key=lambda x:x[1], reverse=True)

for i in range(N):
    if len(inputs) == 0:
        break
    if inputs[0][1] > alist[i]:
        alist[i] = inputs[0][1]
        inputs[0][0] -= 1
        if inputs[0][0] == 0:
            inputs.pop(0)
    else:
        break
print(sum(alist))
### BUGGY CODE ###

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

b = []
for i in range(n):
    r = 0
    for j in range(n-i):
        r += a[i+j]
        b.append(r)


n2 = n*(n+1)//2

res = 0
for i in range(41):
    p = res + (1 << (40-i))
    
    c = 0
    for j in range(n2):
        if p == p&b[j]:
            c+=1
    
    if c >= k:
        res = p

print(res)

### FIXED CODE ###

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

b = []
for i in range(n):
    r = 0
    for j in range(i,n):
        r += a[j]
        b.append(r)


n2 = n*(n+1)//2

res = 0
for i in range(41):
    p = res + 2**(40-i)
    
    c = 0
    for j in range(n2):
        if p == p&b[j]:
            c+=1
    
    if c >= k:
        res = p

print(res)
### BUGGY CODE ###

s=list(input())

c=0
for i in range(len(s)):
    if s[i:i+3]==["A","B","C"]:
        j=1
        ci=1
        while s[i-j]=="A":
            ci+=1
            j+=1
            if i-j<0:
                break
        s[i-j+1]="B"
        s[i-j+2]="C"
        s[i-j+3:i+3]=["A" for i in range(j)]
        c+=ci        

print(c)


### FIXED CODE ###

s=input()

s=s.replace("BC","D")

count=0

c=0
while c<len(s):
    if s[c]=="A" or s[c]=="D":
        d=c
        while s[d]=="A" or s[d]=="D":
            d+=1
            if d==len(s):
                break
        an=0
        for i in range(c,d):
            if s[i]=="A":
                an+=1
            else:
                count+=an
        c=d
    else:
        c+=1

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

A, B, C, K = map(int, input().split())
for i in range(K):
	temp_a = A
	temp_b = B
	A = B + C
	B = temp_a + C
	C = temp_a + temp_b
if abs(A - B) <= 10 ** 18:
	print(A - B)
else:
	print("unfair")

### FIXED CODE ###

A, B, C, K = map(int, input().split())
if K % 2 != 0:
	res = B - A
else:
	res = A - B
if res >= 10 ** 18:
	print("Unfair")
else:
	print(res)
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
B = []
for i in set(A):
    B.append(A.count(i))
print(sum(sorted(B)[:len(set(A)) - k]))

### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
A = list(map(int, input().split()))
AD = sorted(list(Counter(A).values()))
print(sum(AD[:len(AD) - k]))
### BUGGY CODE ###

import sys
import fractions
input = sys.stdin.readline


def gcd(x, y):
    while y > 0:
        r = x%y
        x = y
        y = r
    return x
 
def lcm(x, y):
    return x//fractions.gcd(x, y)*y
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for x in a:
    l = lcm(x, l)
 
ans = 0
for x in a:
    ans += l//x
 
print(ans%(10**9+7))


### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline


def gcd(x, y):
    while y > 0:
        r = x%y
        x = y
        y = r
    return x
 
def lcm(x, y):
    return x//fractions.gcd(x, y)*y
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for x in a:
    l = lcm(x, l)
 
ans = 0
for x in a:
    ans += l//x
 
print(ans%(10**9+7))
### BUGGY CODE ###

#import sys
#input = sys.stdin.buffer.readline

def main():
    N,M = map(int,input().split())
    S = [list(str(input())) for _ in range(N)]
    
    up = [[0 for _ in range(M)] for _ in range(N)]
    down = [[0 for _ in range(M)] for _ in range(N)]
    left = [[0 for _ in range(M)] for _ in range(N)]
    right = [[0 for _ in range(M)] for _ in range(N)]
    
    for i in range(M):
        if S[0][i] == ".":
            up[0][i] = 1
        for j in range(N-1):
            if S[j+1][i] == "#":
                up[j+1][i] = 0
            else:
                up[j+1][i] = up[j][i] + 1

    for i in range(M):
        if S[-1][i] == ".":
            down[-1][i] = 1
        for j in range(N-1):
            if S[-2-j][i] == "#":
                down[-2-j][i] = 0
            else:
                down[-2-j][i] = down[-1-j][i] + 1

    for i in range(N):
        if S[i][0] == ".":
            left[i][0] = 1
        for j in range(M-1):
            if S[i][j+1] == "#":
                left[i][j+1] = 0
            else:
                left[i][j+1] = left[i][j] + 1
    
    for i in range(N):
        if S[i][-1] == ".":
            right[i][-1] = 1
        for j in range(M-1):
            if S[i][-2-j] == "#":
                right[i][-2-j] = 0
            else:
                right[i][-2-j] = right[i][-1-j] + 1
    
    ans = 0
    for i in range(N):
        for j in range(M):
            if S[i][j] == ".":
                num = up[i][j]+down[i][j]+left[i][j]+right[i][j]-3
                ans = max(ans,num)
    
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

#import sys
#input = sys.stdin.buffer.readline
import numpy as np

def main():
    H,W = map(int,input().split())
    S = np.array([list(input()) for _ in range(H)]) == '.'

    up = np.zeros((H,W), dtype=int)
    down = np.zeros((H,W), dtype=int)
    left = np.zeros((H,W), dtype=int)
    right = np.zeros((H,W), dtype=int)
    
    for i in range(H-1):
        up[i+1,:] = (up[i,:] + 1) * S[i,:]
    for i in range(H-1):
        down[-i-2,:] = (down[-i-1,:] + 1) * S[-i-1,:]
    for i in range(W-1):
        left[:,i+1] = (left[:,i] + 1) * S[:,i]
    for i in range(W-1):
        right[:,-i-2] = (right[:,-i-1] + 1) * S[:,-i-1]
        
    print(((up+down+left+right)*S).max()+1)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

#包除原理
n = int(input())

TE = [[] for _ in range(n)]
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai -= 1
    bi -= 1
    TE[ai].append(bi)
    TE[bi].append(ai)
m  = int(input())
D =[]
for i in range(m):
    ai,bi = map(int ,input().split( ))
    ai -= 1
    bi-=1
    D.append((ai,bi))

bit = 1<<m


P =[0]*n
C = [[] for _ in range(n)]
from collections import deque
Q = deque()
Q.append(0)
V = [0]*n 
V[0] = 1

while Q:
    v = Q.popleft()
    for u in TE[v]:
        if not V[u]:
            V[u] = 1
            Q.append(u)
            P[u] = v
            C[v].append(u)
def path(u,v):
    u_p = set()
    tmp1 = u
    while tmp1:
        u_p.add(tmp1)
        tmp1 = P[tmp1]
    u_p.add(tmp1)
    tmp2 = v

    while tmp2 not in u_p:
        tmp2 = P[tmp2]     
    pth = set()
    tmp3 = u
    tmp4 = v
    while tmp3!=tmp2:
        pth.add((tmp3,P[tmp3]))##点だとダメ
        tmp3 = P[tmp3]
        
    while tmp4!= tmp2:
        pth.add((tmp4,P[tmp4]))
        tmp4 = P[tmp4]
    return pth
ans = 2**(n-1)
for i in range(1,bit):
    cnt = 0
    paths = set()
    for j in range(m):
        if (i>>j)&1:
            paths =paths | path(D[j][0],D[j][1])
            cnt += 1
    ans += (-1)**cnt *2**(n-1-len(paths))
print(ans)
    




### FIXED CODE ###

#包除原理
#辺の保持をbit演算での保持へ変換するのが辛い
n = int(input())

TE = [[] for _ in range(n)]
TE2 = []
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai -= 1
    bi -= 1
    TE[ai].append(bi)
    TE[bi].append(ai)
    TE2.append((ai,bi))
m  = int(input())
D =[]
for i in range(m):
    ai,bi = map(int ,input().split( ))
    ai -= 1
    bi-=1
    D.append((ai,bi))

bit = 1<<m


P =[0]*n
C = [[] for _ in range(n)]
from collections import deque
Q = deque()
Q.append(0)
V = [0]*n
V[0] = 1

while Q:
    v = Q.popleft()
    for u in TE[v]:
        if not V[u]:
            V[u] = 1
            Q.append(u)
            P[u] = v
            C[v].append(u)
def path(u,v):
    u_p = set()
    tmp1 = u
    while tmp1:
        u_p.add(tmp1)
        tmp1 = P[tmp1]
    u_p.add(tmp1)
    tmp2 = v

    while tmp2 not in u_p:
        tmp2 = P[tmp2]
    pth = 0##
    tmp3 = u
    tmp4 = v
    while tmp3!=tmp2:
        for t in range(n-1):
            if TE2[t] == (tmp3,P[tmp3]) or TE2[t]==(P[tmp3],tmp3):
                pth |= (1<<t)
        tmp3 = P[tmp3]

    while tmp4!= tmp2:
        for t in range(n-1):
            if TE2[t] == (tmp4,P[tmp4]) or TE2[t]==(P[tmp4],tmp4):
                pth |= (1<<t)
        tmp4 = P[tmp4]
    return pth

D2 = [path(D[i][0],D[i][1]) for i in range(m)]
#print(D2)
ans = 2**(n-1)
for i in range(1,bit):
    cnt = 0
    paths = 0
    for j in range(m):
        if (i>>j)&1:
            paths |= D2[j]
            cnt += 1
    cnt2 = 0
    for j in range(n-1):
        cnt2 += (paths>>j)&1
    ans += (-1)**cnt *2**(n-1-cnt2)
print(ans)
### BUGGY CODE ###

import copy

n = int(input())
s = str(input())
r_list = []
g_list = []
b_list = []
count = 0
for i in range(len(s)):
    if s[i] == "R":
        r_list.append(i)
    elif s[i] == "G":
        g_list.append(i)
    else:
        b_list.append(i)

for r in r_list:
    for g in g_list:
        x = abs(r-g)
        if max(r,g)+x in b_list:
            count += 1
        if min(r,g)-x in b_list:
            count += 1
        if(r+g)/2 in b_list:
            count += 1
print(len(r_list)*len(g_list)*len(b_list)-count)

### FIXED CODE ###

n = int(input())
s = list(input())
ans = (s.count("R")*s.count("G")*s.count("B"))

for i in range(n):
    for j in range(n-2*i):
        if {s[j], s[j+i], s[j+2*i]} == {"R", "G", "B"}:
            ans -= 1
print(ans)
### BUGGY CODE ###

n = int(input())
num = [int(i) for i in input().split()]

q = 1

for i in num:
    q=q*i
    if i == 0:
        q=0
        break

if q>1e18: print(-1)
else: print(q)
        


### FIXED CODE ###

n = int(input())
num = [int(i) for i in input().split()]

cont=0
ans=1

for j in num:
    if j == 0: cont+=1

if cont > 0: print(0)
else:
    for i in num:
        ans=ans*i
        if ans>1e18:
            ans=-1
            break
    print(ans)
### BUGGY CODE ###

import itertools
x,y,z,k = list(map(int, input().split())) 
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = [i + j for (i, j) in list(itertools.product(a, b))]

ab.sort(reverse=True)
del ab[min(k,x*y):]

abc = [ij + h for (ij, h) in list(itertools.product(ab, c))]

abc.sort(reverse=True)

for g in range(k):
  print(abc[g])

### FIXED CODE ###

import heapq
x,y,z,k = list(map(int, input().split())) 
a = sorted(list(map(int, input().split())),reverse=True)
b = sorted(list(map(int, input().split())),reverse=True)
c = sorted(list(map(int, input().split())),reverse=True)

ans = []
log = set()

total = (a[0] + b[0] + c[0]) * (-1)
heapq.heappush(ans, (total, 0, 0, 0))
log.add((0, 0, 0))

for i in range(k):
  (total, aa, bb, cc) = heapq.heappop(ans)
  print(total * (-1))
  if (aa+1, bb, cc) not in log:
    if aa+1 < x:
      total = (a[aa+1] + b[bb] + c[cc]) * (-1)
      heapq.heappush(ans, (total, aa+1, bb, cc))
      log.add((aa+1, bb, cc))
  if (aa, bb+1, cc) not in log:
    if bb+1 < y:
      total = (a[aa] + b[bb+1] + c[cc]) * (-1)
      heapq.heappush(ans, (total, aa, bb+1, cc))
      log.add((aa, bb+1, cc))
  if (aa, bb, cc+1) not in log:
    if cc+1 < z:
      total = (a[aa] + b[bb] + c[cc+1]) * (-1)
      heapq.heappush(ans, (total, aa, bb, cc+1))
      log.add((aa, bb, cc+1))
### BUGGY CODE ###

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

xlist.sort()

diflist=[]

for i in range(m-1):
    diflist.append(xlist[i+1]-xlist[i])

    diflist.sort()

if n >= m:
    print(0)
else:
    print(sum(diflist[:(m-n)]))

### FIXED CODE ###

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

xlist.sort()

diflist=[]


for i in range(m-1):
    diflist.append(xlist[i+1]-xlist[i])
diflist.sort()

if n >= m:
    print(0)
else:
    print(sum(diflist[:(m-n)]))
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
data=[[int(i) for i in input().split()] for i in range(m)]
data.sort(key=lambda x:x[1],reverse=True)
a.sort(reverse=True)
ans=0
flag=True
for _ in range(n):
  if data[0][1]<a[0] or flag==False:
    ans+=a.pop(0)
  else:
    ans+=data[0][1]
    data[0][0]-=1
    if data[0][0]==0:
      if len(data)>1:
        data=data[1:]
      else:
        flag=False
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=[[1,int(i)] for i in input().split()]
data=[[int(i) for i in input().split()] for i in range(m)]
data.extend(a)
data.sort(key=lambda x:x[1],reverse=True)
ans=0
flag=True
index=0
while n>0:
  tmp=min(data[index][0],n)
  ans+=data[index][1]*tmp
  n-=tmp
  index+=1
print(ans)
### BUGGY CODE ###

X = int(input())

for a in range(1 , 10**3 , 1):
  A = a**5
  for b in range(0 , X+1 , 1):
    B = b**5
    if(A-B==X):
      print(a, b)
      exit()
    else:
      continue
      
for a in range(0 , 10**3 , 1):
  A = a**5
  for b in range(0 , -X-1 , -1):
    B = b**5
    if(A-B==X):
      print(a, b)
      exit()
    else:
      continue

### FIXED CODE ###

X = int(input())
 
for a in range(-119 , 120 , 1):
  A = a**5
  for b in range(-119 , 120 , 1):
    B = b**5
    if(A-B==X):
      print(a, b)
      exit()
    else:
      continue
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
mod = 1000000007
a = tuple(int(input()) for _ in range(m))

dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n+1):
    if i in a: continue
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
mod = 1000000007
a = set(int(input()) for _ in range(m))

dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n+1):
    if i not in a: dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%mod)
### BUGGY CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1 or d < dst[nh][nw]:
            dq.appendleft((nh, nw, d))
            dst[nh][nw] = d

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        if dst[nh][nw] == -1 or d + 1 < dst[nh][nw]:
            dq.append((nh, nw, d + 1))
            dst[nh][nw] = d + 1

print(dst[eh][ew])


### FIXED CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])
### BUGGY CODE ###

N, *S = open(0).read().split()
N = int(N)
ans = 0
for p in range(N):
  flag = False
  for i in range(N):
    for j in range(N):
     x = i
     y = (j-p)%N
     a,b = y, (x+p)%N
     if S[i][j] != S[a][b]:
       flag = True
       break
    if flag:
      break
  else:
    ans+= N
print(ans)

### FIXED CODE ###

N, *S = open(0).read().split()
N = int(N)
ans = 0
for p in range(N):
  flag = False
  for i in range(N):
    for j in range(N):
     x = i
     y = (j-p)%N
     a,b = y, (x+p)%N
     if S[i][j] != S[a][b]:
       flag = True
       break
    if flag:
      break
  else:
    ans+= N
print(ans)
### BUGGY CODE ###

N = int(input())
S = [s for s in input()]
lis = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
ans = set()
for s in lis:
    for i in range(N-2):
        if S[i] == s[0]:
            if s[1] not in S[i+1:]:continue
            elif s[2] not in S[i+2:]:continue
            else:
                for j in range(i+1,N-1):
                    if S[j] == s[1]:
                        if s[2] in S[j+1:]:
                            ans.add(s)
                            break
                        else:continue
                    else:continue
        else:continue
# print(lis[10:20])
print(len(ans))

### FIXED CODE ###

N = int(input())
S = [s for s in input()]
lis = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
ans = 0
from collections import defaultdict
d = defaultdict(list)
for i,s in enumerate(S):
    d[s].append(i)

for s in lis:
    if d[s[0]]:
        i = min(d[s[0]])
        if d[s[1]]:
            for j in d[s[1]]:
                if j > i:
                    if d[s[2]]:
                        if max(d[s[2]]) > j:
                            ans += 1
                            break
                    break
        else:continue
    else:continue
                            
print(ans)