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

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

dp = [0] * (n)
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2,n):
    minp = dp[i-1] + abs(h[i]-h[i-1])
    for j in range(1,k+1):

        if i - j < 0:
            break;
        #print(i,j,minp,dp[i-j] + abs(h[i]-h[i-j]))
        minp = min(minp,
                dp[i-j] + abs(h[i]-h[i-j]))
    dp[i] = minp
#print(dp)
print(dp[n-1])


### FIXED CODE ###

import sys
import numpy as np
n,k = map(int,input().split())
h = np.array(list(map(int,sys.stdin.readline().split())))

dp = np.zeros(n, dtype=int)
dp[0] = 0
for i in range(1,n):
    x = max(i-k, 0)
    #dp[i] = min(d + abs(h[i]-hd) for d, hd in zip(dp[x:i], h[x:i]))
    dp[i] = (dp[x:i] + abs(h[i] - h[x:i])).min()
print(dp[-1])
### BUGGY CODE ###

from math import sqrt
n=int(input())
rn=int(sqrt(n))
s=[0]*(rn+1)
s[0]=-1
s[1]=-1
t=[0]*(rn+1)
for i in range(2,rn+1):
    if s[i] != 0:
        continue
    s[i] = i
    j = i
    while j < rn + 1:
        t[j] = 1
        j *= i
        for j in range(i * i, rn + 1,i):
            if s[j] == 0:
                s[j] == i

result = 0
last = -1
for i in range(2,rn+1):
    if t[i] == 0:
        continue
    if n % i == 0:
        result += 1
        n //= i
        last =i
if n != 1 and n > rn:
    result += 1
print(result)

### FIXED CODE ###

from math import sqrt

N = int(input())

rn = int(sqrt(N))
sieve = [0] * (rn + 1)
sieve[0] = -1
sieve[1] = -1
t = [0] * (rn + 1)
for i in range(2, rn + 1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    j = i
    while j < rn + 1:
        t[j] = 1
        j *= i
    for j in range(i * i, rn + 1, i):
        if sieve[j] == 0:
            sieve[j] = i

result = 0
last = -1
for i in range(2, rn + 1):
    if t[i] == 0:
        continue
    if N % i == 0:
        result += 1
        N //= i
        last = i
if N != 1 and N > rn:
    result += 1
print(result)
### BUGGY CODE ###

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

tables = [ [0 for _ in range(n)] for _ in range(n)]

def incl(n):
    return n + 1

for _ in range(m):
    l, r = map(int, input().split())
    for i in range(r - 1, n):
        tables[l - 1][i] += 1

pq = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

for p, q in pq:
    ans = 0
    if p > 0:
        for i in range(p, q + 1):
            ans += tables[i][q] - tables[i][p - 1]
    else:
        for i in range(q + 1):
            ans += tables[i][q]
    print(ans)

### FIXED CODE ###

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

temp = [ [0 for _ in range(n)] for _ in range(n)]
tables = [ [0 for _ in range(n)] for _ in range(n)]

if n == 1:
    print('1')
    exit()

for _ in range(m):
    l, r = map(int, input().split())
    temp[l - 1][r - 1] += 1

pq = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

hoge = 0
for j in range(n):
    hoge += temp[0][j]
    tables[0][j] = hoge

for i in range(1, n):
    hoge = 0
    for j in range(n):
        hoge += temp[i][j]
        tables[i][j] = tables[i - 1][j] + hoge

for p, q in pq:
    if p == 0:
        print(tables[q][q])
    else:
        print(tables[q][q] - tables[p - 1][q] - tables[q][p - 1] + tables[p - 1][p - 1] )
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  h, w = map(int, input().strip().split())
  maze = [list(input().strip()) for _ in range(h)]
  countw = [[0]*w for _ in range(h)]
  counth = [[0]*w for _ in range(h)]
  for i in range(h):
    l=r=0
    for j in range(w):      
      if maze[i][j] == '#':
        l=0
      else:
        l+=1
        countw[i][j] += l
      if maze[i][-(j+1)] == '#':
        r=0
      else:
        r+=1
        countw[i][-(j+1)] += r
        
  for j in range(w):
    t=b=0
    for i in range(h):
      if maze[i][j] == '#':
        t=0
      else:
        t+=1
        counth[i][j] += t
      if maze[-(i+1)][j] == '#':
        b=0
      else:
        b+=1
        counth[-(i+1)][j] += b
    
  max = -1
  for i in range(h):
    for j in range(w):
      score = counth[i][j] + countw[i][j]
      if max < score:
        max = score
  print(max-3)
  
if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  h, w = map(int, input().strip().split())
  maze = [list(input().strip()) for _ in range(h)]
  countw = [[0]*w for _ in range(h)]
  counth = [[0]*w for _ in range(h)]
  for i in range(h):
    l=r=0
    for j in range(w):      
      if maze[i][j] == '#':
        l=0
      else:
        l+=1
        countw[i][j] += l
      if maze[i][-(j+1)] == '#':
        r=0
      else:
        r+=1
        countw[i][-(j+1)] += r
        
  for j in range(w):
    t=b=0
    for i in range(h):
      if maze[i][j] == '#':
        t=0
      else:
        t+=1
        counth[i][j] += t
      if maze[-(i+1)][j] == '#':
        b=0
      else:
        b+=1
        counth[-(i+1)][j] += b
    
  max = -1
  for i in range(h):
    for j in range(w):
      score = counth[i][j] + countw[i][j]
      if max < score:
        max = score
  print(max-3)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

from bisect import bisect_left

N,Q = map(int, input().split())
STX = []
for i in range(N):
  *stx, = list(map(int, input().split()))
  STX.append(stx)
D = []
for i in range(Q):
  D.append(int(input()))

STX = sorted(STX, key=lambda x: x[2])

mask = [-1]*Q
ANS = [-1]*Q

for (s,t,x) in STX:
  s2 = (s - x)
  t2 = (t - x)

  start = bisect_left(D, s2)
  end = bisect_left(D, t2, lo=start)

  #print(start, end, DI)
  while (start < end):
    if (-1 == mask[start]):
      ANS[start] = x
      mask[start] = end
      start += 1
    else:
      start = mask[start]


print(*ANS, sep='\n')


### FIXED CODE ###

import sys
from bisect import bisect_left
input = sys.stdin.readline

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

STX = sorted(STX, key=lambda x: x[2])

MASK = [-1]*Q
ANS = [-1]*Q

for (s,t,x) in STX:
  s2 = (s - x)
  t2 = (t - x)

  start = bisect_left(D, s2)
  end = bisect_left(D, t2, lo=start)

  #print(start, end, DI)
  while (start < end):
    if (-1 == MASK[start]):
      ANS[start] = x
      MASK[start] = end
      start += 1
    else:
      start = MASK[start]


print(*ANS, sep='\n')
### BUGGY CODE ###

n,m = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(m)]
b = []
for i in range(len(a)):
    c = a[i]
    d = list(range(c[0], c[1]))
    b.append(d)

bb = b
e = [0]*(n-1)
h = []
for _ in range(n):
    h.append([])
count = 0
visited = []

for i, name in enumerate(bb):
    #if len(name) == 1:
    #    count += 1
    #    visited.append(i)
    #else:
        for j in name:
            e[j-1] += 1
            h[j-1].append(i)

while e != [0]*(n-1):
    g = e.index(max(e))
    for i in h[g]:
        if i in visited:
            continue
        else:
            this_bb = bb[i]
            visited.append(i)
            for j in bb[i]:
                e[j-1] -= 1
    count += 1

print(count)


### FIXED CODE ###

n, m = map(int, input().split())
box = [list(map(int, input().split())) for i in range(m)]

box = sorted(box, key=lambda x: x[1])
count, cut = 0, 0

for x, y in box:
    if cut <= x:
        count += 1
        cut = y

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

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

x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())

min_x = min(x)
min_y = min(y)
for i in range(n):
    x[i] -= min_x
    y[i] -= min_y

sx = sorted(x)
sy = sorted(y)

if n == k:
    print(sx[n - 1] * sy[n - 1])
    exit()

a = 0
b = 1
ans = sx[n - 1] * sy[n - 1]
temp = 0
for p in range(n):
    for q in range(p + 1, n):
        for a in range(n):
            for b in range(a + 1, n):
                count = 0
                for i in range(n):
                    if sx[a] <= x[i] <= sx[b] and sy[p] <= y[i] <= sy[q]:
                        count += 1
                if count >= k:
                    ans = min(ans, (sx[b] - sx[a]) * (sy[q] - sy[p]))

print(ans)

### FIXED CODE ###

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

x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
for i in range(n):
    x[i], y[i] = map(int, input().split())

min_x = min(x)
min_y = min(y)
for i in range(n):
    x[i] -= min_x
    y[i] -= min_y

sx = sorted(x)
sy = sorted(y)

if n == k:
    print(sx[n - 1] * sy[n - 1])
    exit()

d = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n):
    d[sx.index(x[i]) + 1][sy.index(y[i]) + 1] = 1

for i in range(n + 1):
    for j in range(1, n + 1):
        d[i][j] += d[i][j - 1]

for i in range(n + 1):
    for j in range(1, n + 1):
        d[j][i] += d[j - 1][i]

#sx = [0] + sx
#sy = [0] + sy

a = 0
b = 1
ans = sx[n - 1] * sy[n - 1]
temp = 0
for p in range(n):
    for q in range(p + 1, n):
        for a in range(n):
            for b in range(a + 1, n):
                count = 0
                if d[b + 1][q + 1] - d[b + 1][p] - d[a][q + 1] + d[a][p] >= k:
                    ans = min(ans, (sx[b] - sx[a]) * (sy[q] - sy[p]))

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

N=int(input())
S=input()
S=S+'9'
ans=0
for i in range(N):
    if S[i]=='#' and S[i+1]=='.':
        cntj=0
        for j in range(i,-1,-1):
            if S[j]=='#':
                cntj+=1
            else:
                break
        cntk=0
        for k in range(i+1,N+1):
            if S[k]=='.':
                cntk+=1
            else:
                break
        if cntj >= cntk:
            ans += cntk
            S = S[:i+1]+'#'*cntk+S[i+cntk+1:]
        else:
            ans += cntj
            S = S[:i-cntj+1]+'.'*cntj+S[i+1:]
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
w=s.count('.')
b=0
ans=w
for i in range(n):
    if s[i]=='#':
        b+=1
    else:
        w-=1
    ans=min(ans,w+b)
print(ans)
### BUGGY CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from bisect import bisect


def resolve():
    it = map(int, sys.stdin.read().split())
    N, M, K = next(it), next(it), next(it)

    A = [0] * (N+1)
    B = [0] * (M+1)
    ans = 0
    for i in range(1, N+1):
        A[i] = A[i-1] + next(it)
    for i in range(1, M+1):
        B[i] = B[i-1] + next(it)

    NM = N + M
    for i in range(1, NM+1):
        for j in range(max(0, i-M), min(i, N)+1):
            if A[j] + B[i-j] <= K:
                ans = i
                break
        else:
            break

    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N, M, K = next(it), next(it), next(it)

    A = [0] * (N+1)
    B = [0] * (M+1)
    ans = 0
    for i in range(1, N+1):
        A[i] = A[i-1] + next(it)
    for i in range(1, M+1):
        B[i] = B[i-1] + next(it)

    lo = 0
    hi = 2*(N+M)+1
    while lo < hi:
        mid = (lo+hi)//2
        for j in range(max(0, mid-M), min(mid, N)+1):
            if A[j] + B[mid-j] <= K:
                lo = mid+1
                break
        else:
            hi = mid

    print(lo-1)


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

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

if m > 0:
    aaa = [int(input()) for i in range(m)]
else:
    aaa = set()

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7
 
for i in range(2, n + 1):
    if i in aaa:
        continue
    dp[i] = (dp[i - 2] + dp[i - 1]) % MOD
print(dp[n])

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
s = set(map(int, [input() for _ in range(m)]))
MOD = 10 ** 9 + 7
a = 1 if not 0 in s else 0
b = 1 if not 1 in s else 0
for i in range(2, n + 1):
    if i in s:
        a, b = b, 0
    else:
        a, b = b, (a + b) % MOD
print(b)
### BUGGY CODE ###

R,G,B,N = list(map(int, input().split()))

B,G,R = sorted([R,G,B])

ans = 0
for r in range(N//R + 1):
  for g in range(N//G + 1):
    if r*R + g*G > N:
      break
    if (N - r*R - g*G) % B == 0:
      ans += 1
      
print(ans)


### FIXED CODE ###

R,G,B,N = list(map(int, input().split()))

B,G,R = sorted([R,G,B])

ans = 0
for r in range(N//R + 1):
  for g in range(N//G + 1):
    if r*R + g*G > N:
      break
    if (N - r*R - g*G) % B == 0:
      ans += 1
      
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(map(int,input().split()))
ans = []
for i in range(n):
    ans.append(abs(sum(s[:i]) - sum(s[i:])))
print(min(ans))

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
ans = 2020202020
a = 0
b = sum(s)
for i in range(n):
    a += s[i]
    b -= s[i]
    ans = min(ans,abs(a-b))
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce
n,a,b=map(int,input().split())
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

x=cmb(n,a)+cmb(n,b)
y=pow(2,n)-1
ans=(y-x%(10**9+7))
print(ans)



### FIXED CODE ###

n,a,b=map(int,input().split())
def comb(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

x=pow(2,n,10**9+7)-1
y=comb(n,a)+comb(n,b)
ans=x-y





while ans<0:
          ans+=10**9+7
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.buffer.readline

n,k=map(int,input().split())
dp2=list(map(int,input().split()))
    
k=min(k,41)
for ki in range(1,k+1):
    ims=[0]*(n+1)
    for ni in range(n):
        if ni<dp2[ni]: ims[0]+=1
        else: ims[ni-dp2[ni]]+=1
        if n>ni+dp2[ni]:
            ims[ni+dp2[ni]+1]-=1

    dp2[0]=ims[0]
    for ni in range(1,n):
        dp2[ni]=dp2[ni-1]+ims[ni]
    
print(' '.join(map(str,dp2)))


### FIXED CODE ###

n,k=map(int,input().split())
dp2=list(map(int,input().split()))
    
k=min(k,41)
for ki in range(1,k+1):
    ims=[0]*(n+1)
    for ni in range(n):
        if 0>ni-dp2[ni]:
            ims[0]+=1
        else:
            ims[ni-dp2[ni]]+=1
        if n<ni+dp2[ni]+1:
            ims[n]-=1
        else:
            ims[ni+dp2[ni]+1]-=1

    dp2[0]=ims[0]
    for ni in range(1,n):
        dp2[ni]=dp2[ni-1]+ims[ni]
    
for i in range(n):
    print(dp2[i],end=" ")
print()
### BUGGY CODE ###

def exchange(n, s, d):
  v = n

  for i in range(n // s[0] + 1):
    x0 = n - s[0] * i
    y0 = d[0] * i

    for j in range(x0 // s[1] + 1):
      x1 = x0 - s[1] * j
      y1 = y0 + d[1] * j

      k = x1 // s[2]
      x1 -= s[2] * k
      y1 += d[2] * k

      v = max(x1 + y1, v)

  return v


def main():
  n = int(input())
  a = list(map(int, input().split()))
  b = list(map(int, input().split()))

  n = exchange(n, a, b)
  n = exchange(n, b, a)

  print(n)


if __name__ == '__main__':
  main()


### FIXED CODE ###

def exchange(n, s, d):
  v = [n] * (n + 1)
  r = [(1, 1)] + [(a, b) for a, b in zip(s, d) if a < b]

  for i in range(len(v) - 1):
    for a, b in r:
      if i + a < len(v):
        v[i + a] = max(v[i] - a + b, v[i + a])

  return v[-1]


def main():
  n = int(input())
  a = list(map(int, input().split()))
  b = list(map(int, input().split()))

  n = exchange(n, a, b)
  n = exchange(n, b, a)

  print(n)


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

#####segfunc######
def segfunc(x,y):
    if x == y == None:
        return set()
    if x == None:
        return y
    if y == None:
        return x
    return x | y
def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=set([init_val[i]])   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return set()
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
n = int(input())
s = list(input())
ide_ele = None
num =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
init(s)
for i in range(int(input())):
    a,b,c = input().split()
    if a == "1":
        update(int(b)-1, set([c]))
    else:
        if b == c:
            print(1)
        else:
            print(len(query(int(b)-1,int(c))))

### FIXED CODE ###

import sys
input = sys.stdin.readline
#####segfunc######
def segfunc(x,y):
    return x | y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
n = int(input())
s = list(input())[:-1]
ide_ele = 0
num =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
s = [2 ** (ord(i) - ord('a')) for i in s]
init(s)
q = int(input())
for i in range(q):
    tmp = input()
    a,b,c = tmp[:-1].split()
    if a == "1":
        update(int(b)-1, 2 ** (ord(c) - ord('a')))
    else:
        if b == c:
            print(1)
        else:
            tmp = query(int(b)-1, int(c))
            tmp = format(tmp, 'b')
            print(tmp.count('1'))
### BUGGY CODE ###

k = int(input())
border = 10000
if k < border:
    candidate = 1
    count = 1
    while True:
        if count == k:
            print(candidate)
            break

        candidate += 1
        digits = tuple(int(c) for c in str(candidate))
        for i, d in enumerate(digits[:-1]):
            if abs(d - digits[i + 1]) > 1:
                break
        else:
            count += 1

else:
    candidate = 3234566667
    count = 100000
    while True:
        if count == k:
            print(candidate)
            break

        digits = tuple(int(c) for c in str(candidate))
        for i, d in enumerate(digits[:-1]):
            if abs(d - digits[i + 1]) > 1:
                break
        else:
            count -= 1

        candidate -= 1

# Candidate 100000 -> 3234566667


### FIXED CODE ###

def main():
    k = int(input())
    lunluns = [i for i in range(1, 10)]
    if k <= len(lunluns):
        print(lunluns[k - 1])
        return

    while True:
        if k <= len(lunluns):
            print(lunluns[k - 1])
            return
        k -= len(lunluns)
        olds = lunluns
        lunluns = []
        for old in olds:
            for i in (-1, 0, 1):
                digit_next = old % 10 + i
                if digit_next < 0 or digit_next > 9:
                    continue
                new = old * 10 + digit_next
                lunluns.append(new)


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

# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
e = [[] for _ in range(n+1)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    e[v].append((u,(a,b)))
    e[u].append((v,(a,b)))


inf = 10**18
def dijkstra(s,cu):
    d = [inf]*(n+1)
    d[s] = 0
    q = [s]
    heapq.heapify(q)

    while len(q)>0:
        v = heapq.heappop(q)
        for u,ud in e[v]:
            if d[u]<=d[v]+ud[cu]:
                continue
            d[u] = d[v] + ud[cu]
            heapq.heappush(q, u)
    return d


da = dijkstra(s,0)
db = dijkstra(t,1)
res = [0]*n
res[n-1] = da[n]+db[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], da[i+1]+db[i+1])

x = 10**15
for i in range(n):
    print(x - res[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    g[u].append((v,(a,b)))
    g[v].append((u,(a,b)))

inf = 10**18
def dijkstra(s, currency):
    d = [inf]*(n+1)
    d[s] = 0

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

for r in res:
    print(10**15-r)
### BUGGY CODE ###


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

buka = [0] * N
for i in range(1, N, 1):
    buka[i-1] = A.count(i)

for elem in buka:
    print(f'{elem:1d}', end='\n')

### FIXED CODE ###


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

buka = [str(A.count(i)) for i in range(1, N+1, 1)] # countメソッドのためTLE

print("\n".join(buka))
"""
"""
# sys（入力メイン）-----------------------------------------
import sys
read = sys.stdin.buffer.read # 全読み込み
readline = sys.stdin.buffer.readline # 一行読み込み
readlines = sys.stdin.bufer.readlines # 一行ずつ全読み込み
sys.setrecursionlimit(10**7) # 再帰限界変更（デフォルトは1000）

# 文字列（数値変換も含む）
n = readline().rstrip() # １行に１文字列のみ
lis = readline().rstrip().split() # # １行に複数の文字列

# 数値（文字変換も含む）
n = int(readline().rstrip()) # １行に数値１個のみ
a, b, c = int(readline().rstrip().split()) # １行に複数の数値
lis = [readline().rstrip().split() for _ in range(n)] # １行に複数の数値(m個)かつ、n行続く場合（出力は二次元リスト：[['1', '2'], ['4', '5']]）

-----------------------------------------
"""

import sys
read = sys.stdin.buffer.read # 全読み込み
readline = sys.stdin.buffer.readline # 一行読み込み
readlines = sys.stdin.buffer.readlines # 一行ずつ全読み込み
sys.setrecursionlimit(10**7) # 再帰限界変更（デフォルトは1000）

N = int(readline().rstrip()) 
A = list(map(int,readline().rstrip().split()))

buka=[0]*N

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

L=[str(a) for a in buka]
L="\n".join(L)
print(L)
### BUGGY CODE ###

N = int(input())

def find(x, U, r):
  p = []
  while not x == U[x]:
    p.append(x)
    x = U[x]
  for x_ in p:
    U[x_] == x
  return x
  
def merge(x, y, U, r):
  x = find(x, U, r)
  y = find(y, U, r)
  
  if x == y:
    return False
  #print(x,y, U)
  if r[x] < r[y]:
    x, y = y, x
  U[y] = x
  r[x] = max(r[y]+1, r[x])
  #print(x,y, U)
  return True
  
U = [i for i in range(N)]
r = [0 for _ in range(N)]

B = []
C = []
for i in range(N):
  u, v = map(int, input().split())
  B.append((u, v, i))
  C.append((v, u, i))
B.sort()
C.sort()


#辺の作成
R = []
for i in range(1,N):
  c = B[i][0] - B[i-1][0]
  p1 = B[i][2]
  p2 = B[i-1][2]
  R.append((c, p1, p2))
  R.append((c, p2, p1))
  
  c = C[i][0] - C[i-1][0]
  p1 = C[i][2]
  p2 = C[i-1][2]
  R.append((c, p1, p2))
  R.append((c, p2, p1))
R.sort()

#Union Find:
U = [i for i in range(N)]
r = [0 for _ in range(N)]
#print(U)  
ans = 0
for road in R:
  c = road[0]
  x = road[1]
  y = road[2]
  if merge(x, y, U, r):
    #print(U)  
    ans += c
#print(U)    
print(ans)

### FIXED CODE ###

N = int(input())

def find(x, U, r):
  p = []
  while not x == U[x]:
    p.append(x)
    x = U[x]
  for x_ in p:
    U[x_] == x
  return x
  
def merge(x, y, U, r):
  x = find(x, U, r)
  y = find(y, U, r)
  
  if x == y:
    return False
  #print(x,y, U)
  if r[x] < r[y]:
    x, y = y, x
  U[y] = x
  r[x] = max(r[y]+1, r[x])
  #print(x,y, U)
  return True
  
U = [i for i in range(N)]
r = [0 for _ in range(N)]

B = []
C = []
for i in range(N):
  u, v = map(int, input().split())
  B.append((u, v, i))
  C.append((v, u, i))
B.sort()
C.sort()

#辺の作成
R = []
for i in range(1,N):
  c = B[i][0] - B[i-1][0]
  p1 = B[i][2]
  p2 = B[i-1][2]
  R.append((c, p1, p2))
  
  c = C[i][0] - C[i-1][0]
  p1 = C[i][2]
  p2 = C[i-1][2]
  R.append((c, p1, p2))
R.sort()

#Union Find:
U = [i for i in range(N)]
r = [0 for _ in range(N)]
#print(U)  
ans = 0
for road in R:
  c = road[0]
  x = road[1]
  y = road[2]
  if merge(x, y, U, r):
    #print(U)  
    ans += c
#print(U)    
print(ans)