Harryxun/stf_run huggingface dataset:
T = list(input())

if T[0] == '?':
    if T[1] == 'D' or T[1] == '?':
        T[0] = 'P'
    if T[1] == 'P':
        T[0] = 'D'

for i in range(len(T)-1):
    if T[i] == '?':
        if T[i+1] == 'D' and T[i-1] == 'P':
            T[i] = 'D'
        if T[i+1] == 'D' and T[i-1] == 'D':
            T[i] = 'P'
        if T[i+1] == 'P':
            T[i] = 'D'
        if T[i+1] == '?' and T[i-1] == 'P':
            T[i] = 'D'
        if T[i+1] == '?' and T[i-1] == 'D':
            T[i] = 'P'

if T[-1] == '?':
    T[-1] = 'D'

ans = ''.join(T)
print(ans)

### FIXED CODE ###

T = list(input())

if len(T) == 1:
    if T[0] == '?':
        T[0] = 'D'

else:
    if T[0] == '?':
        if T[1] == 'D' or T[1] == '?':
            T[0] = 'P'
        if T[1] == 'P':
            T[0] = 'D'

    for i in range(len(T)-1):
        if T[i] == '?':
            if T[i+1] == 'D' and T[i-1] == 'P':
                T[i] = 'D'
            if T[i+1] == 'D' and T[i-1] == 'D':
                T[i] = 'P'
            if T[i+1] == 'P':
                T[i] = 'D'
            if T[i+1] == '?' and T[i-1] == 'P':
                T[i] = 'D'
            if T[i+1] == '?' and T[i-1] == 'D':
                T[i] = 'P'

    if T[-1] == '?':
        T[-1] = 'D'

ans = ''.join(T)
print(ans)
def judge(S):
    li = list(S)
    count = 0
    for num in range(1):
        if li[num] == "R" and li[num+1] == "R" :
            count = count + 1
    print(count)

judge(S)

### FIXED CODE ###

S = input()
li = list(S)
count = 0
re_num = 0
for num in range(3):
    if li[num] == "R" :
        count = count + 1

if count == 0 :
    re_num = 0
elif count == 1 :
    re_num = 1
elif count == 2 and li[1] == "S" :
    re_num = 1
elif count == 2 and li[1] == "R" :
    re_num = 2
else :
    re_num = 3

print(re_num)
N = int(input())
a = []
hist = []
for i in range(N):
    a.appnd(int(input()))
pos = 0
count = 0
while True:
    if pos+1 in hist:
        print(-1)
        break
    hist.append(a[pos])
    pos = a[pos]-1
    count += 1
    if pos == 1:
        print(count)
        break


### FIXED CODE ###

N = int(input())
a = [int(input()) for i in range(N)]
ans = 0
turn = 1
while True:
    if a[turn-1] == 2:
        ans += 1
        break
    if a[turn-1] == 0:
        ans = -1
        break
    next_turn = a[turn-1]
    a[turn-1] = 0
    ans += 1
    turn = next_turn

print(ans)
W, H ,x, y, r = map(int,input().split())
if r <= x and x <= W-r and r <= y and y <= H-r:
    print(Yes)
else:print(No)


### FIXED CODE ###

W, H ,x, y, r = map(int,input().split())
if r <= x and x <= W-r and r <= y and y <= H-r:
    print('Yes')
else:print('No')
N = int(input())
S = input()
K = int(input())

c = S[K]
for i in range(N):
  if S[i] !== c:
    S[i] = '*'

print(S)
    

### FIXED CODE ###

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

kc = S[K - 1]
ans = ''
for c in S:
  if c != kc:
    ans += '*'
  else:
    ans += c

print(ans)
x,y,z=input().split()＃これは文字
x=int(x)
y=int(y)
z=int(z)
print(z,x,y)





### FIXED CODE ###

x,y,z=map(int,input().split())
print(z,x,y)
N = int(input())
thousand = 1000*M
thousand - N < 1000
print(M)

### FIXED CODE ###

N = int(input())
print((1000 - N % 1000) % 1000 )
import sys
import math
from collections import Counter
n = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
def comb(n):
  return math.factrial(n)/(math.factrial(n-2)*2)
for k in range(n):
  ans =0
  L=A[:k]+A[k+1:]
  for v in Counter(L).values():
    if v>=2:
      ans +=comb(v)
  print(ans)

### FIXED CODE ###

#ABC159D
import sys, math
from collections import Counter

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

def comb(n):
    return int(math.factorial(n)/(2*math.factorial(n-2)))

total = 0
L = Counter(A)
for v in L.values():
    if v>=2:
        total += comb(v)

for k in range(N):
    print(total - (L[A[k]]-1))
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())

def check(x):
  i = 2
  res = []
  while i * i <= x:
    while x % i == 0:
      x //= i
      res.append(i)
    i += 1
  if x > 1:
    res.append(x)
  return res
table = [0] * (N + 1)
for i in range(2, N + 1):
  for p in check(i):
    table[p] += 1
  #print(check(i))
t = []
#print(table)
for p in table:
  if p > 0: t.append(p)
t.sort()
#print(t)
k = len(t)
#print(k)
res = t[-1] >= 74
for i in range(k - 1):
  for j in range(i + 1, k):
    if t[i] + 1 >= 3 and (t[j] + 1 >= 25):
      res += 1
    if t[i] + 1 >= 5 and (t[j] + 1 >= 15):
      res += 1
    if t[i] + 1 >= 15 and (t[j] + 1 >= 5):
      res += 1
    if t[i] + 1 >= 25 and (t[j] + 1 >= 3):
      res += 1
#print(k, res)
for i in range(k - 2):
  for j in range(i + 1, k - 1):
    for l in range(j + 1, k):
      if (t[i] + 1) >= 3 and (t[j] + 1 >= 5) and (t[l] + 1 >= 5):
        res += 1
      if (t[i] + 1) >= 5 and (t[j] + 1 >= 3) and (t[l] + 1 >= 5):
        res += 1
      if (t[i] + 1) >= 5 and (t[j] + 1 >= 5) and (t[l] + 1 >= 3):
        res += 1
print(res)

### FIXED CODE ###

import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())

def check(x):
  i = 2
  res = []
  while i * i <= x:
    while x % i == 0:
      x //= i
      res.append(i)
    i += 1
  if x > 1:
    res.append(x)
  return res
table = [0] * (N + 1)
for i in range(2, N + 1):
  for p in check(i):
    table[p] += 1
  #print(check(i))
t = [0]
#print(table)
for p in table:
  if p > 0: t.append(p)
t.sort()
#print(t)
k = len(t)
#print(k)
res = t[-1] >= 74
for i in range(k - 1):
  for j in range(i + 1, k):
    if t[i] + 1 >= 3 and (t[j] + 1 >= 25):
      res += 1
    if t[i] + 1 >= 5 and (t[j] + 1 >= 15):
      res += 1
    if t[i] + 1 >= 15 and (t[j] + 1 >= 5):
      res += 1
    if t[i] + 1 >= 25 and (t[j] + 1 >= 3):
      res += 1
#print(k, res)
for i in range(k - 2):
  for j in range(i + 1, k - 1):
    for l in range(j + 1, k):
      if (t[i] + 1) >= 3 and (t[j] + 1 >= 5) and (t[l] + 1 >= 5):
        res += 1
      if (t[i] + 1) >= 5 and (t[j] + 1 >= 3) and (t[l] + 1 >= 5):
        res += 1
      if (t[i] + 1) >= 5 and (t[j] + 1 >= 5) and (t[l] + 1 >= 3):
        res += 1
print(int(res))
N = int(input())
s,t = map(str,input().split())
ans = ""
for i in range(N):
  ans.append(s[i])
  ans.append(t[i])
print(ans)
  

### FIXED CODE ###

N = int(input())
s,t = map(str,input().split())
ans = ""
for i in range(N):
  ans+=s[i]
  ans+=t[i]
print(ans)
from collections import Counter


n = int(input())
vs = list(map(int, input().split()))
a = vs[::2]
b = vs[1::2]

ca = Counter(a)
cb = Counter(b)
if ca.most_common(1)[0][0] != cb.most_common(1)[0][0]:
    print(n - ca.most_common(1)[0][1] - cb.most_common(1)[0][1])
else:
    print(min(
        n - ca.most_common(1)[0][1] - cb.most_common(2)[1][1],
        n - ca.most_common(2)[1][1] - cb.most_common(1)[0][1]
    ))


### FIXED CODE ###

from collections import Counter


n = int(input())
vs = list(map(int, input().split()))
a = vs[::2]
b = vs[1::2]

ca = Counter(a)
cb = Counter(b)
ca[0] = 0
cb[0] = 0
if ca.most_common(1)[0][0] != cb.most_common(1)[0][0]:
    print(n - ca.most_common(1)[0][1] - cb.most_common(1)[0][1])
else:
    print(min(
        n - ca.most_common(1)[0][1] - cb.most_common(2)[1][1],
        n - ca.most_common(2)[1][1] - cb.most_common(1)[0][1]
    ))
    # if len(set(vs)) == 1:
    #     print(n // 2)
    # else:
    #     print(min(
    #         n - ca.most_common(1)[0][1] - cb.most_common(2)[1][1],
    #         n - ca.most_common(2)[1][1] - cb.most_common(1)[0][1]
    #     ))
a,b=list(map(float,input().split()))
c=a*(b*100)
d=int(c//100)
print(d)

### FIXED CODE ###

import collections
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
 
n=int(input())
c= collections.Counter(prime_factorize(n))
#ここまでで素因数分解して個数が何個あるかcheckしてる
sum=0
for i in c:
    n=1
    while n*(n+1)/2<=c[i]:
        n=n+1
    sum=sum+n-1
print(sum)
letters = eval(input("Enter your words: "))
for i in letters:
  if i[2]==i[3] and i[4]==i[5]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

l = input()
print("Yes" if (l[2]==l[3] and l[4]==l[5]) else "No")
import math

A, B = map(int, input().split())

min_A = math.ceil(A * 100 / 8)
max_A = ((A + 1) * 100 / 8
min_B = math.ceil(B * 100 / 10)
max_B = (B + 1) * 100 / 10

if (min_A <= min_B and min_B < max_A):
    ans = min_B
elif (min_B <= min_A and min_A < max_B):
    ans = min_A
else:
    ans = -1

print(ans)


### FIXED CODE ###

import math

A, B = map(int, input().split())

min_A = math.ceil(A * 100 / 8)
max_A = (A + 1) * 100 / 8
min_B = math.ceil(B * 100 / 10)
max_B = (B + 1) * 100 / 10

if (min_A <= min_B and min_B < max_A):
    ans = min_B
elif (min_B <= min_A and min_A < max_B):
    ans = min_A
else:
    ans = -1

print(ans)
def gcd(x, y):
	if x < y:
		x, y = y, x
	if y == 0:
		return x
	z = x % y
	return gcd(y, z) 		
N=int(input())
prenum = 1
for i in range(N):
	T = int(input())
	lcm = (prenum*T) / gcd(T, prenum)
	prenum = lcm
print(int(lcm))

### FIXED CODE ###

def gcd(x, y):
	if x < y:
		x, y = y, x
	if y == 0:
		return x
	z = x % y
	return gcd(y, z) 
	
N=int(input())
prenum = 1
for i in range(N):
	T = int(input())
	lcm = prenum // gcd(prenum, T) * T
	prenum = lcm
print(lcm)
import sys

fin = sys.stdin.readline

N, M = map(int, fin().split())
As = list(map(int, fin().split()))
BC = [tuple(map(int, fin().split())) for _ in range(M)]

As = sorted(As)
# BC = sorted(BC, key=lambda x: x[1], reverse=True)

BC_ = {}
for num, val in BC:
    if val in BC_:
        BC_[val] += num
    else:
        BC_[val] = num

BC_ = sorted(BC_.items(), reverse=True)


def f(a, n, v):
    if a[n-1] < v:
        return v * n, a[n:]
    count = 0
    for i in range(min(n, len(a))):
        if a[i] < v:
            count += 1
        else:
            break
    return v * count, a[count:]


sum__ = 0
for val, num in BC_:
    if len(As) == 0 or As[0] >= val:
        break
    sum_, As = f(As, num, val)
    sum__ += sum_

print(sum__ + sum(As))




### FIXED CODE ###

import sys

fin = sys.stdin.readline

N, M = map(int, fin().split())
As = list(map(int, fin().split()))
BC = [tuple(map(int, fin().split())) for _ in range(M)]

As = sorted(As)
# BC = sorted(BC, key=lambda x: x[1], reverse=True)

BC_ = {}
for num, val in BC:
    if val in BC_:
        BC_[val] += num
    else:
        BC_[val] = num

BC_ = sorted(BC_.items(), reverse=True)

#
# def f(a, n, v):
#     if a[min(n-1, len(a)-1)] < v:
#         return v * min(n, len(a)), a[n:]
#     count = 0
#     for i in range(min(n, len(a))):
#         if a[i] < v:
#             count += 1
#         else:
#             break
#     return v * count, a[count:]


sum__ = 0
now = 0
for val, num in BC_:
    if now >= len(As) or As[now] >= val:
        break

    if As[min(num - 1 + now, len(As) - 1)] < val:
        sum_ = val * min(num, len(As) - now)
        now += min(num, len(As) - now)
    else:
        count = 0
        for i in range(min(num, len(As)-now)):
            if As[i + now] < val:
                count += 1
            else:
                break
        sum_ = val * count
        now += count
    sum__ += sum_

print(sum__ + sum(As[now:]))
A = int(input())
B = int(input())
C = int(input())
X = int(input())

count = 0

for i in range(A+1):
  for j in range(B+1):
    for k in range(C+1):
      if 500 *i + 100 *j + 50 *k == X
          count += 1

print(count)


### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())

count = 0

for i in range(A+1):
  for j in range(B+1):
    for k in range(C+1):
      if 500 *i + 100 *j + 50 *k == X:
        count += 1

print(count)
from scipy.special import comb
n, p = map(int, input().split())
a = list(map(int, input().split()))
ev, od = 0, 0
for i in a:
    if i%2 == 0:
        ev += 1
    else:
        od += 1
ans = 0
if p == 0:
    for i in range(0, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i, exact = True)*comb(ev, j, exact = True)
else:
    for i in range(1, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i, exact = True)*comb(ev, j, exact = True) 
print(ans)

### FIXED CODE ###

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

def comb(n, r):
    ans = 1
    if n < 2*r:
        r = n - r
    for i in range(r):
        ans *= (n - i)
        ans //= (i + 1)
    return ans

ev, od = 0, 0
for i in a:
    if i%2 == 0:
        ev += 1
    else:
        od += 1
ans = 0
if p == 0:
    for i in range(0, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i)*comb(ev, j)
else:
    for i in range(1, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i)*comb(ev, j) 
print(ans)
a,b=map(int,input().split())
if a%3 ==0:
  print('Possible')
elif b%3 ==0:
  print('Possible')
elif (a+b)%3 ==0:
  print('Possible')
else
  print('Impossible')

### FIXED CODE ###

a,b=map(int,input().split())
if a%3 ==0:
  print('Possible')
elif b%3 ==0:
  print('Possible')
elif (a+b)%3 ==0:
  print('Possible')
else:
  print('Impossible')
s = str(input())
print('Yes' if s[0] ='7' or s[1] ='7' or s[2] ='7' else 'No') 

### FIXED CODE ###

s = input()
print('Yes' if s[0] =='7' or s[1] =='7' or s[2] =='7' else 'No')
A=input()
B=input()
C=input()
if A+B>C or B>C:
  print(B+C)
else:
  print(2*B+C-A-B)


### FIXED CODE ###

A,B,C=map(int,input().split())
if A+B>=C:
  print(B+C)
else:
  print(2*B+A+1)
a=input().split()
if a[1]=="+":
    print(int(a[0])+int(a[1]))
else:
    print(int(a[0])-int(a[1]))

### FIXED CODE ###

a=input().split()
if a[1]=="+":
    print(int(a[0])+int(a[2]))
else:
    print(int(a[0])-int(a[2]))
a, b = input().split()
n = int(a + b)

if sqrt(n) ** 2 == n:
    print("Yes")
else:
    print("No")



### FIXED CODE ###

import math

a, b = input().split()
n = int(a + b)

if math.floor(math.sqrt(n)) ** 2 == n:
    print("Yes")
else:
    print("No")
fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    println!("ABC{}", s.trim())
}


### FIXED CODE ###

print('ABC' + input())
import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
n,k = map(int,input().split())
for i in range(1,k + 1):
    print(C(n - k + 1,i) * C(k - 1,i - 1) % 1000000007)

### FIXED CODE ###

import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
n,k = map(int,input().split())
for i in range(1,k + 1):
    if n - k + 1 < i:
        print(0)
        continue
    else:
        print(C(n - k + 1,i) * C(k - 1,i - 1) % 1000000007)
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
z = input()
print(l[z+1])

### FIXED CODE ###

l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
z = input()
n = int(z) - 1
print(l[n])
a = list()
for elem in input().split(' '):
    a.append(int(elem)) 

step = a[1] - a[0]
next =  a[1] + step

while True:
    if next >= a[2]:
        print(next)
        break
    else:
        next +=  step

### FIXED CODE ###

N = int(input())
a = list()
for elem in input().split(' '):
    a.append(int(elem))

sum = 0;
for number in a:
    sum+=1/number

print(1/sum)
D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

last = [0 for _ in range(26)]
calc = [0 for _ in range(26)]

for i in range(D):
  for j in range(26):
    day = i + 1
    calc[i] = c[i] * (day - last[i])
  min_idx = calc.index(max(calc))
  last[min_idx] = day
  print(min_idx + 1)

### FIXED CODE ###

D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

for i in range(D):
  print(s[i].index(max(s[i]))+1)
from sys import setrecursionlimit

setrecursionlimit(10**6)

def dfs(i, depth):
    visited[i] = True
    oe = depth%2
    ans[i-1] = oe
    count[oe] += 1
    nodes = tree[i]
    for node in nodes:
        if visited[node]:
            continue
        dfs(node, depth+1)
    


N = int(input())
ans = [-1]*N
tree = [[] for i in range(N+1)]
visited = [False]*(N+1)
count = [0, 0]
base = [1, 2, 3]
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a] += [b]
    tree[b] += [a]
dfs(1, 0+1)
if count[0] >= count[1]:
    for i, oe in enumerate(ans):
        if base[oe] > N:
            ans[i-1] = str(base[2])
            base[2] += 3
        else:
            ans[i-1] = str(base[oe])
            base[oe] += 3
else:
    for i, oe in enumerate(ans):
        oe = (oe+1)%2
        if base[oe] > N:
            ans[i] = str(base[2])
            base[2] += 3
        else:
            ans[i] = str(base[oe])
            base[oe] += 3
print(' '.join(ans))

### FIXED CODE ###

from sys import setrecursionlimit

setrecursionlimit(10**6)

def dfs(i, depth):
    visited[i] = True
    oe = depth%2
    ans[i-1] = oe
    count[oe] += 1
    nodes = tree[i]
    for node in nodes:
        if visited[node]:
            continue
        dfs(node, depth+1)
    


N = int(input())
ans = [-1]*N
tree = [[] for i in range(N+1)]
visited = [False]*(N+1)
count = [0, 0]
base = [1, 2, 3]
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a] += [b]
    tree[b] += [a]
dfs(1, 0)
even_len = count[0]
odd_len = count[1]
if even_len > N//3 and odd_len > N//3:
    for i, oe in enumerate(ans):
        if base[oe] > N:
            ans[i] = str(base[2])
            base[2] += 3
        else:
            ans[i] = str(base[oe])
            base[oe] += 3
elif even_len <= N//3:
    for i, oe in enumerate(ans):
        if oe == 0:
            ans[i] = str(base[2])
            base[2] += 3
        elif base[0] <= N:
            ans[i] = str(base[0])
            base[0] += 3
        elif base[1] <= N:
            ans[i] = str(base[1])
            base[1] += 3
        else:
            ans[i] = str(base[2])
            base[2] += 3
elif odd_len <= N//3:
    for i, oe in enumerate(ans):
        if oe == 1:
            ans[i] = str(base[2])
            base[2] += 3
        elif base[0] <= N:
            ans[i] = str(base[0])
            base[0] += 3
        elif base[1] <= N:
            ans[i] = str(base[1])
            base[1] += 3
        else:
            ans[i] = str(base[2])
            base[2] += 3
print(' '.join(ans))
K = int(input())
A,B = [int(i) for i in input().split()]
flag=0
for i in range(1,1001):
  if(iK>=A and iK<=B):
    print("OK")
    flag=1
    break
if (flag==0):
  print("NG")

### FIXED CODE ###

K = int(input())
A,B = [int(i) for i in input().split()]
flag=0
for i in range(1,1001):
    if(i*K>=A and i*K<=B):
        print("OK")
        flag=1
        break
if (flag==0):
    print("NG")
from collections import deque

def merge(s, t):
    u = []

    while s + t:
        
        if s == [] or t == []:
            return u + s + t

        if s[0] >= t[0]:
            u.append(s[0])
            s = s[1:]
        else: # s0 > t0
            u.append(t[0])
            t = t[1:]

    return u

def merge_sort(A):
    while len(A) > 1:
        B = []
        for _ in range(len(A) // 2):
            B.append(merge(A[0], A[1]))
            A = A[2:]
        B += A
        A = B

    return(A[0])

X, Y, A, B, C = [int(x) for x in input().split()]
p = deque(merge_sort([[int(x)] for x in input().split()]))
q = deque(merge_sort([[int(x)] for x in input().split()]))
r = deque(merge_sort([[int(x)] for x in input().split()]))

ans = 0
for i in range(X):
    if p[0] >= r[0]:
        ans += p.popleft()
    else:
        ans += r.popleft()

for i in range(Y):
    if q[0] >= r[0]:
        ans += q.popleft()
    else:
        ans += r.popleft()

print(ans)

### FIXED CODE ###

X, Y, A, B, C = [int(x) for x in input().split()]
p = sorted([int(x) for x in input().split()], reverse=True)[:X]
q = sorted([int(x) for x in input().split()], reverse=True)[:Y]
r = sorted([int(x) for x in input().split()], reverse=True)[:X + Y]

s = sorted(p + q + r, reverse=True)

ans = sum(s[:X + Y])

print(ans)
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
xs,ys,xt,yt=map(int,input().split())
N=int(input())
XYR=[list(map(int,input().split())) for i in range(N)]
XYR.append([xt,yt,0])#終点
XYR.append([xs,ys,0])#開始
kyori=[[0 for i in range(len(XYR))] for n in range(len(XYR))]
for i in range(len(XYR)):
    for m in range(i,len(XYR)):
        if i==m:
            t=0
        else:
            x1,y1,r1=XYR[i]
            x2,y2,r2=XYR[m]
            t=max(((x2-x1)**2+(y2-y1)**2)**.5-r1-r2,0)

        kyori[i][m]=t
        kyori[m][i]=t

print(exit)
stack=sorted(kyori[-2])
heapify(stack)
Pdic={}
dic={}
kyoriset=set()
for i in range(len(XYR)):
    a=kyori[-1][i]
    Pdic.update({i:a})
    if not a in kyoriset:
        kyoriset.add(a)
        dic.update({a:[i]})
    else:
        dic[a].append(i)

visited=set([len(XYR)-1])
#print(Pdic)
#print(dic)
#print(stack)
while stack:
    m=heappop(stack)
    a=dic[m].pop()
    if a==len(XYR)-2:
        print(m)
        exit()
    if not a in visited:
        visited.add(a)
        for i in range(len(XYR)):
            nm=kyori[a][i]+m
            #if Pdic[i]>nm:
            #    Pdic[i]=nm
            heappush(stack,nm)
            if not nm in dic:
                #kyoriset.add(nm)
                dic.update({nm:[i]})
            else:
                dic[nm].append(i)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
idle=10**13
xs,ys,xt,yt=map(int,input().split())
N=int(input())
XYR=[list(map(int,input().split())) for i in range(N)]
XYR.append([xt,yt,0])#終点
XYR.append([xs,ys,0])#開始
"""for i in range(len(XYR)):
    XYR[i][0]*=idle
    XYR[i][1]*=idle
    XYR[i][2]*=idle"""
kyori=[[0 for i in range(len(XYR))] for n in range(len(XYR))]
for i in range(len(XYR)):
    for m in range(i,len(XYR)):
        if i==m:
            t=0
        else:
            x1,y1,r1=XYR[i]
            x2,y2,r2=XYR[m]
            t=max(((x2-x1)**2+(y2-y1)**2)**.5-r1-r2,0)

        kyori[i][m]=t
        kyori[m][i]=t
stack=sorted(kyori[-1])
heapify(stack)
Pdic={}
dic={}
kyoriset=set()
for i in range(len(XYR)):
    a=kyori[-1][i]
    Pdic.update({i:a})
    if not a in kyoriset:
        kyoriset.add(a)
        dic.update({a:[i]})
    else:
        dic[a].append(i)
visited=set([len(XYR)-1])
while stack:
    m=heappop(stack)
    a=dic[m].pop()
    if a==len(XYR)-2:
        print(m)
        exit()
    if not a in visited:
        visited.add(a)
        for i in range(len(XYR)):
            nm=kyori[a][i]+m
            if Pdic[i]>nm:
                Pdic[i]=nm
                heappush(stack,nm)
                if not nm in kyoriset:
                    kyoriset.add(nm)
                    dic.update({nm:[i]})
                else:
                    dic[nm].append(i)