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

import sys

def parent(i):
    return (i + 1) / 2 - 1

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def sibling(i):
    if i % 2 == 0:
        return i - 1
    else:
        return i + 1

def insert(S, k):
    S.append(k)
    idx = len(S) - 1
    while True:
        p = parent(idx)
        if p < 0 or S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p

def maxHeapify(A, i):
    l = 2 * i + 1
    r = 2 * i + 2

    if l < len(A) and A[l] > A[i]:
        largest = l
    else:
        largest = i

    if r < len(A) and A[r] > A[largest]:
        largest = r

    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)

def extract(S):
    print S[0]
    S[0] = S[-1]
    S.pop()
    maxHeapify(S, 0)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)

### FIXED CODE ###

import sys

def insert(k):
    global S, last
    S[last] = k
    idx = last
    while True:
        p = (idx + 1) / 2 - 1
        if S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p
    last += 1

def maxHeapify(i):
    global S, last
    l = 2 * i + 1
    r = 2 * i + 2

    if l < last and S[l] > S[i]:
        largest = l
    else:
        largest = i

    if r < last and S[r] > S[largest]:
        largest = r

    if largest != i:
        S[i], S[largest] = S[largest], S[i]
        maxHeapify(largest)

def extract():
    global S, last
    print S[0]
    last -= 1
    S[0], S[last] = S[last], 0
    maxHeapify(0)

lines = sys.stdin.readlines()
lines.pop()

S = [0] * 2000001
S[2000000] = 2000000000
last = 0
for line in lines:
    if line[0] == "i":
        insert(int(line[7:]))
    else:
        extract()
### BUGGY CODE ###

from itertools import groupby

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

for _ in range(K):
    if not (S.find("L")>=0 and S.find("R")>=0):
        break
    A = list((s,len(list(it))) for s, it in groupby(S))
    s0, _ = A[0]
    s1, l = A[1]
    A[1] = (s0, l)
    S = "".join(s*l for s, l in A)
print(N - len(list(groupby(S))))

### FIXED CODE ###

from itertools import groupby
d = {"R": "L", "L": "R"}
N, K = map(int, input().split())
S = input()
A = [(s,len(list(it))) for s, it in groupby(S)]
A = [(d[s], l) if i & 1 and i//2 < K else (s, l) for i, (s, l) in enumerate(A)]
S = "".join(s*l for s, l in A)
print(N - len(list(groupby(S))))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

SC=[0,0,0]#1個,2個,3個

for a in A:
    SC[a-1]+=1
SC=tuple(SC)

#N=300
#SC=(N-2,1,1,0)

DAYSDICT=dict()

def days(SC):
    if DAYSDICT.get(SC)!=None:
        return DAYSDICT[SC]

    #if SC[0]<0 or SC[1]<0 or SC[2]<0:
    #    return 0

    k=sum(SC)

    if k==0:
        return 0

    ANS=N
    if SC[0]>0:
        ANS+=days((SC[0]-1,SC[1],SC[2]))*SC[0]
    if SC[1]>0:
        ANS+=days((SC[0]+1,SC[1]-1,SC[2]))*SC[1]
    if SC[2]>0:
        ANS+=days((SC[0],SC[1]+1,SC[2]-1))*SC[2]
        
    DAYSDICT[SC]=ANS/k
    return DAYSDICT[SC]

for k in range(SC[2]+1):
    for j in range(SC[1]+SC[2]+1-k):
        for i in range(SC[0]+SC[1]+SC[2]+1-j-k):
            days((i,j,k))

print(DAYSDICT[SC])

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

SC=[0,0,0]#1個,2個,3個

for a in A:
    SC[a-1]+=1
one,two,three=SC

DAYSDICT=[[[0.0]*301 for j in range(301)] for k in range(301)]
DAYSDICT[0][0][0]=0
def days(one,two,three):
    ANS=N
    if one>0:
        ANS+=DAYSDICT[one-1][two][three]*one
    if two>0:
        ANS+=DAYSDICT[one+1][two-1][three]*two
    if three>0:
        ANS+=DAYSDICT[one][two+1][three-1]*three
        
    DAYSDICT[one][two][three]=ANS/(one+two+three)


for k in range(three+1):
    for j in range(two+three+1-k):
        for i in range(one+two+three+1-j-k):
            if i==j==k==0:
                continue
            days(i,j,k)

print(DAYSDICT[one][two][three])
### BUGGY CODE ###

def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque
n,m=LI()
edge=[[]*n for i in range(n)]
for i in range(m):
    a,b=LI()
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
# print(edge)

ans=[-1]*n
goal=deque([0])
while goal:
    if -1 not in ans:break
    g=goal.popleft()
    for i in range(n):
        v=edge[i]
        if g in v:
            ans[i]=g
            edge[i].clear()
            goal.append(i)

if -1 in ans:
    no()
    exit()
yes()
for i in ans[1:]:
    print(i+1)



### FIXED CODE ###

def LI():return list(map(int,input().split()))
def yes():print("Yes")
def no():print("No")
from collections import deque

def main():
    n,m=LI()
    edge=[[] for i in range(n)]
    for i in range(m):
        a,b=LI()
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)    
    ans=[-1]*(n)
    goal=deque([0])
    while goal:
        g=goal.popleft()
        for i in edge[g]:
            if ans[i]==-1:
                ans[i]=g+1
                goal.append(i)
    yes()
    print(*ans[1:])
main()
### BUGGY CODE ###

N,Q=map(int,input().split())


event=[]

for _ in range(N):
    S,T,X=map(int,input().split())
    event.append([S-X,1,X])
    event.append([T-X,-1,X])

D_list=[int(input()) for _ in range(Q)]


event.sort()
for d in D_list:
    stop_set=set()
    for e in event:
        if e[0]>d:
            break
        else :
            if e[1]==1:
                stop_set=stop_set|{e[2]}
            elif e[1]==-1:
                stop_set=stop_set-{e[2]}
    if stop_set==set():
        stop_set=stop_set|{-1}
    print(min(stop_set))

### FIXED CODE ###

from heapq import heappop,heappush

N,Q=map(int,input().split())


event=[]
q=[]
for _ in range(N):
    S,T,X=map(int,input().split())
    event.append([S-X,1,X])
    event.append([T-X,-1,X])

for i in range(Q):
    event.append([int(input()),2,i])

stop_set=set()
event.sort()
q=[]

for pos,m,x in event:
    if m==-1:
        stop_set.remove(x)
        
    elif m==1:
        #heappushする時点でqはソートされている
        heappush(q,x)
        stop_set.add(x)
    
    else:
        #この時点でのstop_setは、i番目の人が遭遇する通行止めの座標
        #この時点でのqは今までstopになった座標
        while q:
            #qはソート済なので、q[0]は最小値　それがstop_setから外れている場合、heappopでそれを排除する
            if q[0] not in stop_set:
                heappop(q)
            #q[0]がstop_setから外れてない場合、それ以降のqも外れていないのでbreak    
            else:
                break

        if q:
            print(q[0])
        else:
            print(-1)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
cnt = [[float('inf')]*w for _ in range(h)]
moves = ((0, 1), (0, -1), (1, 0), (-1, 0))

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0 

def bfs(sy, sx):
  q = deque([[sy, sx]])
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy
      nx = x + dx 
      if 0 <= ny < h and 0 <= nx < w and a[ny][nx] == '.' and used[ny][nx] == 0:
        used[ny][nx] = 1
        cnt[ny][nx] = min(cnt[ny][nx], cnt[y][x]+1)
        q.append([ny, nx])


for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      used = [[0]*w for _ in range(h)]
      bfs(i, j)

ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])
print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
ans = 0
searched = [[0 for _ in range(w)] for _ in range(h)]
q = deque([])

def bfs():
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      next_y = y + dy
      next_x = x + dx 
      if 0 <= next_y < h and 0 <= next_x < w and searched[next_y][next_x] == 0 and a[next_y][next_x] == '.' and cnt[next_y][next_x] > cnt[y][x]+1:
        searched[next_y][next_x] = 1
        q.append([next_y, next_x])
        cnt[next_y][next_x] = cnt[y][x]+1

for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0
      searched[i][j] = 1
      q.append([i, j])

bfs()
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])

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

n=input()
s=[]
for i in range(n):
	s+=[raw_input()]
result=0
for shift in range(n):
	ok=True
	for i in range(n):
		for j in range(n):
			if s[i][j]!=s[j][i]:
				ok=False
				break
	if ok:
		result+=n
	for i in range(n):
		s[i]=s[i][1:]+s[i][0:1]
print result

### FIXED CODE ###

n=input()
s=[raw_input() for i in range(n)]
t=[]
for i in range(n):
	t+=[s[j][i] for j in xrange(n)]*2
s+=s
s=''.join(s)
#print s
t=''.join(t)
#print t
result=0
for shift in xrange(n):
	ok=True
	for i in xrange(n):
		if s[(i+shift)*n: (i+shift)*n+n]!=t[i*n*2+shift: i*n*2+shift+n]:
			ok=False
			break
	if ok:
		result+=n
print result
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for i in range(Q):
  B, C = map(int, input().split())
  count = 0
  check = True
  while check == True:
    if B in A:
      count += 1
      A.remove(B)
    else:
      check = False
  for i in range(count):
    A.append(C)
  print(sum(A))


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
su = sum(A)
counter = Counter(A)
lis = {}
for i in range(Q):
  B, C = map(int, input().split())
  su -= B * counter[B]
  su += C * counter[B]
  counter[C] += counter[B]
  counter[B] = 0
  print(su)
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
All = [[0]*40 for i in range(n)]
K = [0]*40
stopper = 0
sum_ = 0



for i in range(len(A)):
    bin_a = format(A[i],'b')
    list_a = [int(i) for i in bin_a]
    All[i] = [0]*(40-len(list_a))+ list_a
    
bin_k =   format(k,'b') 
list_k = [int(i) for i in bin_k]
K = [0]*(40-len(list_k))+list_k

b = np.cumsum(All, axis = 0)
B = b[len(b)-1]
    
for i in range(40):
    if K[i]==1 and B[i]>= (n+1)//2:
        K[i]=0
        stopper = i
        break

if stopper!=0 and stopper<=38:
    for i in range(stopper+1,40):
        if  B[i]>= (n+1)//2:
            K[i] = 0
        else:
            K[i] = 1

for i in range(n):
    for j in range(1,41):
        All[i][-j] = K[-j]^All[i][-j]
        sum_ = sum_ + All[i][-j]*(2**(j-1))

print(sum_)

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
All = [[0]*41 for i in range(n)]
K = [0]*41
stopper = 0
sum_ = 0



for i in range(len(A)):
    bin_a = format(A[i],'b')
    list_a = [int(i) for i in bin_a]
    All[i] = [0]*(41-len(list_a))+ list_a
    
bin_k =   format(k,'b') 
list_k = [int(i) for i in bin_k]
K = [0]*(41-len(list_k))+list_k

b = np.cumsum(All, axis = 0)
B = b[len(b)-1]
    
for i in range(41):
    if K[i]==1 and B[i]>= (n+1)//2:
        K[i]=0
        stopper = i
        break

if stopper!=0 and stopper<=39:
    for i in range(stopper+1,41):
        if  B[i]>= (n+1)//2:
            K[i] = 0
        else:
            K[i] = 1
            
            
for i in range(41):
    if K[i]==1:
        B[i] = n-B[i]

for i in range(1,42):
    sum_ = sum_ + B[-i]*(2**(i-1))

print(sum_)
### BUGGY CODE ###

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

num = len(s)
ans = 0
for i in range(num):
    a = [s[i]]
    for j in range(i+1, num):
        if s[j] in set(a):
            continue
        a.append(s[j])
        for k in range(j+1, num):
            if s[k] in set(a) or j-i == k-j:
                continue
            ans += 1
        a.pop()

print(ans)


### FIXED CODE ###

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

num = len(s)
ans = s.count('R')*s.count('G')*s.count('B')

for i in range(num):
    for j in range(i+1, num):
        if 0 <= 2*j-i < num:
            if s[i] != s[j] and s[j] != s[2*j-i] and s[2*j-i] != s[i]:
                ans -= 1
print(ans)
### BUGGY CODE ###

from queue import Queue
N, Q = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
d = [0]*N
ok = [True]*N
cnt = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x
q = Queue()
q.put(0)
while not q.empty():
    p = q.get()
    d[p] += cnt[p]
    ok[p] = False
    for np in E[p]:
        if ok[np]:
            cnt[np] += cnt[p]
            q.put(np)

print(*d)

### FIXED CODE ###

from collections import defaultdict
N, Q = map(int, input().split())
E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
d = [0]*N
ok = [True]*N
cnt = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x
stack = [0]
while stack:
    p = stack.pop()
    d[p] += cnt[p]
    ok[p] = False
    for np in E[p]:
        if ok[np]:
            cnt[np] += cnt[p]
            stack.append(np)

print(*d)
### BUGGY CODE ###

N,M=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()
cost=sum(A)
for i in range(M):
    if A[N-1]%2==0:
        cost-=A[N-1]//2
    else:
        cost-=A[N-1]//2+1
    A[N-1]=A[N-1]//2
    if A[N-2]>A[N-1]:
        A.sort()
print(cost)

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=[-1*int(i) for i in input().split()]
heapq.heapify(A)
for _ in range(M):
    a=-1*heapq.heappop(A)
    a=a//2
    heapq.heappush(A,-1*a)
print(-1*sum(A))
### BUGGY CODE ###

from sys import stdin
data = int(stdin.readline().rstrip())

list = []
for x in range(1,10**2):
    for y in range(1, 10**2):
        for z in range(1, 10**2):
            list.append(x**2+y**2+z**2+x*y+y*z+z*x)

for i in range(1,data+1):
    print(list.count(i))

### FIXED CODE ###

from sys import stdin
data = int(stdin.readline().rstrip())

list = [0]*10000
for x in range(1,10**2):
    for y in range(1, 10**2):
        for z in range(1, 10**2):
            a = x**2+y**2+z**2+x*y+y*z+z*x
            if a <= 10**4:
                list[a-1] += 1

for i in range(1,data+1):
    print(list[i-1])
### BUGGY CODE ###

#!/usr/bin/env python3
from scipy.special import comb


def stair(r):
    con = 0
    for i in range(r // 2 + 1):
        con += comb(r - i, i, exact=True)
    return con


n, m, *a = map(int, open(0).read().split())
if sum(a[i + 1] == a[i] + 1 for i in range(m - 1)) > 0:
    print(0)
    exit()

a.append(n+1)
c = -1
ans = 1
for i in a:
    ans = ans * stair(i - c - 2) % (10**9 + 7)
    c = i
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(1000000)


memo = [0]*(10**5+1)
def count(n):
    if n < 2:
        return 1
    if memo[n] != 0:
        return memo[n]
    memo[n] = count(n-1) + count(n-2)
    return memo[n]


n, m, *a = map(int, open(0).read().split())
if sum(a[i + 1] == a[i] + 1 for i in range(m - 1)) > 0:
    print(0)
    exit()

a.append(n + 1)
c = -1
ans = 1
for i in a:
    ans = ans * count(i - c - 2) % (10**9 + 7)
    c = i
print(ans)
### BUGGY CODE ###

k,s = map(int, input().split())
count = 0
for i in range(0,k+1,1):
  if i > s:
    break
  for j in range(0,k+1,1):
    if j > s:
      break
    for k in range(0,k+1,1):
      if k > s:
        break
      if i+j+k == s:
        count = count+1
print(count)

### FIXED CODE ###

k,s = map(int, input().split())
count = 0
for i in range(0,k+1,1):
  for j in range(0,k+1,1):
    if 0 <= s-i-j <= k:
      count = count+1
print(count)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B_to_C = []
for i in range(Q):
  B_to_C.append([int(x) for x in input().split()])

dict_A = {}

for a in A:
  if a in dict_A:
    dict_A[a] += 1
  else:
    dict_A[a] = 1
    
for B, C in B_to_C:
  if B in dict_A:
    if C in dict_A:
      dict_A[C] += dict_A[B]
      del dict_A[B]
    else:
      dict_A[C] = dict_A[B]
      del dict_A[B]
      
  sums = 0
  for k, v in dict_A.items():
    sums += k*v
  print(sums)
  
  

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B_to_C = []
for i in range(Q):
  B_to_C.append([int(x) for x in input().split()])

dict_A = {}
sums = 0

for a in A:
  if a in dict_A:
    dict_A[a] += 1
  else:
    dict_A[a] = 1
    
for k, v in dict_A.items():
  sums += k*v
  
for B, C in B_to_C:
  if B in dict_A:
    count_of_num = dict_A[B]
    if C in dict_A:
      dict_A[C] += dict_A[B]
      del dict_A[B]
    else:
      dict_A[C] = dict_A[B]
      del dict_A[B]
      
    sums = sums - B*count_of_num + C*count_of_num
    print(sums)
    
  else:
    print(sums)
### BUGGY CODE ###

import sys
n = int(input())
s = input()
q = int(input())
k = list(map(int, sys.stdin.readline().split()))
x = []
for i in s:
  if i == "D":
    x.append(1)
  elif i == "M":
    x.append(2)
  elif i == "C":
    x.append(3)
  else:
    x.append(0)
mrui = [0]* (n+1)
for i in range(1,n+1):
  mrui[i] = mrui[i-1]
  if x[i-1] == 2:
    mrui[i] += 1
dp = [[0]*4 for _ in range(n)]
for i in k:
  dp[-1] = [1,0,0,0]
  for j in range(n):
    dp[j] = dp[j-1]
    kon = x[j]
    if kon:
      dp[j][kon] += dp[j-1][kon-1]
    if j >= i-1:
      if x[j-i+1] == 1:
        dp[j][1] -= 1
        dp[j][2] -= (mrui[j+1]-mrui[j-i+2])
  
  print(dp[n-1][3])

### FIXED CODE ###

import sys
n = int(input())
s = input()
q = int(input())
k = list(map(int, sys.stdin.readline().split()))
x = []
for i in s:
  if i == "D":
    x.append(1)
  elif i == "M":
    x.append(2)
  elif i == "C":
    x.append(3)
  else:
    x.append(0)
mrui = [0]* (n+1)
for i in range(1,n+1):
  mrui[i] = mrui[i-1]
  if x[i-1] == 2:
    mrui[i] += 1
dp = [0,0,0,0]
dp1 = [0,0,0,0]
for i in k:
  dp = [1,0,0,0]
  for j in range(n):
    dp1 = dp
    kon = x[j]
    if kon:
      dp1[kon] += dp[kon-1]
    dp = dp1
    if j >= i-1:
      if x[j-i+1] == 1:
        dp[1] -= 1
        dp[2] -= (mrui[j+1]-mrui[j-i+2])
  
  print(dp1[3])
### BUGGY CODE ###

from collections import deque
def mbfs(S,H,W,sh,sw):
    dist[sh][sw]=0
    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for di in range(4):
            nh=h+dx[di]
            nw=w+dy[di]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if((dist[nh][nw]!=-1 and dist[nh][nw]<dist[h][w]+1) or S[nh][nw]=='#'):
                continue
            dist[nh][nw]=dist[h][w]+1
            d.append([nh,nw])
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
dist=[[-1]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            mbfs(A,H,W,i,j)
print(max(max(dist[i]) for i in range(H)))

### FIXED CODE ###

from collections import deque
def mbfs(S,H,W):
    dxy=[[1,0],[0,1],[-1,0],[0,-1]]
    while(len(d)!=0):
        h,w,x=d.popleft()
        for t,y in dxy:
            if(0<=h+t<=H-1 and 0<=w+y<=W-1 and S[h+t][w+y]!='#'):
                S[h+t][w+y]='#'
                d.append([h+t,w+y,x+1])
    return x
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
d=deque()
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            d.append([i,j,0])
print(mbfs(A,H,W))
### BUGGY CODE ###

n = int(input())
a = sorted([int(i) for i in input().split()], reverse=True)
mod = 10**9 + 7
ans = 0
for j in range(len(bin(a[0])) - 2):
  k = [0, 0]
  for i in a:
    k[i >> j & 1] += 1
  ans = (ans + (k[0] * k[1]) * 2**j) % mod
print(ans)

### 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 ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 19 21:27:49 2020

@author: arute
"""


from sys import stdin

import time
import numpy as np

############################################

# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])

data = []
write = stdin.readline().split()
for i in range(N-1):
    data.append(int(write[i]))

data = np.asarray(data)

for i in range(N):
    print(np.sum(data==(i+1)))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 19 21:27:49 2020

@author: arute
"""


from sys import stdin

import time
import numpy as np


############################################

# read data for n sequences.
temp = stdin.readline().split()
N = int(temp[0])

data = []
write = stdin.readline().split()
for i in range(N-1):
    data.append(int(write[i]))

data = np.asarray(data)

out = np.zeros(N)
for d in data:
    out[d-1] += 1

o = ""
for l in out:
    o+=str(int(l))+"\n"

print(o)
### BUGGY CODE ###

import collections
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

m = int(input())
a = list(map(int,input().split()))[:m]

for i in a:
    res = 0
    t = a[:]
    t.remove(i)
    c = collections.Counter(t)
    for v in c.values():
        if v >= 2:
            res += combinations_count(v, 2)
    
    print(res)

### FIXED CODE ###

import collections


m = int(input())
A = list(map(int,input().split()))[:m]
c = collections.Counter(A)
 
def hoge(n):
    return n * (n - 1) // 2

full = sum([ hoge(i) for i in c.values()])

for a in A:
    print(full - hoge(c[a]) + hoge(c[a]-1))
### BUGGY CODE ###

from collections import deque

n=int(input())
S=deque()
A=deque()

for i in range(n):
	cnt=0
	str=input().split()
	if str[0][0]=="i":
		S.append(str[1])
	else:
		for i in range(len(S)):
			if S[i]==str[1]:
				cnt+=1
				break
		
		if cnt==1:
			print("yes")
		else:
			print("no")


### FIXED CODE ###

n=int(input())
dict={}
for i in range(n):
    str=input()
    if str[0]=="i":
        dict.update({str[7:]:1})
    else:
        if str[5:] in dict:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

a = list(map(int,input().split()))
k = int(a[0])
s = int(a[1])
count = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if(x + y + z == s):
                count += 1

print(count)

### FIXED CODE ###

a = list(map(int,input().split()))
k = int(a[0])
s = int(a[1])
count = 0

for x in range(k+1):
    for y in range(k+1):
        if(s-x-y >= 0) and (s-x-y <= k):
            count += 1
print(count)
### BUGGY CODE ###

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

a = n

while a >= abs(a-k):
    a = abs(a-k)
    
print(a)
    

### FIXED CODE ###

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

print(min(n%k, k - n%k))
### BUGGY CODE ###

n,a=int(input()),list(map(int,input().split()));dp=[[None]*n for _ in range(n)]
for i in range(n):dp[i][i]=a[i]
for j in range(1,n):
  for i in range(n-j):dp[i][j+i]=max(a[i]-dp[i+1][j+i],a[j+i]-dp[i][j+i-1])
print(dp[0][-1])

### FIXED CODE ###

n,a=int(input()),list(map(int,input().split()));dp=[[None]*n for _ in range(n)]
for i in range(n):dp[i][i]=a[i]
for j in range(1,n):
  for i in range(n-j):dp[i][j+i]=max(a[i]-dp[i+1][j+i],a[j+i]-dp[i][j+i-1])
print(dp[0][-1])
### BUGGY CODE ###

k = int(input())
sum = 0

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

def gcd2(a, c):
    while c != 0:
        a, c = c, a % c
        
    return a


for i in range(1, k +1):
    for j in range(1, k +1):
        for k in range(1, k +1):
            sum += gcd2(gcd(i, j), k)
print(sum)

### FIXED CODE ###

k = int(input())
sum = 0

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

def gcd2(a, c):
    while c != 0:
        a, c = c, a % c
        
    return a


for i in range(1, k +1):
    for j in range(1, k +1):
        for k in range(1, k +1):
            sum += gcd2(gcd(i, j), k)
print(sum)