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

h, w = map(int, input().split())

mtx = [[0] * w for _ in range(h)]

for i in range(h):
    s = input()
    for j, ch in enumerate(s):
        mtx[i][j] = 1 if ch == '#' else 0

ret_mtx = [[[0] * 4 for _ in range(w)] for _ in range(h)]

# left 2 right
for i in range(h):
    for j in range(w):
        if mtx[i][j] == 1:
            continue
        else:
            ret_mtx[i][j][0] = 1 if i == 0 else ret_mtx[i-1][j][0] + 1
            ret_mtx[i][j][1] = 1 if j == 0 else ret_mtx[i][j-1][1] + 1


for i in range(h):
    for j in range(w):
        if mtx[-1-i][-1-j] == 1:
            continue
        else:
            ret_mtx[-1-i][-1-j][2] = 1 if i == 0 else ret_mtx[-i][-1-j][2] + 1
            ret_mtx[-1-i][-1-j][3] = 1 if j == 0 else ret_mtx[-1-i][-j][3] + 1

ret = 0

for i in range(len(ret_mtx)):
    for j in range(len(ret_mtx[i])):
        tmp = sum(ret_mtx[i][j]) - 3
        ret = max(ret, tmp)

print(ret)


### FIXED CODE ###

h, w = map(int, input().split())

mtx = [input() for _ in range(h)]

ret_mtx1 = [[0] * w for _ in range(h)]
ret_mtx2 = [[0] * w for _ in range(h)]
ret_mtx3 = [[0] * w for _ in range(h)]
ret_mtx4 = [[0] * w for _ in range(h)]

# left 2 right
for i in range(h):
    for j in range(w):
        if mtx[i][j] == '.':
            ret_mtx1[i][j] = 1 if i == 0 else ret_mtx1[i-1][j] + 1
            ret_mtx2[i][j] = 1 if j == 0 else ret_mtx2[i][j-1] + 1
        if mtx[-1-i][-1-j] == '.':
            ret_mtx3[-1-i][-1-j] = 1 if i == 0 else ret_mtx3[-i][-1-j] + 1
            ret_mtx4[-1-i][-1-j] = 1 if j == 0 else ret_mtx4[-1-i][-j] + 1

ret = 0

for i in range(h):
    for j in range(w):
        tmp = ret_mtx1[i][j] + ret_mtx2[i][j] + \
            ret_mtx3[i][j] + ret_mtx4[i][j] - 3
        ret = max(ret, tmp)

print(ret)
### BUGGY CODE ###

A,B = map(int, input().split())
max = A * B
lst = []
lst.append(max)

for i in range(max,0,-1):
    if (i % A == 0) and (i % B == 0):
        lst.append(i)
print(min(lst))


### FIXED CODE ###

A,B = map(int, input().split())
for i in range(B):
    if ( A * (i+1) ) % B == 0:
        print(A*(i+1))
        break
### BUGGY CODE ###

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**(40)
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

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

pc = True

fac = [0]*(10**6+1)
for a in A:
    lst = factorize(a)
    for p in lst:
        if not fac[p[0]]:
            fac[p[0]] = 1
        else:
            pc = False
            break
    if not pc:
        break
if pc:
    print('pairwise coprime')
else:
    g = A[0]
    for i in range(1,n):
        g = gcd(g, A[i])
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')

### FIXED CODE ###

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

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

pc = True

fac = [0]*(10**6+1)
for a in A:
    lst = factorize(a)
    for p in lst:
        if not fac[p[0]]:
            fac[p[0]] = 1
        else:
            pc = False
            break
    if not pc:
        break
if pc:
    print('pairwise coprime')
else:
    g = A[0]
    for i in range(1,n):
        g = gcd(g, A[i])
    if g == 1:
        print('setwise coprime')
    else:
        print('not coprime')
### BUGGY CODE ###

n,k =map(int,input().split())
 
while True:
  zet = abs(n-k)
  if zet == 0:
    print(zet)
    break
  if zet > n:
    print(n)
    break
  n = zet

### FIXED CODE ###

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

syou = n//k

zet = abs(n-k*syou)
if zet == 0:
  print(zet)
else:
  zet1 = abs(n-k*(syou+1))
  if zet > zet1:
    print(zet1)
  else: 
    print(zet)
### BUGGY CODE ###

S=int(input())
m=S//2019
ans=0
baisu=[]
for i in range(m):
  baisu.append(2019*(i+1))
for num in baisu:
  if str(num) in str(S):
    ans += 1
print(ans)


### FIXED CODE ###

s_inv = str(input())[::-1]
dp = [1]+[0]*2018
MOD = 0
ans = 0
num = 0
k = 1

for i in range(len(s_inv)):
  num+=int(s_inv[i])*k
  MOD = num % 2019
  dp[MOD] += 1
  k = k*10
  k %= 2019
for i in dp:
  ans += i*(i-1)/2

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

n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")

ans = r*g*b

for i in range(n):
    for j in range(n):
        if i + j*2 < n:
            if s[i] != s[i + j] and s[i] != s[i + j*2] and s[i + j] != s[i + j*2]:
                ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")

comb = r*g*b

for i in range(1, n - 1):
    for j in range(2, n):
        if i < j:
            if (2*j - i) <= n:
                if s[i - 1] != s[j - 1]:
                    if s[i - 1] != s[2*j - i - 1]:
                        if s[j - 1] != s[2*j - i - 1]:
                            comb -= 1

print(comb)
### BUGGY CODE ###

import copy
import math

def w(u,v):
    n1 = u[0]
    n2 = v[0]
    s1 = u[1]
    s2 = v[1]

N,M,S=map(int,input().split())

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M


for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())

Cs=[0]*N
Ds=[0]*N
for i in range(N):
    Cs[i],Ds[i] = map(int,input().split())

# -----

V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(1,N+1):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1
T= copy.copy(V)

if S > Ns:
    S = Ns

# -----

w = [[math.inf]*Nv for _ in range(Nv) ]
# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            w[ V[(u,ns_s)] ][ V[(v,ns_g)] ] = b
            # V -> U
            w[ V[(v,ns_s)] ][ V[(u,ns_g)] ] = b
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# C,D
for i in range(N):
    c = Cs[i]
    d = Ds[i]
    v = i+1
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        w[ V[(v,ns_s)] ][ V[(v,ns_g)] ] = d

# -----
D=[-1]*Nv
# -----
s=(1,S)
del T[s]
D[V[s]] = 0
for v in T:
    D[V[v]] = w[ V[s] ][ V[v] ]
while len(T) > 0:
    u,_ = min(T.items(),key=lambda x:D[x[1]])
    del T[u]
    for v in T:
        D[ V[v] ] = min( D[ V[v] ], D[ V[u] ] + w[ V[u] ][ V[v] ] )

for i in range(2,N+1):
    ans = min([ D[ V[(i,ns)] ] for ns in range(Ns+1) ])
    print(ans)

### FIXED CODE ###

import math
import heapq

N,M,S=map(int,input().split())

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())
    Us[i] -= 1
    Vs[i] -= 1

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(N):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1

G=[[] for _ in range(Nv)]

if S > Ns:
    S = Ns

# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            G[ V[(u,ns_s)] ].append( (V[(v,ns_g)],b) )
            # V -> U
            G[ V[(v,ns_s)] ].append( (V[(u,ns_g)],b) )
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = map(int,input().split())
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        G[ V[(i,ns_s)] ].append( (V[(i,ns_g)],d) )

# -----
D=[math.inf]*Nv
q=[]
# -----

s=V[(0,S)]
D[s] = 0
heapq.heappush(q,(0,s))

while len(q) > 0:
    p_cost,p_v = heapq.heappop(q)
    if D[p_v] < p_cost:
        continue
    for e_to,e_cost in G[p_v]:
        if D[ e_to ] > D[p_v] + e_cost:
            D[e_to] = D[p_v] + e_cost
            heapq.heappush(q, (D[e_to], e_to))

for i in range(1,N):
    ans = min([D[i*(Ns+1)+v] for v in range(Ns+1)])
    print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split(" ")))

sum_a =  sum(a)

minv = abs(2*sum(a[:1]) - sum_a)

for i in range(1, N-1):
    tmp = abs(2*sum(a[:i+1]) - sum_a)
#     print(tmp)
    
    if minv > tmp:
        minv = tmp
        
print(minv)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split(" ")))

su = sum(a)
diff = 1e10
cc = 0

for i in range(len(a)-1):
    cc += a[i]
    diff = min(diff, abs(su-2*cc))
print(diff)
### BUGGY CODE ###

n, y = map(int, input().split())
r = range(n+1)

ans = "-1 -1 -1"
for i in r:
    for j in r:
        k = (y-(10000*i+5000*j))//1000
        if k >= 0 and 10000*i+5000*j+1000*k == y and i+j+k == n:
            ans = "{} {} {}".format(i, j, k)

print(ans)


### FIXED CODE ###

N, Y = map(int, input().split())
ans = '-1 -1 -1'
for i in range(N + 1):
    for j in range(N + 1):
        k = N - (i + j)
        if k >= 0 and 10000 * i + 5000 * j + 1000 * k == Y:
            ans = '{} {} {}'.format(i, j, k)
            break
    else:
        continue
    break
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        ans += j
print(ans)


### FIXED CODE ###

import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    ans = n * (n + 1) // 2
    for i in range(2, n + 1):
        k = n // i
        ans += i * k * (k + 1) // 2
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    TA = []
    for _ in range(N):
        t, a = map(int, input().split())
        TA.append((t, a))

    x, y = TA[0]
    for i in range(1, N):
        t, a = TA[i]

        tmp_x = t
        tmp_y = a
        while tmp_x < x or tmp_y < y:
            tmp_x += t
            tmp_y += a

        x = tmp_x
        y = tmp_y

    ans = x + y
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    TA = []
    for _ in range(N):
        t, a = map(int, input().split())
        TA.append((t, a))

    A, B = 1, 1
    for i in range(N):
        x, y = TA[i]
        n = max((A + x - 1) // x, (B + y - 1) // y,)
        A = n * x
        B = n * y

    ans = A + B
    print(ans)


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

import bisect
n,m = map(int,input().split())
l = list(map(int,input().split()))
l.sort()
right = 2*10**5+1
left = 0

while right - left >1:
    mid = (right+left)//2
    
    x = 0
    for i in range(n):
        a = l[i]
        index = bisect.bisect_left(l,mid-a)
        x += n-index
   
    if x >= m:
        left = mid
    else:
        right = mid
ans = []
for i in range(n):
    a = l[i]
    for j in range(n):
        if a + l[j] >= left:
            ans.append(a+l[j])
ans.sort(reverse=True)

print(sum(ans[0:m]))



### FIXED CODE ###

def main():
    import bisect
    import numpy as np
    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    l.sort()
    l1 = np.array(l)
    def bise(x):
        y = np.searchsorted(l1,x-l1)
        return n*n-y.sum()

    left = -1
    right = l[-1]*2+1

    while right > left+1:
        mid = (right+left)//2
        
        if bise(mid) >= k:
            left = mid
        else:
            right = mid
    ans = 0
    count = 0
    acc = [0]
    for i in l:
        acc.append(acc[-1]+i)
    for i in l:
        index = bisect.bisect_left(l,right-i)
        ans += i*(n-index) + acc[n]-acc[index]
        count += n-index

    print(ans-(count-k)*left)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from itertools import product
N = int(input())
S = input()
S = [int(s) for s in S]
ans = 0
for q in product(range(10),repeat=3):
    i = 0
    for s in S:
        if s==q[i]:
            if i==2:
                ans += 1
                break
            else:
                i+=1
print (ans)
            


### FIXED CODE ###

from itertools import product
N = int(input())
S = input()
S = [int(s) for s in S]
ans = 0
for q in product(range(10),repeat=3):
    i = 0
    for s in S:
        if s==q[i]:
            if i==2:
                ans += 1
                break
            else:
                i+=1
print (ans)
### BUGGY CODE ###

from collections import deque
def main():
  s = deque(list(input()))
  q = int(input())

  cnt = 0
  for _ in range(q):
    t = input()
    if t[0] == "1":
      cnt += 1
    else:
      if cnt%2 == 1:
        s.reverse()
        cnt = 0
      _,f,c = t.split(" ")
      if f == "1":
        s.appendleft(c)
      else:
        s.append(c)
  if cnt%2 == 1:
    s.reverse()
  print("".join(list(s)))

if __name__=="__main__":
  main()

### FIXED CODE ###

from collections import deque
def main():
  s = deque(list(input()))
  q = int(input())
  sr = s.reverse
  sa = s.append
  sal = s.appendleft

  cnt = 0
  for _ in range(q):
    t = input()
    if t[0] == "1":
      cnt += 1
    else:
      _,f,c = t.split(" ")
      if f == "1":
        if cnt%2==1:
          sa(c)
        else:
          sal(c)
      else:
        if cnt%2==1:
          sal(c)
        else:
          sa(c)
  if cnt%2 == 1:
    sr()
  print("".join(list(s)))

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

import itertools
while 1:
	n = input()
	if n == 0: break
	s = map(int,raw_input().split())
	sm = ans = sum(s)
	for i in range(1,n-1):
		for party in itertools.combinations(s,i):
			ans = min(ans,abs(sm-2*sum(party)))
			if ans == 0:
				break
	print ans

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)
### BUGGY CODE ###

N=int(input())
S=input()
b=0
for i in range(1000):
 i1=int(i/100)
 i2=int((i-i1*100)/10)
 i3=i%10
 a=0
 for j in range(N):
  if a==0:
   if int(S[j])==i1:
    a+=1
  elif a==1:
   if int(S[j])==i2:
    a+=1
  else:
   if int(S[j])==i3:
    b+=1
    break
print(b)

### FIXED CODE ###

N=int(input())
S=input()
A=[0]*N
for i in range(N):
 A[i]=int(S[i])
b=0
for i in range(1000):
 i1=int(i/100)
 i2=int((i-i1*100)/10)
 i3=i%10
 a=0
 for j in range(N):
  if a==0:
   if A[j]==i1:
    a+=1
  elif a==1:
   if A[j]==i2:
    a+=1
  else:
   if A[j]==i3:
    b+=1
    break
print(b)
### BUGGY CODE ###

from functools import reduce
S = list(map(int,input().rstrip()))
l=len(S)
result=0
for i in range(0,l-3):
    for j in range(i+4,l+1):
        n = reduce( lambda a,b:10*a+b, S[i:j])
        if n %2019==0:
            result+=1
print(result)

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    from functools import reduce
    import collections
     
    S = list(map(int,input().rstrip()))
    N=len(S)
    mod_list = [0]
    for i in range(1,N+1):
        new1 =pow(10,i-1,2019)
        new = (new1*S[-i]+mod_list[-1])%2019
        #print(new)
        mod_list.append(new)
        
    count = collections.Counter(mod_list)
    ans =0
    for j in range(2019):
        n = count[j]
        ans+= n*(n-1)/2
    print(int(ans))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# 2019は10と互いに素なので、
# N%2019と(N*(10**正整数))%2019は一致する
# pppppxxxxxxxを2019で割った余りとxxxxxxxを2019で割った余りが一致すれば、
# pppppは2019で割り切れることが言える

S = input()
from collections import defaultdict
amari = defaultdict(int)
for i in range(1,len(S)+1):
  amari[int(S[len(S)-i:])%2019] += 1
  
ans = 0
if 0 in amari:
  ans += amari[0]
for n in amari.values():
  ans += (n * (n-1)) // 2
  
print(ans)

### FIXED CODE ###

# 2019は10と互いに素なので、
# N%2019と(N*(10**正整数))%2019は一致する
# pppppxxxxxxxを2019で割った余りとxxxxxxxを2019で割った余りが一致すれば、
# pppppは2019で割り切れることが言える

S = input()
from collections import defaultdict
amari = defaultdict(int)
cur = 0 # 今の数値
keta = 1 # 今の桁数
for i in range(len(S)-1,-1,-1):
  cur += int(S[i]) * keta
  cur %= 2019
  keta *= 10
  keta %= 2019
  amari[cur] += 1

ans = 0
if 0 in amari:
  ans += amari[0]
for n in amari.values():
  ans += (n * (n-1)) // 2
  
print(ans)
### BUGGY CODE ###

N, M, L = map(int, input().split())
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = c


# 全点間最短距離を計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j])
for i in range(N):
    G[i][i] = 0

# コストL以下で移動可能な頂点間にコスト１の辺を張る
E = [[float('inf')] * N for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j] <= L:
            E[i][j] = 1


# そのグラフの全点間最短距離を求める
for k in range(N):
    for i in range(N):
        for j in range(N):
            E[i][j] = min(E[i][j], E[i][k] + E[k][j])


# クエリに答えていく
Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    s, t = s - 1, t - 1
    print(E[s][t] - 1 if E[s][t] != float('inf') else - 1)


### FIXED CODE ###

import sys
from scipy.sparse.csgraph import floyd_warshall
N, M, L = map(int, input().split())
INF = 10 ** 9 + 1
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = c


# 全点間最短距離を計算
G = floyd_warshall(G)


# コストL以下で移動可能な頂点間にコスト１の辺を張る
E = [[float('inf')] * N for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j] <= L:
            E[i][j] = 1


# そのグラフの全点間最短距離を求める
E = floyd_warshall(E)


# クエリに答えていく
Q = int(input())
for i in range(Q):
    s, t = map(int, sys.stdin.readline().split())
    s, t = s - 1, t - 1
    print(int(E[s][t] - 1) if E[s][t] != float('inf') else - 1)
### BUGGY CODE ###

import sys

n = int(input())
a = [0] + [int(sys.stdin.readline()) for _ in range(n)]

pushed = [1]
button = 1

for _ in range(n):
    if a[button] in pushed:
        print(-1)
        break
    pushed.append(a[button])
    button = a[button]
    if button == 2:
        print(len(pushed) - 1)
        break

### FIXED CODE ###

import sys

n = int(input())
a = [0] + [int(sys.stdin.readline()) for _ in range(n)]

button = 1
count = 0

for _ in range(n):
    if button == 2:
        print(count)
        break
    button = a[button]
    count += 1

if count == n:
    print(-1)
### BUGGY CODE ###

def main():
  n = int(input())
  l = list(map(int, input().split()))
  for i in range(n):
    print(l.count(i+1))

if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  n = int(input())
  l = list(map(int, input().split()))
  ans = [0] * n
  for i in range(n-1):
    ans[l[i]-1] += 1
  for i in ans:
    print(i)

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

from collections import Counter
import math
import sys


def input():
    return sys.stdin.readline()[:-1]


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def make_divisors(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i != n and i in c:
                return False

            tmp = n // i
            if i != tmp:
                if tmp != n and tmp in c:
                    return False
    return True


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

c = Counter(A)

# 1がある時
if 1 in c:
    if c[1] >= 2:
        print(0)
    else:
        print(1)
    exit(0)

ans = 0
for a in A:
    # 同じ数が複数ある
    if c[a] >= 2:
        continue

    # 1と同数がなくて素数なら割り切れる数はない
    if is_prime(a):
        ans += 1
        continue

    # 約数があるか
    if make_divisors(a):
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

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

c = Counter(A)
p = [True]*(10**6+1)

for k, v in c.items():
    t = k*2
    while t <= 10**6:
        p[t] = False
        t += k

ans = 0
for a in A:
    if c[a] == 1 and p[a]:
        ans += 1
print(ans)
### BUGGY CODE ###

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

dp = [0]

while dp[-1] < H:
    elem = 0
    for A, B in AB:
        if B <= len(dp): 
            elem = max(elem, dp[-B] + A)
    dp.append(elem)

print(len(dp) - 1)

### FIXED CODE ###

from operator import itemgetter

INF = 10 ** 10

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

A_max = max(map(itemgetter(0), AB))

dp = [INF] * (H + A_max+1)
dp[0] = 0

for i in range(0, H+A_max+1):
    for A, B in AB:
        if A <= i:
            dp[i] = min(dp[i], dp[i-A] + B)

print(min(dp[H:]))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if i + 1 == A[j] and j + 1 == A[i]:
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    if i + 1 == A[A[i]-1]:
        ans += 1
print(ans // 2)
### BUGGY CODE ###

n=int(input())
ans=n-1
for i in range(2,n):
  if n%i:continue
  j=n//i
  if j<i:break
  ans=j+i-2
print(ans)

### FIXED CODE ###

n=int(input())
a=n-1
for i in range(1,int(n**0.5)+1):
  if n%i:continue
  j,k=i,n//i
  a=min(a,j+k-2)
print(a)