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

import numpy as np
import sys
input = sys.stdin.readline # for speed up

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

c=[0]*n
for ii in np.arange(1,k):
  c[ii]=c[0]+abs(h[ii]-h[0])
  for jj in np.arange(1,ii):
    if c[ii]>c[jj]:
      c[ii]=min(c[ii],c[jj]+abs(h[ii]-h[jj]))
    """
    cjj=c[jj]+abs(h[ii]-h[jj])
    if c[ii]>cjj:
      c[ii]=cjj
    """
"""
c[1]=c[0]+abs(h[1]-h[0])
c[2]=min(c[0]+abs(h[2]-h[0]),c[1]+abs(h[2]-h[1]))
c[3]=min(c[0]+abs(h[3]-h[0]),c[1]+abs(h[3]-h[1]),c[2]+abs(h[3]-h[2]))
"""
for ii in np.arange(k,n):
  c[ii]=c[ii-k]+abs(h[ii]-h[ii-k])
  for jj in np.arange(ii-k+1,ii):
    if c[ii]>c[jj]:
      c[ii]=min(c[ii],c[jj]+abs(h[ii]-h[jj]))
    """
    cjj=c[jj]+abs(h[ii]-h[jj])
    if c[ii]>cjj:
      c[ii]=cjj
	"""
print(c[n-1])

### FIXED CODE ###

import numpy as np
import sys
input=sys.stdin.readline # for speed up

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

c=[0]*n
kn=np.arange(1,k)
h0=h[0]
c0=c[0]
for (ii,hii) in zip(kn,h[1:k]):
  #hii=h[ii]
  cii=c0+abs(hii-h0)
  for (cjj,hjj) in zip(c[1:ii],h[1:ii]):
    if cii>cjj:
      #cii=min(cii,cjj+abs(hii-hjj))
      if hii==hjj:
        #cii=min(cii,cjj)
        cii=cjj
      elif hii>hjj:
        if cii>cjj+hii-hjj:
          cii=cjj+hii-hjj
      elif cii>cjj-hii+hjj:
        cii=cjj-hii+hjj
  c[ii]=cii
"""
c[1]=c[0]+abs(h[1]-h[0])
c[2]=min(c[0]+abs(h[2]-h[0]),c[1]+abs(h[2]-h[1]))
c[3]=min(c[0]+abs(h[3]-h[0]),c[1]+abs(h[3]-h[1]),c[2]+abs(h[3]-h[2]))
"""
#print(c)
kn=np.arange(k,n)
for (ii,hii,hiik) in zip(kn,h[k:n],h[0:n-k]):
  #hii=h[ii]
  cii=c[ii-k]+abs(hii-hiik)
  for (cjj,hjj) in zip(c[ii-k+1:ii],h[ii-k+1:ii]):
    if cii>cjj:
      #cii=min(cii,cjj+abs(hii-hjj))
      if hii==hjj:
        #cii=min(cii,cjj)
        cii=cjj
      elif hii>hjj:
        if cii>cjj+hii-hjj:
          cii=cjj+hii-hjj
      elif cii>cjj-hii+hjj:
        cii=cjj-hii+hjj
  c[ii]=cii
  #print(c)
print(c[n-1])
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

N = int(readline())

total = 0

while N >= 1:
    total += N % 10
    N //= 10

ans = 'Yes' if total % 9 == 0 else 'No'

print(ans)


### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

N = int(readline())
ans = 'Yes' if N%9 == 0 else 'No'

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

a,b=map(int,input().split())
s1=len(bin(a))-2
s2=len(bin(b))-2
sum=a
if s1!=s2:
    for i in range(a+1,2**s1):
        sum=i^sum
    for i in range(2**(s2-1),b+1):
        sum=i^sum
    
else:
    for i in range(a+1,b+1):
        sum=i^sum
print(sum)

### FIXED CODE ###

a,b=map(int,input().split())
a1=a//4+1
b1=b//4
sum=a
k=a+1
while k<a1*4:
    sum=sum^k
    k+=1
k=b1*4
while k<=b:
    sum=sum^k
    k+=1
print(sum)
### BUGGY CODE ###

from operator import itemgetter
from collections import OrderedDict
n, q = [int(el) for el in input().split(' ')]
data = OrderedDict({i:0 for i in range(n,0,-1)})
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a] += v
    print(*max(data.items(), key=itemgetter(1)))

### FIXED CODE ###

n, q = [int(el) for el in input().split(' ')]
data = [0] * n
result, index = 0, 1
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a-1] += v
    if v > 0:
        if result < data[a-1]:
            result, index = data[a-1], a
        elif result == data[a-1]:
            index = min(index, a)
    else:
        if index == a:
            result = max(data)
            index = data.index(result) + 1
    print(index, result)
### BUGGY CODE ###

from bisect import*
def main():
    class BTreeNode:
        def __init__(self):self.key,self.child=[],[]
    root=BTreeNode()
    def search_higher(key):
        ptr=root
        ret=None
        while ptr.child:
            i=bisect(ptr.key,key)
            if i!=len(ptr.key):ret=ptr.key[i]
            ptr=ptr.child[i]
        i=bisect(ptr.key,key)
        if i!=len(ptr.key):ret=ptr.key[i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr.child:
            i=bisect_left(ptr.key,key)
            if i!=0:ret=ptr.key[i-1]
            ptr=ptr.child[i]
        i=bisect_left(ptr.key,key)
        if i!=0:ret=ptr.key[i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=512
        if not ptr.child:
            insort(ptr.key,key)
            if len(ptr.key)==b_size*2-1:
                    ret=BTreeNode()
                    ret.key=ptr.key[:b_size]
                    ptr.key=ptr.key[b_size:]
                    return ret
        else:
            i=bisect(ptr.key,key)
            tmp=insert_rec(ptr.child[i],key)
            if tmp:
                ptr.key.insert(i,tmp.key.pop())
                ptr.child.insert(i,tmp)
                if len(ptr.child)==b_size*2:
                    ret=BTreeNode()
                    ret.child=ptr.child[:b_size]
                    ptr.child=ptr.child[b_size:]
                    ret.key=ptr.key[:b_size]
                    ptr.key=ptr.key[b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root.key,root.child=[tmp.key.pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

import math
def cnt_nCnd(n):
    upper = math.ceil(math.sqrt(n))
    count = 0
    for x in range(1, upper):
        x_double = x**2
        for y in range(x, upper):
            y_double = y**2
            for z in range(y, upper):
                if x_double + y_double + z**2 + x*y + y*z + z*x == n:
                    n_uniq = len(set([x, y, z]))
                    if n_uniq == 1:
                        count += 1
                    elif n_uniq == 2:
                        count += 3
                    elif n_uniq == 3:
                        count += 6
    return count


N = int(input())
for n in range(1, N+1):
    print(cnt_nCnd(n))

### FIXED CODE ###

N = int(input())
a = [0]*10050
for i in range(1,105):
    for j in range(1,105):
        for k in range(1,105):
            v = i*i+j*j+k*k+i*j+i*k+j*k
            if v < 10050:
                a[v-1] += 1
 
for i in range(N):
    print(a[i])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
count=[]
for i in range(n):
  if s[i:i+2]=="AC":count.append(1)
  else:count.append(0)
for i in range(q):
  a,b=map(int,input().split())
  print(count[a-1:b-1].count(1))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
count=[0]
for i in range(n-1):count.append(count[i]+(s[i:i+2]=="AC"))
for i in range(q):
  a,b=map(int,input().split())
  print(count[b-1]-count[a-1])
### BUGGY CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    d = set()
    while num%2==0:
        d.add(2)
        num //= 2
    for i in range(3,int(sqrt(num))+1,2):
        while num%i==0:
            d.add(i)
            num //= i
    if num>2:
        d.add(num)
    return list(d)

n = inp()
x = ip()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        for j in pfact(i):
            if dt[j]:
                dt[j] = 0
            else:
                ans = 'setwise coprime'
                break
print(ans)


### FIXED CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
x.sort(reverse=True)
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)
### BUGGY CODE ###

import collections

input_d1 = int(input()) 
input_d2 = list(input().split())

c = collections.Counter(input_d2)
e = {}

for i in c.keys():
    e[i] = 1 - c[i] + sum(map(lambda x:x*(x-1)/2 , c.values()))

for i in input_d2:
    print(int(e[i]))

### FIXED CODE ###

input_d1 = int(input()) 
input_d2 = list(input().split())

c = sorted(input_d2)
c.append('0')
e = {'0':0}
g = [0]
s = 0

for i in range(0,input_d1):
    if c[i] == c[i+1]:
        pass
    else:
        g.append(i+1)
        e[c[i]] = i + 1 - g[s]
        s += 1

e.pop('0')
d = {}
f = sum(map(lambda x:x*(x-1)/2 , e.values()))

for i in e.keys():
    d[i] = 1 - e[i] + f


for i in input_d2:
    print(int(d[i]))
### BUGGY CODE ###

N = int(input())
"""
a = list(range(1,N+1))
b = list(range(2,N+2))
"""
a = []
b = []
for i in range(N-1):
	a.append(i+1)
	b.append(i+2)
a.append(N)
b.append(1)

sum = 0
for i in range(N):
	sum += a[i]%b[i]
print(sum)




### FIXED CODE ###

import numpy as np
N = int(input())
print((N*(N-1))//2)
### BUGGY CODE ###

word = input().rstrip()
n = int(input())
hanten = 0
lhanten = ""
r = ""
for i in range(n):
    a = input().rstrip().split(" ")
    if a[0] == "1":
        hanten = (hanten + 1) % 2
        # word = word[::-1]
        # print(word)
    else:
        if (a[1] == "2" and hanten == 0) or (a[1] == "1" and hanten == 1):
            r += a[2]
            # print("rtuika")
        else:
            lhanten += a[2]
            # print("ltuika")

if hanten == 0:
    print(lhanten[::-1] + word + r)
else:
    print(r[::-1] + word[::-1] + lhanten)

### FIXED CODE ###

word = input().rstrip()
n = int(input())
hanten = 0
lhantenlist = []
rlist = []
for i in range(n):
    a = input().rstrip().split(" ")
    if a[0] == "1":
        hanten = (hanten + 1) % 2
        # word = word[::-1]
        #print(word)
    else:
        if (a[1] == "2" and hanten == 0) or (a[1] == "1" and hanten == 1):
            rlist.append(a[2])
            #print("rtuika: ",rlist)
        else:
            lhantenlist.append(a[2])
            #print("ltuika: ",lhantenlist)

lhanten="".join(lhantenlist)
r="".join(rlist)

if hanten == 0:
    anslist=[lhanten[::-1],word,r]
    ans="".join(anslist)
else:
    anslist = [r[::-1], word[::-1], lhanten]
    ans="".join(anslist)
print(ans)
### BUGGY CODE ###

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

for i in range(len(list)):
  n=list[i]
  if(list.count(n)!=1):
    print("NO")
    break
  if(i==len(list)-1):
    print("YES")

### FIXED CODE ###

import collections
N=int(input())
list = list(map(int, input().split()))
c = collections.Counter(list)

for i in range(len(list)):
  n=list[i]
  if(c[n]!=1):
    print("NO")
    break
  elif(i==len(list)-1):
    print("YES")
### BUGGY CODE ###

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

### FIXED CODE ###

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

s = list(input())
q = int(input())
q_lists = [input().split() for _ in range(q)]
for i in q_lists:
    if len(i)==1:
        s = s[::-1]
    else:
        f = i[1]
        c = i[2]
        if f=='1':
            s = s[::-1]
            s.append(c)
            s = s[::-1]
        else:
            s.append(c)
        
print(''.join(s))        

### FIXED CODE ###

s = input()
q = int(input())
ans_list1 = []
ans_list2 = []
flag = 1
for i in range(q):
    i = input().split()
    if i[0]=="1":
        flag *= -1
    else:
        if i[1]=='1':
            if flag==1:
                ans_list1.append(i[2])
            else:
                ans_list2.append(i[2])
        else:
            if flag==1:
                ans_list2.append(i[2])
            else:
                ans_list1.append(i[2])

if flag==1:
    print(''.join(ans_list1[::-1]) + s +''.join(ans_list2))
else:
    print(''.join(ans_list2[::-1]) + s[::-1] +''.join(ans_list1))
### BUGGY CODE ###

N=int(input())
A=[]
for x in range(N):
  S=input()
  if S in A:
    pass
  else:  
    A.append(S)
print(len(A))    

### FIXED CODE ###

N=int(input())
d=[]
for x in range(N):
  S=input()
  d.append(S)
print(len(set(d)))
### BUGGY CODE ###

# coding: utf-8
N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))

#print("a", a)

dp = ([0] * N)
dp.append(1)
dp.append(0)
mod = 1000000007

for s in reversed(range(N)):
    if s in a: # xだったら
        if s+1 in a:
            dp[s] = 0 # 2回連続で穴があったら0返して終了
            break
        else:
            dp[s] = 0 # 無を代入
    else: # oだったら
        dp[s] = (dp[s+1] + dp[s+2]) % mod # DP!! DP!!
        
print(dp[0])


### FIXED CODE ###

# coding: utf-8
def main():
    N, M = map(int, input().split())

    a = [True] * (N+1)
    #s = [True for _ in range(N+1)]
    for _ in range(M):
        a[int(input())] = False
    #print(a)
    
    #a = []
    #for i in range(M):
    #    a.append(int(input()))
    
    dp = [0] * (N)
    dp.append(1)
    dp.append(0)
    mod = 10**9 + 7
    
    for s in reversed(range(N)):
        if a[s] == False: # xだったら
            if a[s+1] == False:
                dp[s] = 0 # 2回連続で穴があったら0返して終了
                break
            else:
                dp[s] = 0 # 無を代入
        else: # oだったら
            dp[s] = (dp[s+1] + dp[s+2]) % mod # DP!! DP!!
            
    print(dp[0])

main()
### BUGGY CODE ###

N=int(input())
S=input()

P=[]
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      t=S[i]+S[j]+S[k]
      if not(t in P):
        P.append(t)

print(len(P))


### FIXED CODE ###

N=int(input())
S=list(input())

T=[]
c=0
for i in range(10):
  T=S
  i=str(i)
  if i in T[:N-2]:
    indx_i=T.index(i) 
    for j in range(10):
      j=str(j)
      if j in T[indx_i+1:N-1]:
        indx_j=indx_i+T[indx_i+1:].index(j)+1
        for k in range(10):
          k=str(k)
          if k in T[indx_j+1:]:
            c+=1

print(c)
### BUGGY CODE ###

n,q = map(int,input().split())
parent = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    parent[a].append(b)
    parent[b].append(a)
import queue
check = [0] * n

ans = [0] * n

for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    ans[p] += x

a = ''
qq = queue.Queue()
qq.put(0)
check[0] = 1
while not qq.empty():
    now = qq.get()
    for j, son in enumerate(parent[now]):
        if check[son] == 1:
            continue
        ans[son] += ans[now]
        check[son] = 1
        qq.put(son)
for i in range(n):
    a += str(ans[i]) + ' '
print(a)


### FIXED CODE ###

n,q = map(int,input().split())
parent = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    parent[a].append(b)
    parent[b].append(a)
import collections
check = [0] * n

ans = [0] * n

for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    ans[p] += x

a = ''
qq = collections.deque([0])
check[0] = 1
while len(qq) > 0:
    now = qq.popleft()
    for j, son in enumerate(parent[now]):
        if check[son] == 1:
            continue
        ans[son] += ans[now]
        check[son] = 1
        qq.append(son)
for i in range(n):
    a += str(ans[i]) + ' '
print(a)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, A: "List[int]"):
    stack = [-1]

    for i in range(N):
        for j in range(len(stack)):
            if stack[j] < A[i]:
                stack[j] = A[i]
                break
        else:
            stack.append(A[i])
    
    print(len(stack))
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from bisect import bisect_left

def solve(N: int, A: "List[int]"):
    b = deque([A[0]])
    for a in A[1:]:
        if a <= b[0]:
            b.appendleft(a)
        else:
            idx = bisect_left(b, a)
            b[idx-1] = a
    print(len(b))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

import sys
import heapq


def dfs(u,s,target, vs):
    vs[u] = 1
    if(u == target):
        global h
        heapq.heappush(h,s)
        return
    for j in range(e):
        if(e_1[j] == u):
            if(vs[e_2[j]] != 1):
                count = s + e_w[j]
                dfs(e_2[j],count,target,vs[0:])


v,e,r=map(int, input().split());

vs=[0]*v;

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(v):
    vs[i] = 0;
for i in range(e):
    e_1[i], e_2[i], e_w[i] = map(int, input().split());

for i in range(v):
    h = []
    dfs(r,0,i,vs)
    if(len(h) != 0):
        print(heapq.heappop(h))
    else:
        print("INF")


### FIXED CODE ###

import sys
from collections import deque

v,e,r=map(int, input().split());

edge_info=[0]*v;
for i in range(v):
    edge_info[i] = []

for i in range(e):
    e1, e2, w = map(int, input().split());
    edge_info[e1].append((e2,w))

v_q=deque();

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
v_q.append((0,r))
while(len(v_q) != 0):
    cost,u = v_q.popleft()
    if(cost > d[u]):
        continue
    for j in range(len(edge_info[u])):
        e2,w = edge_info[u][j]
        alt = cost+w
        if(d[e2] > alt):
            d[e2] = alt
            v_q.append((alt,e2))

for i in range(v):
    if(d[i] != INF):
        print(d[i])
    else:
        print("INF")
### BUGGY CODE ###

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


ans = 1
i=2
while(p >= i**n):
	if(p%(i**n)==0):
		ans*=i
		p//=i**n
	else:
		i+=1


print(ans)

### FIXED CODE ###

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


ans = 1
if(n==1):print(p)
else:

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

import sys
input = sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
XY=[]
append=XY.append
for i in range(n):
  x,y=map(int,input().split())
  append([i,x,y])
XY.sort(key=lambda x:x[1])
for i in range(1,n):
  n1,x1,y1=XY[i-1][0],XY[i-1][1],XY[i-1][2]
  n2,x2,y2=XY[i][0],XY[i][1],XY[i][2]
  Edge[n1].append([min(abs(x2-x1),abs(y2-y1)),n2])
  Edge[n2].append([min(abs(x2-x1),abs(y2-y1)),n1])
XY.sort(key=lambda x:x[2])
for i in range(1,n):
  n1,x1,y1=XY[i-1][0],XY[i-1][1],XY[i-1][2]
  n2,x2,y2=XY[i][0],XY[i][1],XY[i][2]
  Edge[n1].append([min(abs(x2-x1),abs(y2-y1)),n2])
  Edge[n2].append([min(abs(x2-x1),abs(y2-y1)),n1])
import heapq
def prim_heap():
  used=[True]*n
  Edgelist=[]
  for e in Edge[0]:
    heapq.heappush(Edgelist,e)
  used[0]=False
  res=0
  while len(Edgelist)!=0:
    minedge=heapq.heappop(Edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    used[v]=False
    for e in Edge[v]:
      if used[e[1]]:
        heapq.heappush(Edgelist,e)
    res+=minedge[0]
  return res
print(prim_heap())

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
XY=[]
append=XY.append
for i in range(n):
  x,y=map(int,input().split())
  append([i,x,y])
XY.sort(key=lambda x:x[1])
for i in range(1,n):
  n1,x1,y1=XY[i-1][0],XY[i-1][1],XY[i-1][2]
  n2,x2,y2=XY[i][0],XY[i][1],XY[i][2]
  Edge[n1].append([min(abs(x2-x1),abs(y2-y1)),n2])
  Edge[n2].append([min(abs(x2-x1),abs(y2-y1)),n1])
XY.sort(key=lambda x:x[2])
for i in range(1,n):
  n1,x1,y1=XY[i-1][0],XY[i-1][1],XY[i-1][2]
  n2,x2,y2=XY[i][0],XY[i][1],XY[i][2]
  Edge[n1].append([min(abs(x2-x1),abs(y2-y1)),n2])
  Edge[n2].append([min(abs(x2-x1),abs(y2-y1)),n1])
import heapq
def prim_heap():
  used=[True]*n
  Edgelist=[]
  for e in Edge[0]:
    heapq.heappush(Edgelist,e)
  used[0]=False
  res=0
  while len(Edgelist)!=0:
    minedge=heapq.heappop(Edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    used[v]=False
    for e in Edge[v]:
      if used[e[1]]:
        heapq.heappush(Edgelist,e)
    res+=minedge[0]
  return res
print(prim_heap())
### BUGGY CODE ###

s = input()

n = len(s)
mod = [int(s[n-i-1:]) % 2019 for i in range(n)]
mod.insert(0, 0)

cnt = n+1 - len(list(set(mod)))

print(cnt)

### FIXED CODE ###

s = input()

MOD = 2019
d = [0] * MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i) * t
    r %= MOD
    t *= 10
    t %= MOD
    d[r] += 1

print(sum(i * (i - 1) // 2 for i in d))
### BUGGY CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(max(0,s-2*k),k+1):
  if x>s:
    break
  for y in range(max(0,s-2*k),k+1):
    if x+y>s:
      break
    if s-(x+y)>=0 and s-(x+y)<=k:
      cnt+=1
print(cnt)


### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
  if s-x<0:
    break
  elif s-x<=k:
    cnt+=(s-x)+1
  elif s-x>2*k:
    cnt+=0
  elif s-x>k:
    cnt+=2*k-(s-x)+1
print(cnt)
### BUGGY CODE ###

import collections
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
S,T=map(int,input().split())
s=S-1
t=T-1
ischecked=[[0]*3 for _ in range(N)]
ischecked[s][0]=1
ans=-1
q=collections.deque()
q.append([s,0])
while q:
    v,c=q.popleft()
    if v==t and c%3==0:
        ans=c//3
        break
    for i in tree[v]:
        if ischecked[i][(c+1)%3]==0:
            q.append([i,c+1])
            ischecked[i][(c+1)%3]==1
print(ans)

### FIXED CODE ###

import collections
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
S,T=map(int,input().split())
s=S-1
t=T-1
ischecked=[[0]*3 for _ in range(N)]
ischecked[s][0]=1
ans=-1
q=collections.deque()
q.append([s,0])
while q:
    v,c=q.popleft()
    if v==t and c%3==0:
        ans=c//3
        break
    for i in tree[v]:
        if ischecked[i][(c+1)%3]==0:
            q.append([i,c+1])
            ischecked[i][(c+1)%3]=1
print(ans)