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

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    B = [0] * N
    for a in A:
        prime_a = prime_fact(a)
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    for i, a in enumerate(A):
        b = 1
        prime_a = prime_fact(a)
        for p, n in L.items():
            prime_a.setdefault(p, 0)
            b *= p ** (n - prime_a[p])
        B[i] = b
    print(sum(B) % MOD)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        for j in range(root+1):
            if n % i == 0 and n != 0:
                cnt += 1
                n = n // i
            else:
                break
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    ans = 0
    l = 1
    for p, n in L.items():
        l = l * pow(p, n, MOD) % MOD

    for i, a in enumerate(A):
        ans += l * pow(a, MOD-2, MOD) % MOD
    print(ans % MOD)



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

from sys import setrecursionlimit
setrecursionlimit(1000000)

def Euclid_algorithm(a:int, b:int)->int:
    if a < b:
        a, b = b, a
    else:
        pass
    if b == 0:
        return a
    else:
        return Euclid_algorithm(b, a % b)

k = int(input())
ans = 0
for h in range(1, k+1):
    for i in range(1, k+1):
        for j in range(1, k+1):
            ans += Euclid_algorithm(h, Euclid_algorithm(i, j))
print(ans)


### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
for h in range(1,k+1):
    for i in range(1, k+1):
        for j in range(1, k+1):
            ans += gcd(h, gcd(i, j))
print(ans)
### BUGGY CODE ###

import sys
n=int(input())
As = list(map(int, input().split()))
ans=1
for val in As:
    if val==0:
        ans=0
        break
    ans=val*ans

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

### FIXED CODE ###

import sys
n=int(input())
As = list(map(int, input().split()))
ans=1
for val in As:
    if val==0:
        ans=0
        break
for val in As:
    if ans==0:
        break
    if val==0:
        ans=0
        break
    ans=val*ans
    if 10**18<ans:
        ans=-1
        break

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

n = int(input())
li = list(map(int,input().split()))
ans =[]
for i in range(n):
    ans.append(str(li.index(i+1)+1))
print(' '.join(ans))

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
li_ans = list(enumerate(li))
li_sorted = sorted(li_ans,key = lambda x :x[1])
ans =[str(x[0]+1) for x in li_sorted]
print(' '.join(ans))
### BUGGY CODE ###

n,k = map(int,input().split())
h = []
for i in range(n):
    h.append(int(input()))
h.sort()
h_max = 0
h_min = 0
r = 0
ans = []
#print(h)
for i in range(r,n):
    h_max = max(h[r:k+r])
    #print(h[r:k])
    h_min = min(h[r:k+r])
    if n - r < k: 
        break
    ans.append(h_max - h_min)
    r += 1
print(min(ans))


### FIXED CODE ###

n,k = map(int,input().split())
h = []
for i in range(n):
    h.append(int(input()))
h.sort()
h_max = 0
h_min = 0
r = 0
ans = []
#print(h)
for i in range(r,n-k+1):
    if n - r < k: 
        break
    h_max = h[r+k-1]
    #print(h[r:k])
    h_min = h[r]
    ans.append(h_max - h_min)
    r += 1
print(min(ans))
### BUGGY CODE ###

import itertools,math
n=input().split()
n=[int(i) for i in n]
h=[]
for i in range(n[0]):
    h.append(int(input()))
q=-1

for j in itertools.combinations(h,n[1]):
    if q>max(j)-min(j) or q==-1:
        q=max(j)-min(j)

print(q)

### FIXED CODE ###

n=input().split()
n=[int(i) for i in n]
h=[0]*n[0]
for i in range(n[0]):
    h[i]=int(input())
h.sort()
q=-1
for i in range(0,len(h)-n[1]+1):
    a=h[i+n[1]-1]-h[i]
    if q==-1 or q>a:
        q=a
print(q)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 10**10

for i in range(1, N):
    x = sum(a[:i])
    y = sum(a[i:])
    check = abs(x - y)
    if ans > check:
        ans = check

print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 10**10

for i in range(1, N):
    if i == 1:
        x = sum(a[:i])
        y = sum(a[i:])
    else:
        x += a[i-1]
        y -= a[i-1]
    check = abs(x - y)
    if ans > check:
        ans = check

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

A, B , C , D = map(int, input().split())
count= 0
for i in range(A, B+1):
    if i % C != 0 and i % D != 0:
         count += 1
print(count)


### FIXED CODE ###

import fractions
A, B , C , D = map(int, input().split())

bc = B // C 
bd = B // D
bcd = B // (C*D//fractions.gcd(C, D))
ans = B- (bc + bd - bcd)
ac = (A-1) // C
ad = (A-1) // D
acd = (A-1) //(C*D//fractions.gcd(C, D))
ans2=  A-1 - (ac + ad - acd)
ans = ans - ans2
print(ans)
### BUGGY CODE ###

import math
import statistics
a=int(input())
#b,c=int(input()),int(input())
# c=[]
# for i in b:
#     c.append(i)
#e1,e2 = map(int,input().split())
# f = list(map(int,input().split()))
j = [input() for _ in range(a)]
# h = []
# for i in range(e1):
#     h.append(list(map(int,input().split())))
s=set(j)
s2=list(s)
s3=sorted(s2)
an = []
for i in s3:
    an.append(j.count(i))
s4=[i for i, v in enumerate(an) if v == max(an)]
for i in s4:
    print(s3[i])

### FIXED CODE ###

import math
import statistics
import collections
a=int(input())
#b,c=int(input()),int(input())
# c=[]
#  for i in b:
#     c.append(i)
#e1,e2 = map(int,input().split())
# f = list(map(int,input().split()))
g = [input() for _ in range(a)]
# h = []
# for i in range(e1):
#     h.append(list(map(int,input().split())))

g.sort()

ma=0
count=1
#最大値求める
for i in range(a-1):
    if g[i]==g[i+1]:
        count+=1
    else:
        ma=max(ma,count)
        count=1

ma=max(ma,count)
count=1
ans=[]
#最大値の位置
for i in range(a-1):
    if g[i]==g[i+1]:
        count+=1
    else:
        if count==ma:
            ans.append(g[i])
        count=1
if count==ma:
    ans.append(g[-1])

for i in ans:
    print(i)
### BUGGY CODE ###

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

for i in range(1,n+1):
  for x in range(1,101):
    for y in range(1,101):
      for z in range(1,101):
        if x**2+y**2+z**2+x*y+y*z+z*x == i:
          
          ans[i-1]+=1
          
for i in ans:
  print(i)

### FIXED CODE ###

n = int(input())
ans = [0 for i in range(10001)]
for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      v = x**2+y**2+z**2+x*y+y*z+z*x
      if v<=10000:
        ans[v]+=1
for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

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

if N == 1:
    print(1)
elif N == 2:
    print(1)
else:
    cnt = 0
    for i in range(N - 1):
        if A[i] == A[i + 1]:
            A[i] = '#'
            cnt += 1

    for _ in range(cnt):
        A.remove('#')
    #print(A)

    i = 1
    ans = 1
    while i < len(A) - 1:
        if A[i-1] < A[i] < A[i+1] or A[i-1] > A[i] > A[i+1]:
            pass
        else:
            i += 1
            ans += 1
        i += 1
    print(ans)



### FIXED CODE ###

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

if N == 1:
    print(1)
elif N == 2:
    print(1)
else:
    A = [B[0]]
    cnt = 0
    for i in range(N - 1):
        if B[i] == B[i + 1]:
            pass
        else:
            A.append(B[i+1])

    i = 1
    ans = 1
    n = len(A)
    while i < n - 1:
        if A[i-1] < A[i] < A[i+1] or A[i-1] > A[i] > A[i+1]:
            pass
        else:
            i += 1
            ans += 1
        i += 1
    print(ans)
### BUGGY CODE ###

N = int(input())
S = []
S.append(input())
Triger = 0
temp = ""
for i in range(N-1):
  temp = input()
  for j in S:
    if j == temp:
      Triger += 1
      break
  if Triger == 0:
    S.append(temp)
  else:
    Triger = 0
print(len(S))

### FIXED CODE ###

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

for i in range(N):
  S.append(input())
S= set(S)
print(len(S))
### BUGGY CODE ###

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

for num in range(x):
    print(A.count(num+1))

### FIXED CODE ###

import numpy as np

x = int(input())
l = [0] * x
A = list(map(int, input().split()))

for num in range(x-1):
    l[A[num]-1] += 1

for i in range(x):
    print(l[i])
### BUGGY CODE ###

# -*- coding:utf-8 -*-

def solve():
    N = int(input())

    L0 = 2
    L1 = 1
    i = 2
    while True:
        ans = L0 + L1

        if i == N:
            break
        
        L0 = L1
        L1 = ans

    print(ans)
    
if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-

def solve():
    N = int(input())

    if N == 1:
        print(1)
        return

    L0 = 2
    L1 = 1
    i = 2
    while True:
        ans = L0 + L1

        if i == N:
            break
        
        L0 = L1
        L1 = ans
        i += 1

    print(ans)

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

import queue


def integer_cards(N: int, M: int, A: list, queries: list)->int:
    que = queue.PriorityQueue()

    for a in A:
        que.put(a)

    for B, C in queries:
        for _ in range(B):
            x = que.get()

            que.put(max(x, C))

    res = 0
    for _ in range(N):
        res += que.get()
    return res


if __name__ == "__main__":
    M = 0

    N, M = map(int, input().split())
    A = [int(s) for s in input().split()]
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]

    ans = integer_cards(N, M, A, queries)
    print(ans)


### FIXED CODE ###

import queue


def integer_cards(N: int, M: int, A: list, queries: list)->int:
    que = queue.PriorityQueue()

    for a in A:
        que.put(a)

    queries.sort(key=lambda x: -x[1])

    for B, C in queries:
        x = que.get()
        que.put(x)

        if C <= x:
            break

        for _ in range(B):
            x = que.get()

            que.put(max(x, C))

            if C <= x:
                break

    res = 0
    for _ in range(N):
        res += que.get()
    return res


if __name__ == "__main__":
    M = 0

    N, M = map(int, input().split())
    A = [int(s) for s in input().split()]
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]

    ans = integer_cards(N, M, A, queries)
    print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

count = 0

for i in range(n-3):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        for k in range(j+1, n):
            if s[i] == s[k] or s[j] == s[k]:
                continue
            else:
                if j - i == k - j:
                    continue
                else:
                    count += 1

print(count)


### FIXED CODE ###

n = int(input())
s = input()

nr = s.count("R")
ng = s.count("G")
nb = s.count("B")

count = nr * ng * nb

for i in range(n-2):
    for j in range(i+1, (n+i+1)//2):
        if s[i] == s[j]:continue
        else:
            k = 2*j - i # k - j = j - i
            if s[i] == s[k]:continue
            if s[j] == s[k]:continue
            count -= 1

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

def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

import itertools
N, M, R = map(int,input().split())
r = list(map(int,input().split()))
A=[[float("inf") for i in range(N)] for j in range(N)]
for m in range(M):
  a, b, c = map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c
A = Warshall_Floyd(A,N)

ans = float("inf")
for road in list(itertools.permutations(r)):
  length = 0
  for i in range(R-1):
    length += A[road[i]-1][road[i+1]-1]
  ans = min(ans, length)
print(ans)

### FIXED CODE ###

def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

import itertools
N, M, R = map(int,input().split())
r = list(map(int,input().split()))
A=[[float("inf") for i in range(N)] for j in range(N)]
for m in range(M):
  a, b, c = map(int,input().split())
  A[a-1][b-1] = c
  A[b-1][a-1] = c
A = Warshall_Floyd(A,N)

ans = float("inf")
for road in list(itertools.permutations(r)):
  length = 0
  for i in range(R-1):
    length += A[road[i]-1][road[i+1]-1]
  ans = min(ans, length)
print(ans)
### BUGGY CODE ###

from collections import deque
import sys

N,M,P = map(int,input().split())

flag = [ [False] * N for i in range(N) ]
crash = [False] * N
cost = [float("-inf")] * N
cost[0] = 0

dic = {}
for i in range(N):
    dic[i] = []

    

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    dic[A].append([B,C-P])

q = deque([0])

cnt = 0

while len(q) > 0:

    now = q.popleft()

    for bc in dic[now]:
    
        b = bc[0]
        c = bc[1]

        #print (now,b,flag[now],crash[now],flag[b],crash[b])

        if b == N-1 and crash[now]:
            print (-1)
            sys.exit()

        if cost[now] + c > cost[b]:


            if flag[now][b] and not crash[b]:

                crash[b] = True

                cost[b] = cost[now] + c

                for j in range(N):

                    flag[b][j] = flag[now][j]
                flag[b][b] = True
            
                q.append(b)

            elif not flag[now][b]:
                
                cost[b] = cost[now] + c
                crash[b] = crash[now]
                cost[b] = cost[now] + c
                crash[b] = crash[now]

                for j in range(N):

                    flag[b][j] = flag[now][j]
                    
                flag[b][b] = True

                q.append(b)

    cnt += 1

    if cnt > M * N:
        print (-1)
        sys.exit()

print (max(0,cost[N-1]))
    


### FIXED CODE ###


"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

import sys
sys.setrecursionlimit(200000)

N,M,P = map(int,input().split())

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
if X>Y and X>Z:
  X,Z=Z,X
  A,C=C,A
elif Y>X and Y>Z:
  Y,Z=Z,Y
  B,C=C,Y
C=sorted(C,reverse=True)
k=min(K,X*Y)
AB=sorted([a+b for a in A for b in B],reverse=True)[:k]
ABC=sorted([ab+c for ab in AB for c in C[:K]],reverse=True)[:K]
for x in ABC:
  print(x)


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
B=sorted(list(map(int,input().split())),reverse=True)
C=sorted(list(map(int,input().split())),reverse=True)
ans=[]
for i in range(X):
  if i+1>K:
    break
  for j in range(Y):
    if (i+1)*(j+1)>K:
      break
    for k in range(Z):
      if (i+1)*(j+1)*(k+1)>K:
        break
      ans.append(A[i]+B[j]+C[k])
ans=sorted(ans,reverse=True)
for a in ans[:K]:
  print(a)
### BUGGY CODE ###

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n-1)]
m = int(input())
uv = [list(map(int,input().split())) for _ in range(m)]

from collections import deque

links = [[] for _ in range(n+1)]
for ind,val in enumerate(ab):
    a,b = val
    links[a].append((ind,b))
    links[b].append((ind,a))

def bfs(start,end):
    parent = [[-1,-1] for _ in range(n+1)]
    d = deque()
    d.append(start)
    done = set()
    while(d):
        tmp = d.popleft()
        done.add(tmp)
        for i in links[tmp]:
            link_ind, j = i
            if(not j in done):
                parent[j] = [tmp,link_ind]
                d.append(j)
    route = []
    while(True):
        route.append(parent[end][1])
        end = parent[end][0]
        if(end == start):
            break
    return route[::-1]

links_key = [0] * (n-1)
for i,se in enumerate(uv):
    start,end = se
    route = bfs(start,end)
    for j in route:
        links_key[j] =(links_key[j] | 1<<i)

dp = [[0] * (2**m) for _ in range(n)]
dp[0][0] = 1

for i in range(n-1):
     for j in range(2**m):
         dp[i+1][j] += dp[i][j]
         dp[i+1][(j|links_key[i])] += dp[i][j]

print(dp[-1][-1])

### FIXED CODE ###

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n-1)]
m = int(input())
uv = [list(map(int,input().split())) for _ in range(m)]

from collections import deque

links = [[] for _ in range(n+1)]
for ind,val in enumerate(ab):
    a,b = val
    links[a].append((ind,b))
    links[b].append((ind,a))

def bfs(start,end):
    parent = [[-1,-1] for _ in range(n+1)]
    d = deque()
    d.append(start)
    done = set()
    while(d):
        tmp = d.popleft()
        done.add(tmp)
        for i in links[tmp]:
            link_ind, j = i
            if(not j in done):
                parent[j] = [tmp,link_ind]
                d.append(j)
    route = []
    while(True):
        route.append(parent[end][1])
        end = parent[end][0]
        if(end == start):
            break
    return route[::-1]

links_key = [0] * (n-1)
for i,se in enumerate(uv):
    start,end = se
    route = bfs(start,end)
    for j in route:
        links_key[j] =(links_key[j] | 1<<i)

dp = [[0] * (2**m) for _ in range(n)]
dp[0][0] = 1

for i in range(n-1):
     for j in range(2**m):
         dp[i+1][j] += dp[i][j]
         dp[i+1][(j|links_key[i])] += dp[i][j]

print(dp[-1][-1])
### BUGGY CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
s = input()
ans = 0
for i in range(q):
    l, r = map(int, input().split())
    print(s[l-1:r].count('AC'))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, q = map(int, input().split())
s = input()
memo = [0] * n
cnt = 0

for i in range(1, n):
    if s[i - 1] == 'A' and s[i] == 'C':
        cnt += 1
    memo[i] = cnt

for i in range(q):
    l, r = map(int, input().split())
    print(memo[r - 1] - memo[l - 1])
### BUGGY CODE ###

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

tree = {}

tmp = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
will_go = [0]
already = []
while will_go:
  now = will_go.pop()
  already.append(now)
  for node in tmp:
    if (now == node[0]) & (node[1] not in already):
      will_go.append(node[1])
      if now not in tree:
        tree[now] = [node[1]]
      else:
        tree[now].append(node[1])
    if (now == node[1]) & (node[0] not in already):
      will_go.append(node[0])
      if now not in tree:
        tree[now] = [node[0]]
      else:
        tree[now].append(node[0])

ans = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    if now in tree:
      for root in tree[now]:
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)

### FIXED CODE ###

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

tree = {}
for _ in range(n-1):
  a , b = map(lambda x:int(x)-1, input().split())
  if a not in tree:
    tree[a] = [b]
  else:
    tree[a].append(b)
  if b not in tree:
    tree[b] = [a]
  else:
    tree[b].append(a)

ans = [0]*n
ald = [True]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
ald[0] = False
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    for root in tree[now]:
      if ald[root]:
        ald[root] = False
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = str(input())
W = []
L = []
R = []
for q in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

for s in S:
    W.append(s)

for n in range(N-1):
    if W[n] == 'A' and W[n+1] == 'C':
        W[n] = 'x'

for q in range(Q):
    print(W[L[q]-1:R[q]-1].count('x'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
W = [0] * (N+1)
L = []
R = []
for q in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

for n in range(N-1):
    W[n+1] = W[n] + (1 if S[n:n+2] == 'AC' else 0)    

for q in range(Q):
    print(W[R[q]-1]-W[L[q]-1])
### BUGGY CODE ###

import math
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(graph: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    inf = 3 * 10 ** 9
    dist = [inf] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
circles = [(xs, ys, 0), (xt, yt, 0)] + [tuple(map(int, input().split())) for i in range(n)]
n += 2

edges = [[] for i in range(n)]
for i in range(n):
    for j in range(i+1, n):
        dist = math.sqrt((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2)
        cost = max(0, dist - circles[i][2] - circles[j][2])
        edges[i].append((cost, j))
        edges[j].append((cost, i))


dist = dijkstra(edges, n, 0)

print(dist[1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

def dijkstra(edge_adj: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    inf = 3 * 10 ** 9
    dist = [inf] * node
    used = [False] * node

    dist[start] = 0
    while True:
        v = -1
        for i in range(node):
            if not used[i] and (v == -1 or dist[v] > dist[i]):
                v = i

        if v == -1:
            break

        used[v] = True
        for i in range(node):
            if dist[i] > dist[v] + edge_adj[v][i]:
                dist[i] = dist[v] + edge_adj[v][i]

    return dist
    # dist = [costs to nodes]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
circles = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
    circles.append(tuple(map(int, input().split())))
n += 2

edges = [[0] * n for i in range(n)]
for i in range(n):
    for j in range(i+1, n):
        dist = ((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2) ** 0.5
        cost = max(0, dist - circles[i][2] - circles[j][2])
        edges[i][j] = cost
        edges[j][i] = cost


dist = dijkstra(edges, n, 0)

print(dist[1])