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

import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    s = [int(x) for x in input().split()]
    t = [int(x) for x in input().split()]
    
    mod = pow(10, 9)+7
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    for i in range(m+1):
        dp[0][i] = 1
    
    for i in range(n):
        for j in range(m):
            dp[i+1][j+1] = (dp[i+1][j]+dp[i][j+1]-dp[i][j])%mod
            if s[i] == t[j]:
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= mod
    
    print(dp[n][m])            
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    s = [int(x) for x in input().split()]
    t = [int(x) for x in input().split()]
    
    mod = pow(10, 9)+7
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    for i in range(m+1):
        dp[0][i] = 1
    
    for i in range(n):
        for j in range(m):
            dp[i+1][j+1] = (dp[i+1][j]+dp[i][j+1]-dp[i][j])%mod
            if s[i] == t[j]:
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j+1] %= mod
    
    print(dp[n][m])            
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque
import numpy as np
n,k =map(int,input().split())
A = [int(x)-1  for x in input().split()]
arrive_time = [0]*n
time = 1
done = [A[0]]
arrive_time[A[0]] = time
last = 0
while True:
    v = done[-1]
    if not(A[v] in done):
        done.append(A[v]) 
        time += 1
        arrive_time[A[v]] = time
    else:
        last = A[v]
        break  

if time >= k:
    for i,a in enumerate(arrive_time):
        if a == k:
            print(i+1)
else:
    roop = time - arrive_time[last] + 1
    nokori = (k-arrive_time[last])%roop
    ans = nokori+arrive_time[last]
    for i,a in enumerate(arrive_time):
        if a == ans:
            print(i+1)


### FIXED CODE ###

from collections import deque
import numpy as np
n,k =map(int,input().split())
A = [int(x)-1  for x in input().split()]
arrive_time = [0]*n
time = 1
done = [0]*n
done[A[0]] = 1
arrive_time[A[0]] = time
last = 0
next = A[0]
while True:
    v = next
    if done[A[v]] == 0:
        done[A[v]] = 1 
        time += 1
        arrive_time[A[v]] = time
        next = A[v]
    else:
        last = A[v]
        break  

if time >= k:
    for i,a in enumerate(arrive_time):
        if a == k:
            print(i+1)
else:
    roop = time - arrive_time[last] + 1
    nokori = (k-arrive_time[last])%roop
    ans = nokori+arrive_time[last]
    for i,a in enumerate(arrive_time):
        if a == ans:
            print(i+1)
### BUGGY CODE ###

K,S=map(int,input().split())
ANS=0
for i in range(K+1):
  if i > S:
    break
  for j in range(K+1):
    zz = i + j
    if zz > S:
      break
    for k in range(K+1):
      z = i + j + k
      if z == S:
        #print(i,j,k)
        ANS+=1
      elif z >= S:
        break
print(ANS)

### FIXED CODE ###

K,S=map(int,input().split())
ANS=0
for i in range(K+1):
  if i > S:
    break
  for j in range(K+1):
    z = i + j
    
    if S - z >= 0 and S - z <= K:
      #print(i,j,S-z)
      ANS+=1
    else:
      if S - z <= 0:
      	break
print(ANS)
### BUGGY CODE ###

s=input()
ans=0
while s:
    a=s[0]
    b=s[-1]
    if a==b:
        s=s[1:-1]
        continue
    elif a=="x":
        s=s[1:]
        ans+=1
        continue
    elif b=="x":
        s=s[:-1]
        ans+=1
        continue
    else:
        print(-1)
        exit()

print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
s=input()[:-1]
ans=0
while s:
    a=s[0]
    b=s[-1]
    if a==b:
        s=s[1:-1]
        continue
    elif a=="x":
        s=s[1:]
        ans+=1
        continue
    elif b=="x":
        s=s[:-1]
        ans+=1
        continue
    else:
        print(-1)
        exit()

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

n,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
summ = 0
if k > 0 and k < n:
    for i in range(k):
        del a[0]
elif n <= k:
    a = []
for i in range(len(a)):
    summ += a[i]
print(summ)

### FIXED CODE ###

n,k = map(int,input().split())
a = sorted(list(map(int,input().split())),reverse=True)
summ = 0
if k > 0 and k < n:
    del a[0:k]
elif n <= k:
    a = []
summ = sum(a)
print(summ)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(int(input()) for _ in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
        dp[i]=0
print(dp[n])


### FIXED CODE ###

n,m=map(int,input().split())
a=set(int(input()) for _ in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
        dp[i]=0
print(dp[n])
### BUGGY CODE ###

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

mod = 10**9 + 7

sum = 0
for i in range(N-1):
    for j in range(i+1, N):
        sum += A[i] * A[j] % mod

print(sum % mod)

### FIXED CODE ###

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

sum_A = sum(A)

mod = 10**9 + 7

sum_mod = 0

sum_minus = 0
for a in A:
    sum_mod += a * (sum_A - a - sum_minus) % mod
    sum_minus += a

print(sum_mod % mod)
### BUGGY CODE ###

from collections import Counter
S = str(input())
T = str(input())

for i in range(len(S)+1):
	s = str(S[i:i+1])
	t = str(T[i:i+1])
	S = S.replace(s,'A').replace(t,s).replace('A',t)

answer = 'No'

if S == T:
	answer = 'Yes'
	
print(answer)


### FIXED CODE ###

#coding:utf-8

"""
自分の解答。これだとTLEになってしまったので、復習をします
from collections import Counter
S = str(input())
T = str(input())

for i in range(len(S)+1):
	s = str(S[i:i+1])
	t = str(T[i:i+1])
	S = S.replace(s,'A').replace(t,s).replace('A',t)

answer = 'No'

if S == T:
	answer = 'Yes'
	
print(answer)
"""

"""
対応表を作るイメージ。
azzel→appleにするのには
a a
z p
e i
l e
という変化を回せればおっけー

#初期値-1で、要素26コの対応表をつくる
start = [-1]*26
goal = [-1]*26
print(start)

"""


S = str(input())
T = str(input())

#辞書型を使ってみる。defaultdictは便利らしい。どこがかはちょっとよく分からなかった。
from collections import defaultdict
s = defaultdict(int)
t = defaultdict(int)


for i in S:
	s[i] += 1

for j in T:
	t[j] += 1

#辞書型をソートできるsoted()を使う。
#values()で辞書型のkey valueのvalueだけを取り出している。

ss = sorted(s.values())
tt = sorted(t.values())

if ss == tt:
	print('Yes')
else:
	print('No')
### BUGGY CODE ###

import numpy as np
import heapq

INF=10**12
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
used=np.array([])
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(table[s],s))
used=np.append(used,s)
                
while heap and not(g in used):
    q=heapq.heappop(heap)
    a=q[1]
    used=np.append(used,a)
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if not(p in used):
            table[p]=np.minimum(table[p],table[a]+co)
            heapq.heappush(heap,(table[p],p))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(table[s],s))
                
while heap:
    q=heapq.heappop(heap)
    a=q[1]
    if q[0]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,(table[p],p))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

memo = {}
def permutations(S):
    if len(S) == 1:
        return S
    res = []
    for i, s in enumerate(S):
        L = S[:i] + S[i+1:]
        k = ''.join(L)
        if k in memo:
            P = memo[k]
        else:
            P = permutations(L)
            memo[k] = P
        for p in P:
            res.append(f'{s}{p}')

    return res

if __name__ == '__main__':
    n, l = [int(x) for x in input().split(' ')]
    S = [input() for i in range(0, n)]
    print(min(permutations(S)))
    

### FIXED CODE ###

if __name__ == '__main__':
    n, l = [int(x) for x in input().split(' ')]
    S = [input() for i in range(0, n)]
    print(''.join(sorted(S)))
### BUGGY CODE ###

#coding: UTF-8

prime_number_list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

def is_prime(target_num):
    if target_num in prime_number_list:
        return True
    elif target_num % 2 == 0:
        return False
    for i in range(3, target_num / 2 + 1, 2):
        if target_num % i == 0:
            return False
    return True

def count_prime_numbers(target_num):
    prime_count = 0
    for i in range(2, target_num + 1):
        if is_prime(i):
            prime_count += 1
    return prime_count

while True:
    try:
        input_str = raw_input()
    except EOFError:
        break
    
    print count_prime_numbers(int(input_str))

### FIXED CODE ###

max_n = 999999
prime_list = [1] * (max_n + 1)

# 0, 1は素数ではない
prime_list[0:2] = [0, 0]

# 
for i in range(2, int(max_n**0.5) + 1):
    if prime_list[i] == 1:
        prime_list[i**2::i] = [0] * len(prime_list[i**2::i])

while True:
    try:
        n = int(input())
        print(sum(prime_list[:n + 1]))

    except EOFError:
        break
### BUGGY CODE ###

import numpy as np
N,Q = list(map(int, input().split(" ")))
v_list = np.zeros(N+1, dtype=np.int) # n-1でやること注意
dic_tree = {}
for i in range(N):
    dic_tree[i+1] = [] 

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

# make tree
for k in reversed(range(N)):
    if len(dic_tree) == 0:
        continue
    
    for node in dic_tree[k+1]:
        dic_tree[k+1].extend(dic_tree[node])
        
for i in range(Q):
    p, x = list(map(int, input().split(" ")))
    
    v_list[dic_tree[p]] += x
    v_list[p] += x

print(" ".join(map(str, v_list[1:])))

### FIXED CODE ###

from collections import deque

N,Q = list(map(int, input().split()))
tre = [[] for _ in range(N)]
val = [0] * N
for i in range(N-1):
    a,b = list(map(int, input().split()))
    tre[a-1].append(b-1)
    tre[b-1].append(a-1)

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

stack = deque([0])
visited = [False] * N
visited[0] = True
while stack:
    cur = stack.pop()
    for target in tre[cur]:
        if visited[target]:
            continue
        visited[target] = True
        stack.append(target)
        val[target] += val[cur]

print(*val)
### BUGGY CODE ###

from math import factorial

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

    A.sort()
    n = A[-1]
    maxc = 0
    for r in A[:-1]:
        comb = (factorial(n) // factorial(n - r)) // factorial(r)
        if maxc < comb:
            ans = r
            maxc = comb
    print(n, ans)

main()


### FIXED CODE ###

import bisect

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

    A.sort()
    n = A[-1]
    i = bisect.bisect_left(A, n / 2)
    if n / 2 - A[i-1] <= A[i] - n / 2:
        r = A[i-1]
    else:
        r = A[i]
    print(n, r)

main()
### BUGGY CODE ###

s = int(input())

x1 = 0
y1 = 0

def divisor(n):
    i = 1
    table = []
    while i*i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
            if n//i < 10 ** 9:
                break
        i += 1
    table = list(set(table))
    return table

if s == int(s ** 0.5) ** 2:
    a = int(s**0.5)
    b = int(s**0.5)

else:
    table = divisor(s)
    t = len(table)//2
    a = table[t-1]
    b = table[t]
    
x2 = a
y2 = 0
x3 = 0
y3 = b

print(x1,y1,x2,y2,x3,y3)

### FIXED CODE ###

S = int(input())

M = 10**9
t = (-S) % M  #M - S%M
x = (S + t) // M

answer = [0,0,1,M,x,t]

print(*answer)
### BUGGY CODE ###

import numpy as np

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

for i in range(N):
    B = X.copy()
    B.pop(i)
    print(int(np.median(B)))


### FIXED CODE ###

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

Y = sorted(X)

l = Y[N//2-1]
r = Y[N//2]

for x in X:
    if l >= x:
        print(r)
    else:
        print(l)
### BUGGY CODE ###

n = int(input())
List = list(input())
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):  
        if List[i] != List[j]:
            for k in range(j+1,n):
                if k-j != j-i and  List[k] != List[i] and List[k] != List[j]:
                    ans +=1
                    #print(i,j,k)
print(ans)

### FIXED CODE ###

def main():
    N = int(input())
    S = input()

    rcs = [0] * N
    gcs = [0] * N
    bcs = [0] * N

    for i in range(N):
        if S[i] == 'R':
            rcs[i] = 1
        elif S[i] == 'G':
            gcs[i] = 1
        elif S[i] == 'B':
            bcs[i] = 1

    for i in range(1, N):
        rcs[i] += rcs[i - 1]
        gcs[i] += gcs[i - 1]
        bcs[i] += bcs[i - 1]

    result = 0
    for i in range(N):
        if S[i] == 'R':
            for j in range(i + 1, N):
                if S[j] == 'R':
                    continue
                elif S[j] == 'G':
                    result += bcs[N - 1] - bcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'B':
                        result -= 1
                elif S[j] == 'B':
                    result += gcs[N - 1] - gcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'G':
                        result -= 1
        elif S[i] == 'G':
            for j in range(i + 1, N):
                if S[j] == 'G':
                    continue
                elif S[j] == 'R':
                    result += bcs[N - 1] - bcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'B':
                        result -= 1
                elif S[j] == 'B':
                    result += rcs[N - 1] - rcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'R':
                        result -= 1
        elif S[i] == 'B':
            for j in range(i + 1, N):
                if S[j] == 'B':
                    continue
                elif S[j] == 'R':
                    result += gcs[N - 1] - gcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'G':
                        result -= 1
                elif S[j] == 'G':
                    result += rcs[N - 1] - rcs[j]
                    t = 2 * j - i
                    if t < N and S[t] == 'R':
                        result -= 1
    print(result)


main()
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
Min = min(p)
cnt = 0
for i in range(n):
    l = p[:i+1]
    p_i = p[i]
    if min(l) == p_i:
        cnt += 1
    if p_i == Min:
        break
print(cnt)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = 0
Min = p[0]
for i in range(n):
    if Min >= p[i]:
        cnt += 1
        Min = p[i]
print(cnt)
### BUGGY CODE ###

N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[float('inf')]*(N*1000+1)for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    w,v = wv[i]
    for j in range(N*1000+1):
        if j < v:
            DP[i+1][j] = DP[i][j] 
        else:
            DP[i+1][j] = min(DP[i][j],DP[i][j-v]+w)
for i in range(len(DP[-1])-1,-1,-1):
    if DP[-1][i] <= W:
        print(i)
        break

### FIXED CODE ###

N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[float('inf')]*(N*1000+1)for i in range(N+1)]
DP[0][0] = 0
for i in range(N):
    w,v = wv[i]
    for j in range(N*1000+1):
        if j < v:
            DP[i+1][j] = DP[i][j] 
        else:
            DP[i+1][j] = min(DP[i][j],DP[i][j-v]+w)
for i in range(len(DP[-1])-1,-1,-1):
    if DP[-1][i] <= W:
        print(i)
        break
### BUGGY CODE ###

from sys import stdin

# input
n = int(stdin.readline().rstrip())
s = ["".join(sorted(list(str(input()))) ) for _ in range(n)]
"""
for _ in range(n):
    raw = 
    raw.sort()
    s.append("".join(raw))
"""
c = 0
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        if s[i] == s[j]:
            c += 1
print(c)


### FIXED CODE ###

from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin
 
def main():
    n = int(input())
    S = ["".join(sorted(input())) for _ in range(n)]

    ans = 0
    dd = defaultdict(int)
    for s in S:
        ans += dd[s]
        dd[s] += 1
    print(ans)
 
input = lambda: stdin.readline().rstrip()
main()
### BUGGY CODE ###

import collections
n = int(input())
li = list(map(int,input().split()))
for i in range(n):
  d = collections.Counter(li)
  num = li[i]
  d[num] -= 1
  ans = 0
  for v in d.values():
    v = int(v)
    ans += v*(v-1)//2
  print(ans)

### FIXED CODE ###

import collections
n = int(input())
li = list(map(int,input().split()))
c = collections.Counter(li)
d = c.copy()
ans_1 = 0
for v in d.values():
  v = int(v)
  ans_1 += v*(v-1)//2
for k in li:
  print(ans_1 - (c[k]-1))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
H += 2; W += 2
grid = []
grid.append(["#" * W])
for h in range(H-2):
  grid.append(["#" + input() + "#"])
grid.append(["#" * W])

INF = 10**9
ans = 0
for h in range(1, H-1):
  for w in range(1, W-1):
    m_grid = 0
    if grid[h][0][w]=="#": continue

    dist = [[INF]*W for i in range(H)]
    dist[h][w] = 0 
    q = deque([(h,w)])

    while(q):
      v_h, v_w = q.popleft()
      d_v = dist[v_h][v_w]
      m_grid = max(d_v, m_grid)
      for n_h, n_w in ((v_h, v_w-1),(v_h, v_w+1),(v_h-1, v_w),(v_h+1, v_w)):
        if grid[n_h][0][n_w]=="#": continue
        d_n = d_v + 1
        if d_n > dist[n_h][n_w]:
          continue

        dist[n_h][n_w] = d_n
        q.append((n_h,n_w))
        m_grid = max(d_n, m_grid)

    
    ans = max(ans, m_grid)

print(ans)

      


    


### FIXED CODE ###

from collections import deque
import numpy as np

H,W = map(int,input().split())
maze = [input() for _ in range(H)]

ans = 0
for x in range(H):
    for y in range(W):
        #壁からはスタートできない
        if maze[x][y] == "#":
            continue

        #初期化
        distance = [[0]*W for _ in range(H)]
        #start位置
        stack = deque([[x,y]])

        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == 0:
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])

        #start位置は0で初期化
        distance[x][y] = 0
        ans = max(ans, np.max(distance))

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

import math

n = int(input())
als = list(map(int, input().split()))

sorted(als)

ans = "not coprime"

a, b = als[1], als[0]
while a % b != 0:
    a, b = b, a % b

for i in range(2, n):
    a = als[i]
    while a % b != 0:
        a, b = b, a % b
    if b == 1:
        ans = "setwise coprime"
        break

maxa = max(als)

existeven = False

failed = False

for i in range(n):
    if als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

if not failed:
    for i in range(3, int(math.sqrt(maxa))+1, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j]%i == 0:
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        ans = "pairwise coprime"

print(ans)
        

    

### FIXED CODE ###

import math
from collections import deque

n = int(input())
als = list(map(int, input().split()))

ans = "not coprime"

a, b = als[1], als[0]
if a < b:
    a,b = b,a
while a % b != 0:
    a, b = b, a % b
    if n == 2 and b == 1:
        ans = "pairwise coprime"
        failed = True

for i in range(2, n):
    a = als[i]
    if a < b:
        a,b = b,a 
    while a % b != 0:
        a, b = b, a % b
if b == 1:
    ans = "setwise coprime"
    # break

existeven = False

failed = False

for i in range(n):
    if als[i] >= 2 and als[i]%2 == 0:
        if existeven:
            failed = True
            break
        else:
            existeven = True

maxa = max(als)

afterchecklist = deque([])


if not failed:
    for i in range(3, int(math.sqrt(maxa))+2, 2):
        existfactrial = False
        failed = False
        for j in range(n):
            if als[j] >= i and als[j]%i == 0:
                afterchecklist.append(als[j]/i)
                if existfactrial:
                    failed = True
                    break
                else:
                    existfactrial = True
        if failed:
            break
    if not failed:
        for i in list(afterchecklist):
            existfactrial = False
            failed = False
            for j in range(n):
                if i != 1 and als[j] >= i and als[j]%i == 0:
                    if existfactrial:
                        failed = True
                        break
                    else:
                        existfactrial = True
            if failed:
                break
        if not failed:
            ans = "pairwise coprime"

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

N,K=map(int,input().split())
X=list(map(int,input().split()))+[0]
ans=10**20

for i in range(N-K+1):
    x=X[i:i+K]
    l,r=x[0],x[-1]
    if l<=0 and r<=0:
        ans=min(ans,-l)
    elif l>=0 and r>=0:
        ans=min(ans,r)
    else:
        res=min(abs(l),abs(r))*2+max(abs(l),abs(r))
        ans=min(ans,res)
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
X=list(map(int,input().split()))
ans=float('inf')
for l in range(N-K+1):
    r=l+K-1
    ans=min(ans,min(abs(X[l]),abs(X[r]))+X[r]-X[l])
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop
import itertools
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx,sy,0)]
data+=[tuple(map(int,input().split())) for i in range(n)]
data.append((gx,gy,0))

for i,j in itertools.product(range(n+2), range(n+2)):
    if i>=j:
        continue
    tmp=((data[i][0]-data[j][0])**2+(data[i][1]-data[j][1])**2)**0.5-data[i][2]-data[j][2]
    g[i].append((tmp,j))
    g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))
while que:
    c,v=heappop(que)
    if dist[v]<c:
        continue
    for x in g[v]:
        tmp=(x[0] if not x[0]<0 else 0)+c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])


### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])