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

# N = int(input())
S = input()
Q = int(input())

for i in range(Q):
    t = input().split()
    if t[0] == '1':
        S = S[::-1]
    else:
        if t[1] == '1':
            S = t[2] + S
        else:
            S = S + t[2]

print(S)

### FIXED CODE ###

from collections import deque
# N = int(input())
S = input()
Q = int(input())
T = [input().split() for i in range(Q)]
d = deque(S)
cnt = 0
for i in range(Q):
    if T[i][0] == '1':
        cnt += 1
    else:
        if cnt % 2 == 0:
            if T[i][1] == '1':
                d.appendleft(T[i][2])
            else:
                d.append(T[i][2])
        else:
            if T[i][1] == '2':
                d.appendleft(T[i][2])
            else:
                d.append(T[i][2])
if cnt % 2 == 0:
    print(''.join(d))
else:
    print(''.join(d)[::-1])
### BUGGY CODE ###

def solve():
    N = int(input())
    Ss = input().rstrip()

    for L in reversed(range(1, N//2+1)):
        setCand = set()
        RHs = []
        for i in range(N-L+1):
            if i <= N-2*L or L <= i:
                RH = hash(Ss[i:i+L])
            if i <= N-2*L:
                RHs.append(RH)
            if L <= i:
                setCand.add(RHs[i-L])
                if RH in setCand:
                    print(L)
                    break
        else:
            continue
        break
    else:
        print(0)


solve()


### FIXED CODE ###

N = int(input())
Ss = input()

def isOK(k):
    strAs = ['' for _ in range(N)]
    strBs = ['' for _ in range(N)]
    for L in range(N-k+1):
        R = L+k-1
        ss = Ss[L:R+1]
        strAs[R] = ss
        strBs[L] = ss

    strCands = set()
    for iEn in range(N-1):
        if strAs[iEn] != '':
            strCands.add(strAs[iEn])
        if strBs[iEn+1] != '' and strBs[iEn+1] in strCands:
            return True

    return False


ng, ok = N//2 + 1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

h,n = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(n)]
inf = 1000000000
res = inf
dp = [inf] * (h + 1)
dp[0] = 0
for a,b in lst:
    for j in range(h):
        to = min(j + a,h)
        dp[to] = min(dp[to],dp[j] + b)
print(dp[h])


### FIXED CODE ###

h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)
### BUGGY CODE ###

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

#まとめる
a_set = list(set(a))
a_cnt =[0 for i in range(len(a_set))]
#数えてソートする
for i in range(len(a_set)):
    a_cnt[i] = a.count(a_set[i])
a_cnt.sort() 
#種類の数はa_setの要素数
num_typ = len(a_set)
#数が少ない数値から書き換えていく
if num_typ <= k:
    print(0)
else:
    print(sum(a_cnt[:len(a_cnt)-k]))


### FIXED CODE ###

import collections

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

#数える
a = collections.Counter(a)

#ソートする
a_sort = sorted(a.items(), key=lambda x:x[1])

#必要な分だけ足す
out = 0
if len(a_sort) <= k:
    print(0)
else:
    for i in range(len(a_sort)-k):
        out += a_sort[i][1]
    print(out)
### BUGGY CODE ###

import math
import itertools
import sys
input = sys.stdin.readline


def f(x, y, z):
    return x**2+y**2+z**2+x*y+y*z+z*x


N = int(input())
NL = []

for n in range(1, N+1):
    lim = int(math.sqrt(n)) + 1
    ans = 0
    for x in range(1, lim):
        for y in range(x, lim):
            for z in range(y, lim):
                if f(x, y, z) == n:
                    if len(set([x, y, z])) == 1:
                        ans += 1
                    elif len(set([x, y, z])) == 2:
                        ans += 3
                    else:
                        ans += 6
    print(ans)
# for i in range(1, N):
#     print(NL.count(i))


### FIXED CODE ###

import math
import itertools
import sys
input = sys.stdin.readline


def f(x, y, z):
    return x**2+y**2+z**2+x*y+y*z+z*x


N = int(input())

ans = [0 for _ in range(N)]
lim = 101
for x in range(1, lim):
    for y in range(1, lim):
        for z in range(1, lim):
            A = f(x, y, z)
            if A <= N:
                ans[A-1] += 1
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
n, m = map(int, input().split())

root = [-1]*n

def find(n):
    if root[n] < 0:
        return n
    else:
        return find(root[n])

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    else:
        root[x] += root[y]
        root[y] = x

def size(n):
    return -root[find(n)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)

ans = max(map(size, range(n)))
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
n, m = map(int, input().split())

root = [-1]*n

def r(x):
    if root[x] < 0:
        return x
    else:
        root[x] = r(root[x])
        return root[x]

def unite(x, y):
    x = r(x)
    y = r(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x

def size(x):
    x = r(x)
    return -root[x]

for i in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    unite(x, y)

ans = 0
for i in range(n):
    ans = max(ans, size(i))

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

a, b = map(int, input().split())

xor_sum = a

for i in range(a+1, b+1):
  xor_sum = xor_sum ^ i
  
print(xor_sum)

### FIXED CODE ###

a, b = map(int, input().split())

xor_sum = 0

for i in range(a, a+5): # 123, 124,
  if i % 4 == 0:
    break
  else:
    xor_sum = xor_sum ^ i

for i in range((b-b%4),b+1):#456
  xor_sum = xor_sum ^ i
  
  
print(xor_sum)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
flush = sys.stdout.flush
def query(x):
    print("%d\n" % x)
    flush()
    # ジャッジから返される値を取得
    return readline().strip()


n = int(input())

right = n-1
left = 0

def isok(i):
    if i == "Male":
        return False
    elif i == "Female":
        return True
    else:
        exit(0)

print(0)
flush()
lefti = input()

print(n-1)
flush()
righti = input()

while True:
    mid = left + (right-left)//2
    midi = query(mid)
    if midi == "Vacant":
        exit(0)
    if (lefti == midi and (mid - left) % 2 == 1) or ((lefti != midi) and (mid - left) % 2 == 0):
        righti = midi
        right = mid
    else:
        lefti = midi
        left = mid


### FIXED CODE ###

import sys
readline = sys.stdin.readline
flush = sys.stdout.flush
def query(x):
    print("%d\n" % x)
    flush()
    # ジャッジから返される値を取得
    return readline().strip()


n = int(input())

right = n-1
left = 0

print(0, flush = True)
lefti = input()
if lefti == "Vacant":
    exit(0)
print(n-1, flush = True)
righti = input()
if righti == "Vacant":
    exit(0)

while True:
    mid = left + (right-left)//2
    midi = query(mid)
    if midi == "Vacant":
        exit(0)
    if (lefti == midi and (mid - left) % 2 == 1) or ((lefti != midi) and (mid - left) % 2 == 0):
        righti = midi
        right = mid
    else:
        lefti = midi
        left = mid
### BUGGY CODE ###

#m-solutions2020 c
import sys,math,collections,itertools
input = sys.stdin.readline

N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
ans = 1
for i in range(K):
    ans *= A[i]
pre = ans
for i in range(K,N):
    now = pre * A[i]//A[i-K]
    if now > pre:
        print('Yes')
    else:
        print('No')
    pre = now




### FIXED CODE ###

#m-solutions2020 c
import sys
input = sys.stdin.readline


N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
for i in range(K,N):
    if A[i]>A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
alist = [int(x) for x in input().split()]
attends = [alist.index(y) + 1 for y in sorted(alist)]
print(*attends)


### FIXED CODE ###

n = int(input())
attends = dict(enumerate(list(map(int, input().split())), start=1))
attends_sorted = sorted(attends.items(), key=lambda x: x[1])
arr = [x[0] for x in attends_sorted]
print(*arr)
### BUGGY CODE ###

#整数　a b c d が与えられる。この時a 以上b 以下の整数のうちで、ｃでもdでも割り切れないものの個数を求めてください。
a,b,c,d=map(int,input().split())
num=0
for i in range(a,b+1):
    if i%c==0 or i%d==0:
        num+=0
    else:
        num+=1
print(num)

### FIXED CODE ###

#a以上b以下の整数のうちcでもdでも割り切れないものの個数を求めてください
#1以上b以下の整数の条件を満たすものから1以上a-1以下のもので条件を満たすものを取り除くようにすればいい
import fractions

a,b,c,d=map(int,input().split())
x=c*d//fractions.gcd(c,d)
n=b-((b//c)+(b//d)-b//(x))
m=(a-1)-((a-1)//c+(a-1)//d-(a-1)//(x))
print(n-m)
### BUGGY CODE ###

#import fractions
from itertools import permutations, combinations,combinations_with_replacement,product
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
    
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

def main():
    #n, k = map(int,input().split())
    k = int(input())
    lists = []
    #for i in range(k):
    #    for j in range(k):
    #        for l in range(k):
    #            lists.append((i+1,j+1,l+1))
    for i in range(k):
        lists.append(int(i+1))
        lists.append(int(i+1))
        lists.append(int(i+1))
    
    #for v in combinations_with_replacement(lists,3):
    #    print(v)
    lists = list(combinations_with_replacement(lists,3))
    lists = set(lists)
    #print(lists)
    #lists2 = [i[0]*100+i[1]*10+i[2] for i in lists]
    #print(lists2)
        
    koubai = 0
    for i in lists:
        if len(set(i))==1:
            koubai = koubai + gcd(i[0],i[1],i[2])
            #print(koubai)
        elif len(set(i))==2:
            koubai = koubai + 3*gcd(i[0],i[1],i[2])
        else:
            koubai = koubai + 6*gcd(i[0],i[1],i[2])
            #print(koubai)
    print(koubai)
    



if __name__ == '__main__':
    main()


"""
    grid.append(array)
#print(grid)

for i in grid:
    if len(i)==1:
        s = ''.join(list(reversed(s)))
    else:
        if i[1]=="1":
            s = i[2]+s
        else:
            s = s+i[2]
print(s)

a = array[0]
b = array[1]

min8 = a/0.08
max8 = (a+1)/0.08
min10 = b/0.1
max10 = (b+1)/0.1

def lists(a,b):
    if a%1==0:
        a2 = a
    else:
        a2 = int(a)+1
    if b%1==0:
        b2 = b-1
    else:
        b2 = int(b)
    return np.arange(a2,b2+1)

list8 = lists(min8,max8)
list10 = lists(min10,max10)
#print(list8,list10)
hosii = list(set(list8)&set(list10))
if len(hosii)>0:
    print(int(np.min(hosii)))
else:
    print(-1)


grid = np.array(grid)

N = int(input())
s = [int(input()) for i in range(N)]

for i in s:
    grid = np.where(grid==i,0,grid)
    
print(grid)
    
if grid[0][0]==0 and grid[0][1]==0 and grid[0][2]==0:
    han = "Yes"
elif grid[1][0]==0 and grid[1][1]==0 and grid[1][2]==0:
    han = "Yes"
elif grid[2][0]==0 and grid[2][1]==0 and grid[2][2]==0:
    han = "Yes"
elif grid[0][0]==0 and grid[1][0]==0 and grid[2][0]==0:
    han = "Yes"
elif grid[0][1]==0 and grid[1][1]==0 and grid[2][1]==0:
    han = "Yes"
elif grid[0][2]==0 and grid[1][2]==0 and grid[2][2]==0:
    han = "Yes"
elif grid[0][0]==0 and grid[1][1]==0 and grid[2][2]==0:
    han = "Yes"
elif grid[0][2]==0 and grid[1][1]==0 and grid[2][0]==0:
    han = "Yes"
else:
    han = "No"
print(han)
"""


### FIXED CODE ###

import math

def main():
    #n, k = map(int,input().split())
    k = int(input())
    lists = []
    sum = 0
    for i in range(k):
        for j in range(k):
            for l in range(k):
                sum = sum + math.gcd(math.gcd(i+1 ,j+1), l+1)
    print(sum)

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

import sys
sys.setrecursionlimit(10 ** 7)
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
p, q, r = cnt[1], cnt[2], cnt[3]


def memo_dp(dp_list, i, j, k):
    if (i < 0) or (j < 0) or (k < 0):
        return 0
    if dp_list[i][j][k] != -1:
        return dp_list[i][j][k]
    else:
        pt1 = i * memo_dp(dp_list, i - 1, j, k)
        pt2 = j * memo_dp(dp_list, i + 1, j - 1, k)
        pt3 = k * memo_dp(dp_list, i, j + 1, k - 1)
        dp_list[i][j][k] = (n + pt1 + pt2 + pt3) / (i + j + k)
        return dp_list[i][j][k]


dp = [[[-1] * (301) for _ in range(301)] for _ in range(301)]
dp[0][0][0] = 0

ans = memo_dp(dp, p, q, r)
print(ans)


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = [0,0,0]
for x in LI():
    a[x-1] += 1
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(a[2]+1):
    for j in range(a[1]+a[2]+1):
        for i in range(N+1):
            if not (0 < i+j+k <= N): continue
            x = 0.0
            if i > 0: x += dp[i-1][j][k] * (i/N)
            if j > 0: x += dp[i+1][j-1][k] * (j/N)
            if k > 0: x += dp[i][j+1][k-1] * (k/N)
            x += 1.0
            x *= N / (i+j+k)
            dp[i][j][k] = x
print(dp[a[0]][a[1]][a[2]])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
dp=[[[0] * (302) for i in range(302)] for i in range(302)]

for c in range(C+1):
  for b in range(B+C+1-c):
    for a in range(A+B+C+1-c-b):
      if a == b == c == 0:continue
      result = n
      result += (dp[a-1][b][c]*a if a-1 >= 0 else 0)
      result += (dp[a+1][b-1][c]*b if b-1 >= 0 else 0)
      result += (dp[a][b+1][c-1]*c if c-1 >= 0 else 0)
      dp[a][b][c]=result / (a+b+c)

print(dp[A][B][C])

# def rec (a,b,c):
  # if not (a >= 0 and b >= 0 and c >= 0):
  #   return 0
  # if a == b == c == 0:
  #   return 0
  # if dp[a][b][c] != -1:
  #   return dp[a][b][c]
  # result = n
  # result += rec(a-1,b,c) * a
  # result += rec(a+1,b-1,c) * b
  # result += rec(a,b+1,c-1) * c
  # dp[a][b][c] = result / (a+b+c)
  # return dp[a][b][c]


### FIXED CODE ###

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

S = [0] * 3
for a in A:
  S[a-1] += 1
I, J, K = S

dp = [[[0.0] * (N+1) for j in range(N+1)] for i in range(N+1)]

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

print(dp[I][J][K])
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
  a.append(int(input()))
  
for i in range(n):
  b = a.copy()
  b.remove(b[i])
  print(max(b))
  
  
  
  
  

### FIXED CODE ###

n = int(input())
a = []
x = 0
x_max = 0
for _ in range(n):
  x = int(input())
#  if x_max 
  a.append(x)

b = a.copy()  
b.sort(reverse=True)
a_max1 = b[0]
a_max2 = b[1] 

for i in a:
  if i == a_max1:
    print(a_max2)
  else:
    print(a_max1)
### BUGGY CODE ###

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

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

dp = [0] * (W+1)
for i in range(N):
    for j in range(W, w[i]-1, -1):
        dp[j] = max(dp[j], dp[j-w[i]] + v[i])

print(dp[W])

### FIXED CODE ###

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

dp = [0] * (W+1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        a = dp[j-w]+v
        if dp[j] < a:
            dp[j] = a

print(dp[W])
### BUGGY CODE ###

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == "?":
        for t in range(10):
            for k in range(13):
                dp[i+1][(k*10+t)%13] += dp[i][k]
        for k in range(13):
            dp[i+1][k] %= mod
    else:
        t = int(s[i])
        for k in range(13):
            dp[i+1][(k*10+t)%13] += dp[i][k]
print(dp[n][5])

### FIXED CODE ###

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == "?":
        for t in range(10):
            for k in range(13):
                dp[i+1][(k*10+t)%13] += dp[i][k]
        for k in range(13):
            dp[i+1][k] %= mod
    else:
        t = int(s[i])
        for k in range(13):
            dp[i+1][(k*10+t)%13] += dp[i][k]
print(dp[n][5])
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    w = 0
    e = 0
    r = []
    for i in range(n):
        c = 0
        ls = list(s[0:i])
        rs = list(s[i+1:])
        c += ls.count('W')
        c += rs.count('E')

        r.append(c)
    print(min(r))
main()


### FIXED CODE ###

def main():
    n = int(input())
    s = list(input())
    w = 0
    e = 0
    r = [0]*n
    r[0] = s[1:].count('E')
    for i in range(n-1):
        r[i+1] = r[i]
        if s[i] == 'W':
            r[i+1] += 1
        if s[i+1] == 'E':
            r[i+1] -= 1
    print(min(r))
main()
### BUGGY CODE ###

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

for i in range(M):
  A_max = max(A)
  A[A.index(A_max)] = A_max//2
print(sum(A))

### FIXED CODE ###

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

while M>0:
  A = sorted(A, reverse=True)
  a_ = A[0]//2
  for i,a_i in enumerate(A):
    if a_i > a_ and M>0:
      A[i] = a_i//2
      M -= 1
    else: break
  if a_==0: break
print(sum(A))
### BUGGY CODE ###

n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]

ans = 0
for i in list(set(s)):
  t = s.count(i)
  ans += t*(t-1)//2
print(ans)

### FIXED CODE ###

import collections

n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]

c = collections.Counter(s)

ans = 0
for i in set(s):
  x = c[i]
  ans += x * (x -1)//2
print(ans)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N=int(input())
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    X.append((x,i))
    Y.append((y,i))
X.sort()
Y.sort()
E=[]
ans=0
count=1
for i in range(N-1):
    a=X[i]
    b=X[i+1]
    c=Y[i]
    d=Y[i+1]
    E.extend([(b[0]-a[0],X[i][1],X[i+1][1]),(d[0]-c[0],Y[i][1],Y[i+1][1])])
E.sort()

U=UnionFind(N)
i=0
while(count<N):
    cost,v1,v2=E[i]
    if not U.same_check(v1,v2):
        U.union(v1,v2)
        ans+=cost
        count+=1
    i+=1
print(ans)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
"""
N=int(input())
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    X.append((x,i))
    Y.append((y,i))
X.sort()
Y.sort()
E=[]
ans=0
count=1
for i in range(N-1):
    a=X[i]
    b=X[i+1]
    c=Y[i]
    d=Y[i+1]
    E.extend([(b[0]-a[0],X[i][1],X[i+1][1]),(d[0]-c[0],Y[i][1],Y[i+1][1])])
E.sort()
"""
N = int(input())
P = [[i, list(map(int, input().split()))] for i in range(N)]

X = sorted([[i, xy[0]] for i, xy in P], key=lambda x: x[1])
Y = sorted([[i, xy[1]] for i, xy in P], key=lambda y: y[1])

Xe = [[X[i][0], X[i+1][0], abs(X[i][1]-X[i+1][1])] for i in range(N-1)]
Ye = [[Y[i][0], Y[i+1][0], abs(Y[i][1]-Y[i+1][1])] for i in range(N-1)]
E = sorted(Xe + Ye, key=lambda e: e[2])
U=UnionFind(N)
i=0
ans=0
count=1
while(count<N):
    v1,v2,cost=E[i]
    if not U.same_check(v1,v2):
        U.union(v1,v2)
        ans+=cost
        count+=1
    i+=1
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
#dab={}
lab=[]
for i in range(N):
    a,b=map(int,input().split())
    #dab[a]=b
    lab.append([a,b])
#dab.sort(key=lambda )
lab.sort(key=lambda x:-x[1])
#print("lab",lab)
lsch=[-1]*M#ミスしてた#やっぱおk_どうせM番目には入らない
ans=0
for ab in lab:
    if ab[0]<=M:
        d=M-ab[0]
        #while d>=0:
        for i in range(d,-1,-1):
            if lsch[i]==-1:#whileから書き直したときiではなくdのままにしていた
                lsch[i]=1
                ans+=ab[1]
                #print("ab",ab)
                break
            #d-=1
#print("lsch",lsch)
print(ans)


### FIXED CODE ###

import heapq
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
lab=[]
for i in range(N):
    llab=list(map(int,input().split()))
    lab.append(llab)
lab.sort(key=lambda ab:ab[0])
hq=[]
ind=0
ans=0
#print(lab)
#c=0
for i in range(M):
    if hq:
            ans-=heapq.heappop(hq)
    for j in range(ind,N):
        #if f==0:
        #print(i,j,lab[j][0])
        if lab[j][0]==i+1:
            heapq.heappush(hq,-lab[j][1])#
        else:
            ind=j
            #j=N-1#これダメ、抜けられていない
            break
        #c+=1
    #if hq:
    #        ans-=heapq.heappop(hq)
    #print(hq)
#print(c)
if hq:
    ans-=heapq.heappop(hq)
print(ans)
#for i in range(3):
#    i=3
#    print(12345)
### BUGGY CODE ###

import heapq
import math
from collections import defaultdict
xs, ys, xt, yt = map(int, input().split())
N = int(input())

def constant_factory(value): return lambda: value
minRadiation = defaultdict(constant_factory(10**20))
ToVisit = {(xs, ys, 0), (xt, yt, 0)}
for _ in range(N):
    x, y, r = map(int, input().split())
    ToVisit |= {(x, y, r)}

Q = [(0, xs, ys, 0)]
heapq.heapify(Q)
minRadiation[(xs, ys)] = 0
while Q:
    nowRadiation, nowx, nowy, nowr = heapq.heappop(Q)
    if (nowx, nowy, nowr) in ToVisit:
      ToVisit ^= {(nowx, nowy, nowr)}
      for nextx, nexty, nextr in ToVisit:
          radiationTime = max(0, math.sqrt((nextx-nowx)**2 + (nexty-nowy)**2) - nowr - nextr)
          if minRadiation[(nextx, nexty)] > nowRadiation + radiationTime:
              minRadiation[(nextx, nexty)] = nowRadiation + radiationTime
              heapq.heappush(Q, (nowRadiation + radiationTime, nextx, nexty, nextr))
print(minRadiation[(xt, yt)])

### FIXED CODE ###

import heapq
import math
xs, ys, xt, yt = map(int, input().split())
N = int(input())

Coordinate = {-1: (xs, ys, 0), N:(xt, yt, 0)}
minRadiation = {int(i):10**20 for i in range(-1, N+1)}
ToVisit = {int(i) for i in range(-1, N+1)}
for i in range(N):
    x, y, r = map(int, input().split())
    Coordinate[i] = (x, y, r)

Q = [(0, -1)]
heapq.heapify(Q)
while Q:
    nowRadiation, index = heapq.heappop(Q)
    if index == N:
        print(nowRadiation)
        break
    elif index in ToVisit:
      ToVisit.difference_update({index})
      nowx, nowy, nowr = Coordinate[index]
      for nextIndex in ToVisit:
          nextx, nexty, nextr = Coordinate[nextIndex]
          tempTime = max(0, math.sqrt((nextx-nowx)**2 + (nexty-nowy)**2) - nowr - nextr) + nowRadiation
          if minRadiation[nextIndex] > tempTime:
              minRadiation[nextIndex] = tempTime
              heapq.heappush(Q, (tempTime, nextIndex))