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

import numpy as np

n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

move_p = [a, b, c, d, e]
pos = np.zeros(6)
pos_pre = np.zeros(6)
move_n = np.zeros(5)
pos[0] = n
cnt = 0
while sum(pos[: 6]) != 0:

    for i in range(5):
        if move_p[i] <= pos[i]:
            move_n[i] = move_p[i]
            pos[i] -= move_n[i]
            pos_pre[i + 1] += move_n[i]
        elif pos[i] < move_p[i]:
            move_n[i] = pos[i]
            pos[i] -= move_n[i]
            pos_pre[i + 1] += move_n[i]

    for i in range(5):
        pos[i] += pos_pre[i]
        pos_pre[i] = 0
    cnt += 1

print(cnt)


### FIXED CODE ###

import numpy as np

n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

move_p = [a, b, c, d, e]
# pos = np.zeros(6)
# pos_pre = np.zeros(6)
# move_n = np.zeros(5)
# pos[0] = n
# cnt = 0
# while sum(pos[: 6]) != 0:

#     for i in range(5):
#         if move_p[i] <= pos[i]:
#             move_n[i] = move_p[i]
#             pos[i] -= move_n[i]
#             pos_pre[i + 1] += move_n[i]
#         elif pos[i] < move_p[i]:
#             move_n[i] = pos[i]
#             pos[i] -= move_n[i]
#             pos_pre[i + 1] += move_n[i]

#     for i in range(5):
#         pos[i] += pos_pre[i]
#         pos_pre[i] = 0
#     cnt += 1

min_ = min(move_p)
cnt = int(np.ceil(n / min_) + 4)

print(cnt)
### BUGGY CODE ###

import heapq
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
dh=DH-1
dw=DW-1
S=[[x=='#' for x in list(input())] for _ in range(H)]
q=[(0,0,CH-1,CW-1)]
heapq.heapify(q)
checked=set()
def check(h,w,c):
    if h<0 or h>=H or w<0 or w>=W:
        return
    if S[h][w]:
        return
    p=(abs(dh-h),abs(dw-w))
    heapq.heappush(q,(c,p,h,w))
    return True

def main():
    while q:
        c,_,h,w=heapq.heappop(q)
        if h==dh and w==dw:
            return c
        key=(h,w)
        if key in checked:
            continue
        checked.add(key)
        # walk
        check(h-1,w-0,c)
        check(h-0,w-1,c)
        check(h+1,w+0,c)
        check(h+0,w+1,c)
        # warp
        check(h,w-2,c+1)
        check(h,w+2,c+1)
        check(h-2,w,c+1)
        check(h+2,w,c+1)
        for i in [-2,-1,1,2]:
            for j in [-2,-1,1,2]:
                check(h+i,w+j,c+1)
    return -1
print(main())


### FIXED CODE ###

def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        #if 0<=h<H and 0<=w<W and s[h][w]==-1:
        if s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        #print(q1)
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(1000000)

"""解説
いもす法っぽいことする
[入力例]
4 3
1 2
2 3
2 4
2 10
1 100
3 1

[出力例]
"""
def solve():
    N, Q = list(map(int, input().split()))
    to = [[] for _ in range(N)]  # 木

    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        a, b = a-1, b-1  # 0始まりになるように
        to[a].append(b)  # 無向グラフになるように両方に加える
        to[b].append(a)  # 無向グラフになるように両方に加える

    #print(to)

    ans = [0 for _ in range(N)]
    for _ in range(Q):
        p, x = list(map(int, input().split()))
        p = p-1  # 0始まりになるように
        ans[p] += x

    #print(ans)

    def dfs(v, p=-1):
        for u in to[v]:
            if u==p: continue
            ans[u] += ans[v]  # いもす法っぽい累積和をする
            dfs(u, v)

    dfs(0)

    print(*ans)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
N, Q = map(int, sys.stdin.readline().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(N-1)]
p_x = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

rin = [[] for _ in range(N)]
for v in a_b:
    rin[v[0]-1].append(v[1]-1)
    rin[v[1]-1].append(v[0]-1)

score = [0 for _ in range(N)]
for ele in p_x:
    score[ele[0]-1] +=ele[1]
#print(score)

def dfs(p, bp=-1):
    for c in rin[p]:
        if c != bp:
            #print(c)
            score[c]+= score[p]
            dfs(c, p)

dfs(0)
print(*score)
### BUGGY CODE ###

N = int(input())
T = []
A = []
for _ in range(N):
    t, a = map(int,input().split())
    T.append(t)
    A.append(a)

ct = T[0]
ca = A[0]
for i in range(1, N):
    t = T[i]
    a = A[i]
    m = 1
    while (t + a) * m < (ct + ca) or m * t < ct or m * a < ca:
        m += 1
    ct = m * t
    ca = m * a

print(ct+ca)




### FIXED CODE ###

N = int(input())
T = []
A = []
for _ in range(N):
    t, a = map(int,input().split())
    T.append(t)
    A.append(a)

ans = 1
ct = 1
ca = 1
for t, a in zip(T, A):
    n = max((ct + t - 1) // t, (ca + a - 1) // a)
    ct = n * t
    ca = n * a

print(ct+ca)
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
n = 10**6+1

dp = [0 for _ in range(max(A)+1)]

for i in A:
    dp[i] += 1
    if dp[i]==1:
        for j in range(i*2, max(A)+1, i):
            dp[j] += 2
    # print(dp)
print(dp.count(1))

### FIXED CODE ###

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

m_a = max(A)+1
dp = [0]*m_a

for i in A:
    dp[i] += 1
    if dp[i]==1:
        for j in range(i*2, m_a, i):
            dp[j] += 2
    # print(dp)
print(dp.count(1))
### BUGGY CODE ###

def main():
    n = int(input())
    x = list(map(int,input().split()))

    a = x[1:]
    a.sort()
    print(a[n//2-1])

    for i in range(1,n-1):
        a = x[:i] + x[i+1:]
        a.sort()
        print(a[n//2-1])

    a = x[:n-1]
    a.sort()
    print(a[n//2-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import copy
def main():
    n = int(input())
    x = list(map(int,input().split()))

    a = copy.deepcopy(x)
    a.sort()
    a1 = a[(n-1)//2]
    a2 = a[(n+1)//2]

    for i in range(0,n):
        if x[i]<=a1:
            print(a2)
        else:
            print(a1)

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

N,K,Q = map(int,input().split())
A = []
p = []
for i in range(Q):
    A.append(int((input())))

for i in range(N):
    p.append(A.count(i+1))
    P = K - Q + p[i]
    if P > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
p = [0] * N 
for i in A:
    p[i-1] += 1    

for i in range(N):
    P = K - Q + p[i]
    if P > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def examA():
    S = SI()
    T = SI()
    N = len(S)
    ans = "No"
    for i in range(N):
        cur = S[i:] + S[:i]
        #print(cur)
        if cur==T:
            ans = "Yes"
    print(ans)
    return

def examB():
    H, W = LI()
    S = [SI()for _ in range(H)]
    flag = True
    ans = 0
    print(ans)
    return

def examC():
    L, R = LI()
    ans = inf
    if R-L>=3000:
        R = L+3000

    for l in range(L, R + 1):
        for r in range(l+1, R + 1):
            now = (l*r) %2019
            ans = min(ans,now)
    print(ans)
    return

def examD():
    T = {"dream", "dreamer", "erase", "eraser"}
    S = SI()
    ans = "NO"
    t = ""
    for s in S[::-1]:
        t += s
        if t[::-1] in T:
            t = ""
    if t=="":
        ans = "YES"
    print(ans)
    return

def examE():
    N = 50
    K = I()
    base = K//N
    A = [base+i for i in range(N)]
    rest = K%N
    for i in range(rest):
        A[-i-1] += 1
    print(N)
    print(" ".join(map(str,A)))
    return

def examF():
    N = 20
    C = [2**i for i in range(N)]
    L = I()
    cur = 1
    V = [[i+1, i+2, 0]for i in range(N-1)]
    now = 1
    while(now<N):
        if C[now]<=L:
            cur = C[now]
            V.append([now,now+1,C[now-1]])
            now += 1
        else:
            break
    #print(cur)

    for i in range(now)[::-1]:
        if C[i]<=L-cur:
            cost = cur
            V.append([i+1,N,cost])
            cur += C[i]

    print(N,len(V))
    for s,t,c in V:
        print(s,t,c)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

### FIXED CODE ###

def examC():
    St = S()
    t = ["dream", "dreamer", "erase", "eraser"]
    i = len(St)-1
    cur = ""
    while i>=0:
#        print(cur)
        cur = St[i] + cur
        i -=1
        if cur in t:
            cur = ""
    if len(cur)==0:
        ans = "YES"
    else:
        ans = "NO"
    print(ans)


import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()
### BUGGY CODE ###

N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = bin(next_int).count('1')
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))


### FIXED CODE ###

N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_cnt == 0:
        return 0
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        if next_cnt == 0:
            next_int = 0
        else:
            next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)
### BUGGY CODE ###

import numpy as np
def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    ans = np.ones(N,dtype=int)
    for i in range(N-1):
        for j in range(i+1,N):
            if A[i] % A[j] == 0:
                ans[i] = 0
                break
    for i in range(N-1):
        for j in range(i+1,N):
            if A[N-1 - i] % A[N-1 -j] == 0:
                ans[N-1 - i] = 0
                break
    print(sum(ans))
resolve()

### FIXED CODE ###

#写経
#https://atcoder.jp/contests/abc170/submissions/14363499
import sys

def resolve():
    it = map(int,sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]
    
    if N == 1:
        print(1)
        return
    ax = max(A) + 1
    dp = [0] * ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
    ans = 0
    for ai in A:
        if dp[ai] == 1:
            ans += 1
    print(ans)
resolve()
### BUGGY CODE ###

# coding: utf-8

from copy import deepcopy

import sys
sys.setrecursionlimit(100000)

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

# from time import time
# start = time()

# neighbor = {}
# for i in range(1, N):
#     neighbor[i] = [i+1]
# for i in range(X+4, Y):
#     neighbor[i] = [i-1, i+1]
# neighbor[X] = [X+1, Y]
# neighbor[Y] = [Y-1, Y+1]
# neighbor[N] = [] if Y < N else [N-1] 
# print(neighbor)

neighbor = {}
for i in range(1, X):
    neighbor[i] = [i+1]
for i in range(Y+1, N):
    neighbor[i] = [i+1]
for i in range(X+1, Y):
    neighbor[i] = [i-1, i+1]
neighbor[X] = [X+1, Y]
neighbor[Y] = [Y-1, Y+1]
neighbor[N] = [] if Y < N else [N-1]
# print(neighbor)

# print(neighbor)

# neighbor = {i: [i-1, i+1] for i in range(2, N)}
# neighbor[1] = [2]
# neighbor[N] = [N-1]
# neighbor[X].append(Y)
# neighbor[Y].append(X)

# appeared_st = set([])
appeared_st = [set([]) for _ in range(N+1)]
# appeared_st[0] = 0
n_k = [0] * N
s_t_dict = {}


# def rec(n, dist, s, k, appeared):
#     # print(appeared_st)
#     if dist == k:
#         # if k == 2:
#         #     input()
#         if s < n and n not in appeared_st[s]:
#             appeared_st[s].add(n)
#             appeared_st[0] += 1
#             # print(appeared_st)

#     toes = [node for node in neighbor[n] if node not in appeared]
#     for to in toes:
#         appeared_copy = deepcopy(appeared)
#         appeared_copy.add(to)
#         rec(to, dist+1, s, k, appeared_copy)


def rec(n, dist, s, limit, appeared):
    if s < n:
        ke = "{}.{}".format(s, n)
        if ke in s_t_dict:
            if dist < s_t_dict[ke]:
                n_k[s_t_dict[ke]] -= 1
                s_t_dict[ke] = dist
                n_k[dist] += 1
        else:
            s_t_dict[ke] = dist
            n_k[dist] += 1
            
    # if s < n and n not in appeared_st[s]:
    #     appeared_st[s].add(n)
    #     n_k[dist] += 1
    #     print(appeared_st)
    #     print(n_k)
    #     input()

    if dist == limit:
        return None

    toes = [node for node in neighbor[n] if node not in appeared]
    for to in toes:
        appeared_copy = deepcopy(appeared)
        appeared_copy.add(to)
        rec(to, dist+1, s, limit, appeared_copy)


for s in range(1, N):
    rec(s, 0, s, N-1, {s})

for k in range(1, N):
    print(n_k[k])

# for k in range(1, N):
#     tmp = appeared_st[0]

#     for s in range(1, N+1):
#         rec(s, 0, s, k, {s})

    # print(appeared_st[0] - tmp)

# print(appeared_st)
# print(len(appeared_st))
            
# print(time() - start)


### FIXED CODE ###

# coding: utf-8

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

n_k = [0] * (N+1)

for i in range(1, N):
    for j in range(i+1, N+1):
        n_k[min(abs(j-i), abs(X-i) + 1 + abs(j-Y))] += 1

for k in range(1, N):
    print(n_k[k])
### BUGGY CODE ###

str = input()
times = int(input())
for i in range(times):
    com = input().split()
    if com[0] == "1":
        str = str[::-1]
    else :
        if com[1] == "1":
            str = com[2]+str
        else :
            str += com[2]            

print(str)

### FIXED CODE ###

str = input()
times = int(input())
revers = 0
head = ""
tail = ""
for i in range(times):
    com = input().split()
    if com[0] == "1":
        if revers == 0:
            revers = 1
        else :
            revers = 0
        
    else :
        if com[1] == "1":
            if revers == 0:
                head = com[2]+head
            else :
                tail = tail + com[2]
        else : 
            if revers == 1:
                head = com[2]+head
            else :
                tail = tail + com[2]          
str = head + str + tail
if revers == 1:
    str = str[::-1]
                
print(str)
### BUGGY CODE ###

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


sum_a = [0]
for i in range(n):
    sum_a.append(sum_a[i]+a[i])

sum_b = [0]
for i in range(m):
    sum_b.append(sum_b[i]+b[i])

max = 0 
for i in range(len(sum_a)):
    if sum_a[i] > k:
        max = i-1 if i-1 > max else max
        break
    else:
        for j in range(m+1):
            sum_ab = sum_a[i] + sum_b[j]
            if sum_ab > k:
                max = i+j-1 if i+j-1 > max else max
                break
            else:
                max = i+j if i+j > max else max

print(max)

### FIXED CODE ###

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


sum_a = [0]
for i in range(n):
    sum_a.append(sum_a[i] + a[i])

sum_b = [0]
for i in range(m):
    sum_b.append(sum_b[i] + b[i])


a_i = 0
b_i = 0
for i in range(n+1):
    if sum_a[i] > k:
        break
    else:
        a_i = i

for i in range(m+1):
    if sum_a[a_i] + sum_b[i] > k:
        break
    else:
        b_i = i


ans = a_i + b_i
for i in range(a_i, -1, -1):
    for j in range(b_i, m+1):
        if sum_a[i] + sum_b[j] > k:
            b_i = j - 1
            break
        else:
            ans = max(ans, i+j)

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

n = int(input())
s = input()
MOD = 10**9 + 7
li = []
for i in range(2*n):
    if i % 2 == 0 and s[i] == "B":
        li.append("W")
    elif i % 2 == 0 and s[i] == "W":
        li.append("B")
    elif i % 2 == 1 and s[i] == "B":
        li.append("B")
    elif i % 2 == 1 and s[i] == "W":
        li.append("W")
        
cnt = 0
ans = 1
for string in li:
    if string == "W":
        cnt += 1
    else:
        if cnt <= 0:
            print(0)
            exit()
        ans *= cnt
        cnt -= 1

if cnt != 0:
    print(0)
    exit()

for i in range(1, n+1):
    ans *= i
    ans %= MOD

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
MOD = 10**9 + 7
li = []
for i in range(2*n):
    if i % 2 == 0 and s[i] == "B":
        li.append("W")
    elif i % 2 == 0 and s[i] == "W":
        li.append("B")
    elif i % 2 == 1 and s[i] == "B":
        li.append("B")
    elif i % 2 == 1 and s[i] == "W":
        li.append("W")
        
cnt = 0
ans = 1
for string in li:
    if string == "W":
        cnt += 1
    else:
        if cnt <= 0:
            print(0)
            exit()
        ans *= cnt
        cnt -= 1
    ans %= MOD

if cnt != 0:
    print(0)
    exit()

for i in range(1, n+1):
    ans *= i
    ans %= MOD

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

def gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)

def lcm(a, b):
    return a*(b//gcd(a, b))

mod = int(1e9+7)

n = int(input())
vs = list(map(int, input().split()))
l = 1
for x in vs:
    l = lcm(l, x)

ans = 0
for x in vs:
    ans = (ans + ((l//x)%mod))%mod
print(ans)


### FIXED CODE ###

def gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)

def lcm(a, b):
    return a*(b//gcd(a, b))

mod = int(1e9+7)
def ext_gcd(a, b, x, y):
    if b==0:
        x[0] = 1
        y[0] = 0
        return a
    g = ext_gcd(b, a%b, y, x)
    y[0]-=a//b*x[0]
    return g

def mod_inv(a):
    x = [0]
    y = [0]
    ext_gcd(a, mod, x, y)
    return (x[0]%mod + mod)%mod;

n = int(input())
vs = list(map(int, input().split()))
l = 1
for x in vs:
    l = lcm(l, x)
l = l%mod;
ans = 0
for x in vs:
    ans = (ans + ((l*mod_inv(x))%mod))%mod
print(ans)
### BUGGY CODE ###

m = 10**9+7
def inv(x):
  m = 10**9+7
  t = x
  y = 1
  while True:
    if t == 1:
      break
    y *= m // t
    t = m % t
    y *= -1
    y %= m
  return y
import math
def cc(x,y):
  xx = math.factorial(x) % m
  yy = math.factorial(y) % m
  xy = math.factorial(x-y) % m
  return xx * inv(yy) * inv(xy) % m
n,a,b,c = map(int,input().split())
d = 100 - c
awin = a * inv(d)
bwin = b * inv(d)
asc = 0
bsc = 0
for i in range(n):
  p = cc(n-1+i,i) * awin**(n-1) * bwin**i * (n+i)
  asc += p
  asc %= m
for i in range(n):
  p = cc(n-1+i,i) * awin**i * bwin**(n-1) * (n+i)
  bsc += p
  bsc %= m
sc = asc * awin + bsc * bwin
sc %= m
scn = sc * 100 * inv(d)
scn %= m
print(scn)

### FIXED CODE ###

#18:04
n,a,b,c = map(int,input().split())
mod = 10 ** 9 + 7
def inv(x):
  ans = 1
  now = x
  while now != 1:
    ans *= mod // now + 1
    ans %= mod
    now = now - mod % now
  return ans
p = (a * inv(a+b)) % mod
q = (b * inv(a+b)) % mod
taka = 0
aoki = 0
tcom = 1
acom = 1
for i in range(n):
  taka += tcom * (n+i)
  tcom *= n+i
  tcom *= inv(i+1)
  tcom *= q
  tcom %= mod
  aoki += acom * (n+i)
  acom *= n+i
  acom *= inv(i+1)
  acom *= p
  acom %= mod
for _ in range(n):
  taka *= p
  taka %= mod
  aoki *= q
  aoki %= mod
ans = taka + aoki
ans *= 100
ans *= inv(a+b)
ans %= mod
print(ans)
### BUGGY CODE ###

from itertools import combinations
N = int(input())
S = input()
print (len(set(combinations(S,3))))

### FIXED CODE ###

from itertools import product
N = int(input())
S = input()
S = [int(s) for s in S]
ans = 0
for q in product(range(10),repeat=3):
    i = 0
    for s in S:
        if s==q[i]:
            if i==2:
                ans += 1
                break
            else:
                i+=1
print (ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
Xs,Ys,Xg,Yg=map(int,input().split())

N=int(input())

L=[[Xs,Ys,0]]
for i in range(N):
    x,y,r=map(int,input().split())
    L.append([x,y,r])
L.append([Xg,Yg,0])

C=[-1 for i in range(len(L))]
C[0]=0

X=Xs
Y=Ys
R=0
Q=[]
import heapq
heapq.heapify(Q)
Z=[]
for i in range(1,len(L)):
    if C[i]==-1:
        heapq.heappush(Q,[max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2])),i,0])
        #Z.append([max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2])),i,0])
#print(Z)
        
for j in range(10**7):
    if len(Q)==0:
        break
    else:
        if C[Q[0][1]]!=-1:
            qq=heapq.heappop(Q)
            
        else:
            q=heapq.heappop(Q)
            C[q[1]]=q[0]
            X=L[q[1]][0]
            Y=L[q[1]][1]
            R=L[q[1]][2]
            for i in range(1,len(L)):
                if C[i]==-1:
                    heapq.heappush(Q,[max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2]))+C[q[1]],i,q[1]])
                    #Z.append([max(0,((X-L[i][0])**2+(Y-L[i][1])**2)**0.5-(R+L[i][2])),i,q[1]])
    if C[-1]!=-1:
        break
    #print(C)
    #print(Z)
print(C[-1])
#print(C)

### FIXED CODE ###

import sys
input=sys.stdin.readline

Xs,Ys,Xg,Yg=map(int,input().split())
N=int(input())
L=[]
L.append([Xs,Ys,0])
for i in range(N):
    x,y,r=map(int,input().split())
    L.append([x,y,r])
L.append([Xg,Yg,0])
cost=[[-1 for i in range(N+2)]for j in range(N+2)]
for i in range(N+2):
    for j in range(i,N+2):
        cost[i][j]=max(0,((L[i][0]-L[j][0])**2+(L[i][1]-L[j][1])**2)**0.5-L[i][2]-L[j][2])
        cost[j][i]=cost[i][j]
#print(cost)


def jdijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

#print(jdijkstra(0,N+2,(N+2)**2,cost))
ans=jdijkstra(0,N+2,(N+2)**2,cost)
print(ans[-1])