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

N = int(input())
A = [int(n) for n in input().split()]

for n in range(0, N):
    cnt = 0
    i = 0
    for a in A[i:]:
        i = i + 1
        if n + 1 == a:
            cnt = cnt + 1
        elif n + 1 < a:
            break
    print(A.count(n + 1))

### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = [int(n) for n in input().split()]

d = defaultdict(int)
for i in A:
    d[i-1] += 1
for n in range(N):
    print(d[n])
### BUGGY CODE ###

N = int(input())
num = 1
flag = 0
c=[int(i) for i in input().split()]
for i in c:
    if i == 0:
        flag = 1
        print("0")
if flag == 0:
    for i in c:
        num *= i
    if num > 1000000000000000000:
        print("-1")
    else:
        print(num)

### FIXED CODE ###

N = int(input())
num = 1
flag = 0
c=[int(i) for i in input().split()]
for i in c:
    if i == 0:
        flag = 1
        print("0")
if flag == 0:
    for i in c:
        num *= i
        if num > 1000000000000000000:
            print("-1")
            flag =1
            break
if flag == 0:
    
    print(num)
### BUGGY CODE ###

n = int(input())

A = list(map(int,input().split()))
s = 0
for i in range(n-1):
  if A.count(A[i]) > 1:
    print('NO')
    s = 1
    break
if s == 0:
  print('YES')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = set(a)
         
if len(a) == len(b):
         print('YES')
else:
         print('NO')
### BUGGY CODE ###

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

S = input()

X = [list(map(int,input().split())) for _ in range(Q)]

for i in range(Q):
	count = 0
	for j in range(X[i][0],X[i][1]):
		if S[j-1] == "A" and S[j] == "C":
			count += 1
	print(count)

### FIXED CODE ###

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

S = input()

X = [list(map(int,input().split())) for _ in range(Q)]

count = [0]*len(S)
for i in range(1,len(S)):
	if S[i-1] == "A" and S[i] == "C":
		count[i] = count[i-1] + 1
	else:
		count[i] = count[i-1]
        
for j in range(Q):
	ans = count[X[j][1]-1]-count[X[j][0]-1]
	print(ans)
### BUGGY CODE ###

S=str(input())
S_list=list(S)

Q=int(input())

q=[]
for i in range(Q):
   q.append(input().split())

for i in range(Q):
    if q[i][0]=="1":
        S_list.reverse()
    elif q[i][0]=="2":
        if q[i][1]=="1":
            S_list.reverse()
            S_list.append(q[i][2])
            S_list.reverse()
        elif q[i][1]=="2":
            S_list.append(q[i][2])

S=''.join(S_list)
print(S)

### FIXED CODE ###

S=str(input())
S_list=list(S)

Q=int(input())

q=[]
right=[]
left=[]

rev=1

for i in range(Q):
    q.append(input().split())
    if q[i][0]=="1":
        rev=rev*(-1)
    elif q[i][0]=="2":
        if q[i][1]=="1":
            if rev==1:
                right.append(q[i][2])
            else:
                left.append(q[i][2])
        elif q[i][1]=="2":
            if rev==1:
                left.append(q[i][2])
            else:
                right.append(q[i][2])
right.reverse()
if rev==1:
    S_list=right+S_list+left
else:
    S_list=right+S_list+left
    S_list.reverse()

S=''.join(S_list)
print(S)
### BUGGY CODE ###

power = 1
n = int(input())
tmp = 10 ** 9 + 7

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

print(power % tmp)

### FIXED CODE ###

power = 1
n = int(input())
tmp = 10 ** 9 + 7

for i in range(n):
    power = power * (i + 1) % tmp

print(power)
### BUGGY CODE ###

k,s = map(int,input().split())
c = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                c += 1
print(c)

### FIXED CODE ###

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

N, Q = map(int, input().split())
S = input()
QS = []

# ACがある場所の添字（エンド）
pos = []
last = "x"
for i, si in enumerate(S):
    if last == "A" and si == "C":
        pos.append(i)
    last = si
# print(pos)

for _ in range(Q):
    l, r = map(int, input().split())
    QS.append((l, r))

for l, r in QS:
    start = l - 1
    end = r - 1
    # print(start, end)
    count = 0
    for p in pos:
        if start <= (p - 1) and end >= p:
            count += 1
    print(count)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
QS = []

l = [0, 0]
last = S[0]
for i in range(1, len(S)):
    if last == 'A' and S[i] == 'C':
        l.append(l[-1] + 1)
    else:
        l.append(l[-1])
    last = S[i]

for _ in range(Q):
    left, right = map(int, input().split())
    QS.append((left, right))

# print(l)
for left, right in QS:
    ans = l[right] - l[left]
    print(ans)
### BUGGY CODE ###

import sys
def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)

n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False] * n
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)
flag = 1
tmp = set()
for i in range(n):
  if able[i]:
    tmp.add(i)
while flag ==1:
  flag = 0
  for i in tmp.copy():
    if not able[i]:
      continue
    for k in range(2):
      for j in links[i][k].copy():
        if not able[j]:
          links[i][k].remove(j)
    if (links[i][0] == set() or links[i][1] == set()):
      flag =1
      tmp.remove(i)
      able[i] = False
if any(able):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
s = input()
links = [[] for _ in range(2*n)]
visit = [0] * n *2
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if s[a] == s[b]:
      links[a].append(b+n)
      links[b].append(a+n)
    else:
      links[a+n].append(b)
      links[b+n].append(a)
def dfs(v):
  visit[v] = 1
  for i in links[v]:
    if visit[i] == 1:
      print("Yes")
      exit()
    elif visit[i] == 0:
      dfs(i)
  visit[v] = -1
  
for i in range(n):
  if visit[i] == 0:
    dfs(i)
print("No")
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))
sort_as = sorted(As)
shine = [x + 1 for x in range(N)]
c = 0
s = 0
j = 0
for x in range(N):
  for y in range(len(As)):
    if As[y] < shine[x]:
      continue
    elif shine[x] == As[y]:
      c += 1
    elif shine[x] < As[y]:
      break
  print(c)
  c = 0


### FIXED CODE ###

n = int(input())
As = list(map(int, input().split()))
 
x = [0] * n
for i in As:
    x[i-1] += 1
for y in x:
    print(y)
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

susicount = [0,0,0]
for a in A:
  susicount[a-1] += 1
#print(susicount)

# dp[i][j][k]:寿司3個のお皿がi枚、2個のがj枚、1個がk枚のときの期待値
# dp[i][j][k] = i/N * dp[i-1][j+1][k]
#             + j/N * dp[i][j-1][k+1]
#             + k/N * dp[i][j][k-1]
#             + (N-i-j-k)/N * dp[i][j][k]
#             + 1
# dp[i][j][k]を移項すると、
# dp[i][j][k] = 1/(i+j+k) * (i * dp[i-1][j+1][k]
#                          + j * dp[i][j-1][k+1]
#                          + k * dp[i][j][k-1]
#                          + N)
dp = [[[-1.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]

def rec(i,j,k):
  if i == 0 and j == 0 and k == 0:
    return 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if i != 0:
    res += i * rec(i-1,j+1,k)
  if j != 0:
    res += j * rec(i,j-1,k+1)
  if k != 0:
    res += k * rec(i,j,k-1)
  res = (res+N)/(i+j+k)
  dp[i][j][k] = res
  return res

print(rec(susicount[2],susicount[1],susicount[0]))

### FIXED CODE ###

# 再帰関数を使うとTLEになるので、3重ループにしてみる。
from collections import defaultdict

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

sushi = [0,0,0]
for a in A:
  sushi[a-1] += 1

# dp[i][j][k]:寿司3個のお皿がi枚、2個のがj枚、1個がk枚のときの期待値
# dp[i][j][k] = i/N * dp[i-1][j+1][k]
#             + j/N * dp[i][j-1][k+1]
#             + k/N * dp[i][j][k-1]
#             + (N-i-j-k)/N * dp[i][j][k]
#             + 1
# dp[i][j][k]を移項すると、
# dp[i][j][k] = 1/(i+j+k) * (i * dp[i-1][j+1][k]
#                          + j * dp[i][j-1][k+1]
#                          + k * dp[i][j][k-1]
#                          + N)
dp = [[[0.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)] # 型推論で時間がかからないように0ではなく0.0とする。

for i in range(N+1):
  for j in range(N+1):
    for k in range(N+1):
      if i+j+k > N or i+j+k == 0:
        continue
      if i>0:
        dp[i][j][k] += i * dp[i-1][j+1][k]
      if j>0:
        dp[i][j][k] += j * dp[i][j-1][k+1]
      if k>0:
        dp[i][j][k] += k * dp[i][j][k-1]
      dp[i][j][k] += N
      dp[i][j][k] /= (i+j+k)

print(dp[sushi[2]][sushi[1]][sushi[0]])
### BUGGY CODE ###

from collections import deque

def search(now):   #今いる頂点からけんけんぱでいける点を列挙する
    ret = []
    for v in edge[now]:
        for v2 in edge[v]:
            for v3 in edge[v2]:
                ret.append(v3)
    return list(set(ret))

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    u, v = map(int,input().split())
    edge[u-1].append(v-1)
S,T = map(int,input().split())
S -=1
T -=1

distance = [10**9 for _ in range(N)]
distance[S] = 0

queue = deque([S])
while queue:
    u = queue.popleft()
    for next in search(u):
        if distance[u]+1 < distance[next]:
            distance[next] = distance[u]+1
            queue.append(next)
if distance[T] < 10**9:
    print(distance[T])
else:
    print(-1)

### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
edge = [[] for _ in range(3*N)]
for i in range(M):
    u, v = map(int,input().split())
    for i in range(3):
        edge[i*N + u-1].append(((i+1)%3)*N + (v-1))
S,T = map(int,input().split())
S -=1
T -=1

distance = [10**9 for _ in range(3*N)]
distance[S] = 0

queue = deque([S])
while queue:
    u = queue.popleft()
    for next in edge[u]:
        if distance[u]+1 < distance[next]:
            distance[next] = distance[u]+1
            queue.append(next)
if distance[T] < 10**9:
    print(distance[T]//3)
else:
    print(-1)
### BUGGY CODE ###

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

ans = 1
for i in range(N):
    ans *= A[i]

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

if 0 in A:
    print(0)
    exit()

ans = 1
for i in range(N):
    ans *= A[i]
    if ans > 10**18:
        print(-1)
        break

if ans <= 10**18:
    print(ans)
### BUGGY CODE ###

n, m =map(int, input().split())
a=m//n
c=0
while c==0:
  if(m%a==0):
      c=a
  a=a-1
print(c)

### FIXED CODE ###

n,m=map(int,input().split())
a=1
for i in range(1,min(int(m**0.5),m//n)+1):
    if(m%i==0):
        if(i>=n):
            a=m//i
            break
        else:
            a=i
print(a)
### BUGGY CODE ###

import math
 
s = list(map(str, input().split()))
s = s[0]
n = len(s)

now = 1
amari = []
for i in range(len(s)):
    amari.append(now)
    now = (now * 10) % 13

ans = [[0 for i in range(13)] for j in range(2)]
ans[0][0] = 1
ans[1][0] = 1

for i in range(len(s)):
    now = s[n-1-i]
    ans[(i+1)%2] = [0 for i in range(13)]
    if(now=="?"):
        for k in range(10):
            plus = (amari[i] * k)%13
            for j in range(13):
                ans[(i+1)%2][(j+plus)%13] += ans[i%2][j]
        for j in range(13):
            ans[(i+1)%2][(j+plus)%13] %= 1000000007
    else:
        now = int(now)
        plus = (amari[i] * now)%13
        for j in range(13):
            ans[(i+1)%2][(j+plus)%13] = ans[i%2][j]
            
    last = (i+1)%2
            
print(ans[last][5])


### FIXED CODE ###

import math
 
s = list(map(str, input().split()))
s = s[0]
n = len(s)

now = 1
amari = []
for i in range(len(s)):
    amari.append(now)
    now = (now * 10) % 13

ans = [[0 for i in range(13)] for j in range(2)]
ans[0][0] = 1
ans[1][0] = 1

for i in range(len(s)):
    now = s[n-1-i]
    ans[(i+1)%2] = [0 for i in range(13)]
    if(now=="?"):
        for k in range(10):
            plus = (amari[i] * k)%13
            for j in range(13):
                ans[(i+1)%2][(j+plus)%13] += ans[i%2][j]
        for j in range(13):
            ans[(i+1)%2][(j+plus)%13] %= 1000000007
    else:
        now = int(now)
        plus = (amari[i] * now)%13
        for j in range(13):
            ans[(i+1)%2][(j+plus)%13] = ans[i%2][j]
            
    last = (i+1)%2
            
print(ans[last][5])
### BUGGY CODE ###

K = int(input())
x = 7
count = 1
if K % 2 ==0:
  print("-1")
  exit(0)
for i in range(1000000):
  if x % K == 0:
    print(count)
    exit(0)
  else:
    x = 10*x + 7
    count += 1
print("-1")

### FIXED CODE ###

def calc(k):
    cur = 0
    for i in range(1, 10 ** 7):
        cur *= 10
        cur += 7
        cur %= k
        if cur == 0:
            return i

    return -1


k = int(input())
print(calc(k))
### BUGGY CODE ###

s=input()
l=len(s)
ans=0
for i in range(l-3):
  for j in range(i+3,l):
    if int(s[i:j+1])%2019==0:
      ans+=1
print(ans)

### FIXED CODE ###

def main():
  s=input()[::-1]
  l,mod=len(s),2019
  x=[0]*mod
  x[0]=1
  a,t=0,1
  for i in range(l):
    a = (a + int(s[i])*t) % 2019
    x[a]+=1
    t=(t*10)%mod
  ans=sum([i*(i-1)//2 for i in x])
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

import copy

H, W = map(int, input().split())
A = []
for i in range(H):
    A.append(list(input()))

def become_black(A, i, j):
    return (i != 0 and A[i - 1][j] == '#') \
    or (j != 0 and A[i][j - 1] == '#') \
    or (i != H-1 and A[i + 1][j] == '#') \
    or (j != W-1 and A[i][j+1] == '#')


white_exist = True
counter = 0
while True:
    prev_A = copy.deepcopy(A)
    white_exist = False
    for i in range(H):
        if '.' in A[i]:
            white_exist = True
    if not white_exist:
        break

    for i in range(H):
        for j in range(W):
            if prev_A[i][j] == '.' and become_black(prev_A, i, j):
                A[i][j] = '#'
    counter += 1
print(counter)

### FIXED CODE ###

H, W = map(int, input().split())
INF = H * W
A = [input() for x in range(H)]
used = [[False] * W for x in range(H)]

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append([i, j])
            used[i][j] = True

max_dist = 0
counter = 0
depth = -1
while counter != INF:
    # print(q)
    # print(counter)
    for i in range(len(q) - counter):
        item = q[counter]

        if item[0] > 0 and not used[item[0]-1][item[1]]:
            q.append([item[0] - 1, item[1]])
            used[item[0] - 1][item[1]] = True
        if item[1] > 0 and not used[item[0]][item[1] - 1]:
            q.append([item[0], item[1] - 1])
            used[item[0]][item[1] - 1] = True
        if item[0] < H - 1 and not used[item[0] + 1][item[1]]:
            q.append([item[0] + 1, item[1]])
            used[item[0] + 1][item[1]] = True
        if item[1] < W - 1 and not used[item[0]][item[1] + 1]:
            q.append([item[0], item[1] + 1])
            used[item[0]][item[1] + 1] = True
        counter += 1
    depth += 1

print(depth)
### BUGGY CODE ###

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

evals = []
for i in range(k-1, n, 1):
    eval = scores[i+1-k:i+1]
    sum = 1
    for j in eval:
        sum *= j
    evals.append(sum)

for k in range(1, len(evals), 1):
    print('Yes' if evals[k-1] < evals[k] else 'No')

### FIXED CODE ###

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

evals = []
cnt = 0

for i in range(k, n, 1):
    edge = scores[cnt]
    new_edge = scores[i]
    if edge < new_edge:
        print('Yes')
    else:
        print('No')
    cnt += 1
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall

N,X,Y=map(int,input().split())

edge = [[10**9 for j in range(N)] for i in range(N)]

for i in range(N-1):
  edge[i][i+1] = 1
  edge[i+1][i] = 1

edge[X-1][Y-1] = 1
edge[Y-1][X-1] = 1

G = csgraph_from_dense(edge, null_value=10**9)
d = floyd_warshall(G)
ans = []
for i in d:
  for j in i:
    ans.append(j)

for i in range(1,N):
  print(int(ans.count(i)/2))

### FIXED CODE ###

N,X,Y=map(int,input().split())

ans = [0 for i in range(N+1)]

for i in range(1,N+1):
  for j in range(i+1,N+1):
    if i < X :
      if j < X:
        a = j - i
        ans[a] += 1
      elif j >= X and j < Y:
        a = j - i
        b = (X-i) + 1 + (Y-j)
        c = min(a,b)
        ans[c] += 1
      else:
        a =  (X-i)+ 1 + (j - Y)
        ans[a] += 1
        
    elif i >= X and i < Y:
      if j < Y:
        a = j - i
        b = (i-X) + 1 + (Y-j)
        c = min(a,b)
        ans[c] += 1
      else:
        a = j -i
        b =  (i-X) + 1 + (j - Y)
        c = min(a,b)
        ans[c] += 1
        
    else:
      a = j - i
      ans[a] += 1
        
for i in range(1,N):
  print(int(ans[i]))
### BUGGY CODE ###

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

def fac(n, x):
 fact = 1
 for f in range(n, x+1):
  fact *= f
 return fact

def comb(n, r):
 num = fac(1, r)
 dom = fac(n-r+1, n)
 return dom // num

maxi = a[:2]
for i in a:
 for j in a:
  if i < j: continue
  maxi = (i, j) if comb(*maxi) < comb(i, j) else maxi
print(*maxi)


### FIXED CODE ###

N = int(input())
a = sorted(int(x) for x in input().split())

def hoge(n, r):
 return n * (min(n-r, r))

n = max(a)
ans = (n, a[0])
for i in a[1:]:
 ans = (n, i) if hoge(*ans) < hoge(n, i) else ans
print(*ans)
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    ans += (n//i)*(n//i + 1)/2*i
print(int(ans))
### BUGGY CODE ###

N, M, V, P = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)


def is_possible(idx):
    if idx < P:
        return True
    if A[P - 1] <= A[idx]:
        return True
    if A[idx] + M < A[P - 1]:
        return False
    t = P * M
    for i in range(P - 1, idx):
        t += A[idx] + M - A[i]
    for i in range(idx + 1, N):
        t += M
    if t < M * V:
        return False
    return True


left, right = 0, N
while left + 1 < right:
    middle = (left + right) // 2
    if is_possible(middle):
        assert all(is_possible(i) for i in range(middle))
        left = middle
    else:
        assert all(not is_possible(i) for i in range(middle + 1, right))
        right = middle
print(right)

### FIXED CODE ###

N, M, V, P = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)


def is_possible(idx):
    if idx < P:
        return True
    if A[P - 1] <= A[idx]:
        return True
    if A[idx] + M < A[P - 1]:
        return False
    t = P * M
    for i in range(P - 1, idx):
        t += A[idx] + M - A[i]
    for i in range(idx + 1, N):
        t += M
    if t < M * V:
        return False
    return True


left, right = 0, N
while left + 1 < right:
    middle = (left + right) // 2
    if is_possible(middle):
        left = middle
    else:
        right = middle
print(right)
### BUGGY CODE ###

H,N = [int(i) for i in input().split()]
AB = [[int(i) for i in input().split()] for j in range(N)]
DP = [10000000000]*(H+1)#DP[h] = 体力をh削るのに必要な魔力のmin
DP[0] = 0
for h,curmp in enumerate(DP):
    for a,b in AB:
        goal = min(h+a,H)
        DP[goal] = min(DP[goal],curmp+b)
print(DP[-1])

### FIXED CODE ###

H,N = [int(i) for i in input().split()]
AB = [[int(i) for i in input().split()] for j in range(N)]
DP = [10000000000]*(H+1)#DP[h] = 体力をh削るのに必要な魔力のmin
DP[0] = 0
for h,curmp in enumerate(DP):
    for a,b in AB:
        goal = min(h+a,H)
        DP[goal] = min(DP[goal],curmp+b)
print(DP[-1])
### BUGGY CODE ###

import numpy as np
from functools import lru_cache


@lru_cache(maxsize=40000)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


K = int(input())
total = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            if gcd(i, j) == 1 or gcd(j, k) == 1:
                total += 1
                continue
            total += gcd(gcd(i, j), k)

print(total)


### FIXED CODE ###

import math as f

K = int(input())
total = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        ij = f.gcd(i, j)
        if ij == 1:
            total += K
            continue
        for k in range(1, K + 1):
            total += f.gcd(ij, k)

print(total)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  s = input().rstrip()
  t = input().rstrip()
  ls = len(s)
  lt = len(t)
  dp = [[0]*(lt+1) for _ in range(ls+1)]
  for i in range(ls):
    for j in range(lt):
      if s[i] == t[j]:
        dp[i+1][j+1] = dp[i][j] + 1
      else:
        dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
  ans = ""
  while ls > 0 and lt > 0:
    if dp[ls][lt] == dp[ls-1][lt]:
      ls -= 1
    elif dp[ls][lt] == dp[ls][lt-1]:
      lt -= 1
    else:
      ans = s[ls-1] + ans
      ls -= 1
      lt -= 1
  print(ans)
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = input().rstrip()
t = input().rstrip()
ls = len(s)
lt = len(t)
dp = [[0]*(lt+1) for _ in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
ans = ""
while ls > 0 and lt > 0:
  if dp[ls][lt] == dp[ls-1][lt]:
    ls -= 1
  elif dp[ls][lt] == dp[ls][lt-1]:
    lt -= 1
  else:
    ans = s[ls-1] + ans
    ls -= 1
    lt -= 1
print(ans)
### BUGGY CODE ###

import math
import itertools

N=int(input())

n=math.floor(math.sqrt(N))
l=list(itertools.product(range(n+1),repeat=3))

for n in range(1,N+1):
    ans=0
    for i in range(len(l)):
        x=int(l[i][0])+1
        y=int(l[i][1])+1
        z=int(l[i][2])+1
        if x**2+y**2+z**2+x*y+y*z+z*x==n:
                        ans+=1
    print(ans)

### FIXED CODE ###

n=int(input())
ans=[0 for _ in range(10001)]

for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      v=x*x+y*y+z*z+x*y+y*z+z*x
      if v<10001:
        ans[v]+=1

for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

n,m,k=map(int,input().split())
A=[]
B=[]
for i in range(m):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
C=[]
D=[]
for i in range(k):
    c,d=map(int,input().split())
    C.append(c)
    D.append(d)
union=[]
for i in range(n):
    br=0
    for j in range(len(union)):
        if i+1 in set(union[j]):
            br=1
            break
    if br==1:
        continue
    fri=[i+1]
    mark=[0]
    while 0 in set(mark):
        for s in range(len(fri)):
            if mark[s]==0:
                for t in range(m):
                    if A[t]==fri[s] and B[t] not in set(fri):
                        fri.append(B[t])
                        mark.append(0)
                    if B[t]==fri[s] and A[t] not in set(fri):
                        fri.append(A[t])
                        mark.append(0)
                mark[s]=1
    union.append(fri)
unionsize=[]
for i in range(len(union)):
    unionsize.append(len(union[i]))
counter=[]
for i in range(n):
    counter.append(0)

for i in range(m):
    counter[A[i]-1]+=1
    counter[B[i]-1]+=1
for i in range(k):
    for j in range(len(union)):
        if C[i] in union[j] and D[i] in union[j]:
            counter[C[i]-1]+=1
            counter[D[i]-1]+=1
            break

for i in range(n):
    for j in range(len(union)):
        if i+1 in union[j]:
            print(unionsize[j]-counter[i]-1,end=" ")
            break

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].add(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

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

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    fri[a-1].append(b)
    fri[b-1].append(a)

for i in range(k):
    c,d=map(int,input().split())
    blk[c-1].append(d)
    blk[d-1].append(c)


seen=[0 for i in range(n)]

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append(set())
        dfs(i)
        cnt+=1

seq=[0 for i in range(n)]

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-len(unii&set(blk[j-1]))-1
        seq[j-1]=cj

print(*seq)