Harryxun/stf_run huggingface dataset:
X = int(input().split())

dp = [False] * (X + 1)
dp[0] = True
for i in range(X):
  if i:
    for x in [100, 101, 102, 103, 104, 105]:
      if i+x <= X:
        dp[i+x] = True

if dp[-1]:
  print(1)
else:
  print(0)

### FIXED CODE ###

X = int(input())

dp = [False] * (X + 1)
dp[0] = True
for i in range(X):
  if dp[i]:
    for x in [100, 101, 102, 103, 104, 105]:
      if i+x <= X:
        dp[i+x] = True

if dp[-1]:
  print(1)
else:
  print(0)
x=int(input())
a=int(input())
if x<a:
  print(0)
else:
  print(10)

### FIXED CODE ###

x,a=map(int,input().split())
if x<a:
  print(0)
else:
  print(10)
import numpy as np

def prime_decomposition(n):
  i = 2
  t = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      t.append(i)
    i += 1
  if n > 1:
    t.append(n)
  return t

def get_binary(arr):
	lim = 10**9
	a = np.prod(arr[:-1])
	c = 0
	b = arr[-1]
	while a > lim:
		c+=1
		a=np.prod(arr[c:-1])
		tmp = [arr[-1]] + arr[:c]
		b=np.prod(tmp)
		if b > lim:
			return -1,-1
	return a,b

lim = 10**9
S = int(input())
t = prime_decomposition(S)
a = 1
ta = [0,0]
x1,x2,x3,y1,y2,y3 = 0,0,0,0,0,0
x2,y3 = get_binary(t)
while max(t) >= lim or max(ta) >= lim or len(t) == 1 or (x2 == -1 and y3 == -1) or (x3 == -1 or y2 == -1):
	a+= S//(10**(len(str(S)) - 9))
	t = prime_decomposition(S-a)
	ta = prime_decomposition(a)
	x2,y3 = get_binary(t)
	x3,y2 = get_binary(ta)



print("%d %d %d %d %d %d" % (x1,y1,x2,y2,x3,y3))

### FIXED CODE ###

S = int(input())
lim = 10**9
x1,y1 = 0,0
x2,y2 = 10**9, 1
x3 = (lim-S%lim)%lim
y3 = (S+x3)//lim
print("%d %d %d %d %d %d" % (x1,y1,x2,y2,x3,y3))
N, Q = map(int, input().split())
S = input()

L = []
R = []

for i in range(Q):
    l, r = map(int, input().split())
    L.append(l-1)
    R.append(r-1)

a = [0]*N
pre = ''

for i, s in enumerate(S):
    if pre=='A' and s=='C':
        a[i] = 1
    pre = s

cnt = 0
for i in range(Q):
    cnt = sum(a[:R[i]]) - sum(a[:L[i]])
	print(cnt)

### FIXED CODE ###


N, Q = map(int, input().split())
S = list(input())
lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l-1, r-1])
AC = []
pre = None
cnt = 0
for c in S:
    if c == "A":
        pre = "A"
    elif pre == "A" and c == "C":
        cnt += 1
        pre = None
    elif pre == "A":
        pre = None
    AC.append(cnt)
for l, r in lr:
    print(AC[r] - AC[l])
N = int(input())
t_old, x_old, y_old = 0, 0, 0

for i in range(N):
  t, x, y = map(int, input().split())
  dt = t - t_old
  dx = x - x_old
  dy = y - y_old
  t_old = t
  x_old = x
  y_old = y
  if abs(dx) + abs(dy) =< dt and (dt - (abs(dx) + abs(dy))) % 2 == 0:
    if i == N - 1:
      print('Yes')
    pass
  else:
    print('No')
    break
    


### FIXED CODE ###

N = int(input())
t_old, x_old, y_old = 0, 0, 0

for i in range(N):
  t, x, y = map(int, input().split())
  dt = t - t_old
  dx = x - x_old
  dy = y - y_old
  t_old = t
  x_old = x
  y_old = y
  if abs(dx) + abs(dy) <= dt and (dt - (abs(dx) + abs(dy))) % 2 == 0:
    if i == N - 1:
      print('Yes')
    pass
  else:
    print('No')
    break
N = int(input())
H = list(map(int, input().split()))
 
ans = 0
m=0
for i in range(N-1):
  count.append(0)
  if H[i] > H[i+1]:
    m+=1
    ans = max(ans, m)
    
  else:
    m=0
    
S = str(count).split('0')
L = map(len, S)
print(max(L))

### FIXED CODE ###

S = input()
T = input()

count = 0
for s,t in zip(S,T):
  if s == t:
    count+=1
    
print(count)
import itertools
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N, K = map(int, input().split())
x = combinations_count(N-1, 2)
if N-1 < K < combinations_count(N-1, 2):
    print('-1')
    quit()

for i in range(2,N+1):
    print('1', str(i))

for i in range(2,x-K,2):
    print(str(i), str(i+1))

### FIXED CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N, K = map(int, input().split())
if N > 2:
    x = combinations_count(N-1, 2)
else:
    x = 0
if x < K:
    print('-1')
    quit()

h = []
for i in range(2,N+1):
    h.append(('1', str(i)))

hen = x-K
x = 2
y = 3
while hen > 0:
    h.append((x,y))
    y += 1
    if y > N:
        x += 1
        y = x+1
    hen -= 1

print(len(h))
for x,y in h:
    print(x,y)
N, M = map(int, input().split())
heights = list(map(int,input().split()))
win = []

for i in range(1, N + 1):
  win.append(i)

for i in range(M):
  x, y = map(int, input().split())
  if heights[x - 1] > heights[y - 1]:
    del win[x - 1]
  elif heights[x - 1] < heights[y - 1]:
    del win[y - 1]

print(len(win))

### FIXED CODE ###

N, M = map(int, input().split())
heights = list(map(int,input().split()))
lose = []

for i in range(M):
  x, y = map(int, input().split())
  if heights[x - 1] > heights[y - 1]:
    lose.append(y)
  elif heights[x - 1] < heights[y - 1]:
    lose.append(x)
  elif heights[x - 1] == heights[y - 1]:
    lose.append(y)
    lose.append(x)

print(N - len(list(set(lose))))
n, m, q = map(int, input().split())
value = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    value.append([a - 1, b - 1, c, d])
value.sort()
ans_list = []
for i in range(2 **q):
    t = '0' * (q - len(bin(i)[2:])) + bin(i)[2:]
    dp = [1] * m
    dp_k = [0] * m
    ans = 0
    for j, tt in enumerate(t):
        if tt == '1':
            if dp_k[value[j][1]] == 0:
                dp[value[j][1]] = dp[value[j][0]] + value[j][2]
                dp_k[value[j][1]] = 1
                if dp[value[j][1]] <= m:
                    ans += value[j][3]
                else:
                    ans = 0
                    break
            elif dp_k[value[j][1]] == 1:
                if dp[value[j][1]] == dp[value[j][0]] + value[j][2]:
                    ans += value[j][3]
                else:
                    ans = 0
                    break
            else:
                ans = 0
                break
    ans_list.append(ans)
print(max(ans_list))        

### FIXED CODE ###

import itertools

n, m, q = map(int, input().split())
value = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    value.append([a - 1, b - 1, c, d])
ans = 0
for comb in itertools.combinations_with_replacement(range(1, m + 1), n):
    temp = 0
    for v in value:
        if comb[v[1]] == comb[v[0]] + v[2]:
            temp += v[3]
    ans = max(ans, temp)
print(ans)
a = input()
 print(a + a * 2 + a * 3 = Z)

### FIXED CODE ###

a = int(input())
print(a + a**2 + a**3)
n, m = map(int, input(),split())
print('Yes' if n==m else 'No')

### FIXED CODE ###

n, m = map(int, input().split())
print('Yes' if n==m else 'No')
if n > k:
    print(n)
elif n + m > k:
    print(n)
else:
    print(n - l)

### FIXED CODE ###

a = list(map(int, input().split()))
n = a[0]
m = a[1]
l = a[2]
k = a[3]

if 0 < k <= n:
    print(k)

elif n < k <= n + m:
    print(n)

elif n+m <= k < n+m+l:
    print(n -1*(k -n -m))

elif n+m+l <= k:
    print(n - l)
else:
    print(0)
# B - K-th Common Divisor
# https://atcoder.jp/contests/abc120/tasks/abc120_b
import math

MAX = 100

def gcd(A, B):
    if B > A:
        A, B = A, B

    if B == 0:
        return A

    return gcd(B, A-(A/B)*B)

prime_table = [True]*MAX
prime_table[0] = prime_table[1] = False
for i in range(2, int(math.sqrt(MAX)) + 1):
    for j in range(i*2, MAX, i):
        prime_table[j] = False
primes = [i_idx for i_idx in range(len(prime_table)) if prime_table[i_idx] == True]

A, B, K = map(int, raw_input().split())
gcdAB = gcd(A, B)
factors = set()
factors.add(gcdAB)
factors.add(1)

for prime in primes:
    if prime > gcdAB:
        break
    if gcdAB % prime == 0:
        factors.add(prime)
        factors.add(gcdAB/prime)

factors = list(factors)
factors.sort(reverse=True)

print '{}'.format(factors[K - 1])


### FIXED CODE ###

# B - K-th Common Divisor
# https://atcoder.jp/contests/abc120/tasks/abc120_b
# 1WA
MAX = 100

def gcd(m, n):
    return m if n == 0 else gcd(n, m % n)

A, B, K = map(int, raw_input().split())
gcdAB = gcd(A, B)

cnt = 0
for n in range(gcdAB, 0, -1):
    if gcdAB % n == 0:
        cnt += 1
        if cnt == K:
            print '{}'.format(n)
            break
def Constrcuted(A,C,n):
    tree=[[] for i in range(n+1)]
    for i,j in A:
        tree[i] +=[j]
    top=[k+1 for k in range(n)]
    top=top[0]
    rootedTree(top,-1,tree[top],tree,C[top])


def rootedTree(node,parent,root,tree,point):
    B.append([node,parent,tree[node],point])
    for i in root:
        rootedTree(i,node,tree[i],tree,point+C[i])


n,q=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n-1)]
B=[]
C=[0 for i in range(n+1)]
for i in range(q):
    add,point=map(int,input().split())
    C[add] +=point

Constrcuted(A,C,n)
ans=[0]*n
for i in B:
    ans[i[0]-1]=i[3]
print(*ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

print(*ans)
S = input()
a = True
for i in range(len(S)):
    if len(S) % 2 != 0 :
        a = False 
        break
    else:
        if S[i/2] != 'h' or S[i/2 +1] != 'i':
            a = False
            break

if a = True: 
    print('Yes')
else : 
    print('No')
        
        

### FIXED CODE ###

S = input()
a = True
for i in range(len(S)):
    if len(S) % 2 != 0:
        a = False 
        break
    else:
        if i %2==0 and (S[i] != 'h' or S[i+1] != 'i'):
            a = False

if a: 
    print('Yes')
else: 
    print('No')
N=int(input())
list=list(input().split())
list.sort()
n=0
s=list[0]
for i in range(N):
  if list[i] != s:
    n+=1
    s=list[i]
print(n)

### FIXED CODE ###

N=int(input())
list=[input() for i in range(N)]
list.sort()
n=1
s=list[0]
for i in range(N):
  if list[i] != s:
    n+=1
    s=list[i]
print(n)
from itertools import*
n,a,b=eval('eval(input().replace(" ",",")),'*3)
i=list(permutations(range(n+1))).index
print(abs(i(a)-i(b)))

### FIXED CODE ###

from itertools import*;(n,),a,b=eval('tuple(map(int,input().split())),'*3);i=list(permutations(range(1,n+1))).index;print(abs(i(a)-i(b)))
if int(input()) + int(input()) >= int(input()):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b, c = map(int, input().split())
if a + b >= c:
    print("Yes")
else:
    print("No")
def main():
  from collections import Counter
  N=int(input())
  A=list(ma())
  evens = Counter(A[::2])
  odds = Counter(A[1::2])
  evens[0]=0 #この部分は文字列が小さい時に必要
  odds[0]=0 #
  
  e1, e2=evens.most_common(2) #上位２つを実際の数字をⅠ番目に、出てきた回数を２こめ
  o1, o2=odds.most_common(2) #
  
  if e1[0]!=o1[0]:
    print(N - (e1[1] + o1[1]))
  else: 
    print(N - max(e1[1]+o2[1], e2[1]+o1[1]))
  
if __name__ == '__main__':
  main()


### FIXED CODE ###

def ma():
  return map(int,input().split())

def main():
  from collections import Counter
  N=int(input())
  A=list(ma())
  evens = Counter(A[::2])
  odds = Counter(A[1::2])
  evens[0]=0 #この部分は文字列が小さい時に必要
  odds[0]=0 #
  
  e1, e2=evens.most_common(2) #上位２つを実際の数字をⅠ番目に、出てきた回数を２こめ
  o1, o2=odds.most_common(2) #
  
  if e1[0]!=o1[0]:
    print(N - (e1[1] + o1[1]))
  else: 
    print(N - max(e1[1]+o2[1], e2[1]+o1[1]))
  
if __name__ == '__main__':
  main()
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

N = int(input())
iXY = [[i] + list(map(int, input().split())) for i in range(N)]

P = []
for j in [1, 2]:
  iXY.sort(key=lambda a: a[j])
  for i in range(1, N):
    i0, x0, y0 =  iXY[i - 1]
    i1, x1, y1 =  iXY[i]
    P.append((min(abs(x1 - x0), abs(y1 - y0)), i0, i1))

d, i, j = zip(*P)
G = csr_matrix((d, (i, j)))
mst = minimum_spanning_tree(G)
print(int(mst.sum()))

### FIXED CODE ###

import heapq

N = int(input())
iXY = [[i] + list(map(int, input().split())) for i in range(N)]
G = [set() for _ in range(N)]

iXY.sort(key=lambda a: a[1])
for i in range(1, N):
  i0, x0, y0 = iXY[i - 1]
  i1, x1, y1 = iXY[i]
  G[i0].add((i1))
  G[i1].add((i0))

iXY.sort(key=lambda a: a[2])
for i in range(1, N):
  i0, x0, y0 = iXY[i - 1]
  i1, x1, y1 = iXY[i]
  G[i0].add((i1))
  G[i1].add((i0))

Q = [(0, 0)]
B = set()
a = 0
iXY.sort()

while True:
  d, v = heapq.heappop(Q)
  while v in B:
     d, v = heapq.heappop(Q)
  a += d
  B.add(v)
  if len(B) == N:
    break
  for i in G[v]:
    if i not in B:
      heapq.heappush(Q, (min(abs(iXY[v][1] - iXY[i][1]), abs(iXY[v][2] - iXY[i][2])), i))
print(a)
class UnionFind():
    def __init__(self,n):
        
        self.parents = [-1]*(n+1)

    def find(self, x):
        if self.parents[x] < x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
            
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]

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

uf = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    uf.union(a,b)

cnt = []
for i in uf.roots():
    cnt.append(i)
    
print(max(cnt))

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
        
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x,y = y,x
            
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

uf = UnionFind(n)

ab = [tuple(map(int,input().split())) for _ in range(m)]

for a,b in ab:
    uf.union(a-1,b-1)

ans = -1
for i in uf.parents:
    ans = min(i,ans)
    
print(-ans)
from scipy.special import comb

n = int(input())
s = []
for i in range(n):
    sin = input()
    sin = list(sin)
    sin.sort()
    sin = ''.join(sin)
    s.append(sin)

ss = set(s)
count = 0
for u in ss:
    al = s.count(u)
    count += comb(al, 2, exact=True)
print(count)

### FIXED CODE ###

import itertools

def comb(n, r):
    return len(list(itertools.combinations(range(n), r)))

def get_runlength(s): # ex) s = 'RRLLLLRLRLRLRR'
    ret = []
    count = 1
    for i in range(len(s)):
        if i == len(s) - 1:
            ret.append((s[i], count))
            continue
        if s[i] == s[i + 1]:
            count += 1
        else:
            ret.append((s[i], count))
            count = 1
    return ret

n = int(input())
dic = {}
for i in range(n):
    sin = input()
    sin = list(sin)
    sin.sort()
    sin = ''.join(sin)
    try:
        dic[sin] += 1
    except:
        dic[sin] = 1

count = 0
for v in dic.values():
    count += v * (v - 1) / 2
count = int(count)
print(count)
N = int(input())
B = map(int,input().split())

ans = B[0]
for i in range(N-2):
  ans += max([B[i],B[i+1]])

ans += B[N-2]

print(ans)

### FIXED CODE ###

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

ans = B[0]
for i in range(N-2):
  ans += min([B[i],B[i+1]])

ans += B[N-2]

print(ans)
n = int(input())
s = input()
count = 0

for i in range(n-2):
    if s[i] == "A":
        if s[i+1] == "B":
            if s[i+2] == "C":
                count += 1
print(count

### FIXED CODE ###

n = int(input())
s = input()
count = 0

for i in range(n-2):
    #print(s[i],s[i+1],s[i+2])
    if s[i] == "A":
        if s[i+1] == "B":
            if s[i+2] == "C":
                count += 1
print(count)
### C
import math

N = int(input())
A = [int(x) for x in input().split()]

left = [0] * (N+1)
right = [0] *(N+1)

for i in range(N):
    left[i+1] = math.gcd(left[i], A[i])
for i in reversed(range(N)):
    right[i] = math.gcd(right[i+1], A[i])
    
res = 0
for i in range(N):
    l = left[i]
    r = right[i+1]
    res = max(math.gcd(l, r), res)

print(res)

### FIXED CODE ###

### C

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

N = int(input())
A = [int(x) for x in input().split()]

left = [0] * (N+1)
right = [0] *(N+1)

for i in range(N):
    left[i+1] = gcd(A[i], left[i])
for i in reversed(range(N)):
    right[i] = gcd(A[i], right[i+1])
    
res = 0
for i in range(N):
    l = left[i]
    r = right[i+1]
    res = max(gcd(l, r), res)

print(res)
N, M, K = map(int, input().split())

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

books = 0

p1 = 0
p2 = 0

while K > 0 and ( p1 < N or p2 < M ):
    books += 1

    if p1 < N and A[p1] < B[p2]:
        # print("chosen", "p1", p1)
        K -= A[p1]
        p1 += 1

    elif p2 < M:
        # print("chosen", "p2", p2)
        K -= B[p2]
        p2 += 1

    # print(K, p1, p2)

# print(K)

if K < 0:
    books -= 1
    print(books)

elif K == 0:
    print(books)

else:
    if p1 < N:
        while K > 0 and p1 < N:
            books += 1
            K -= A[p1]
            p1 += 1

    if p2 < M:
        while K > 0 and p2 < M:
            books += 1
            K -= B[p2]
            p2 += 1

    print(books)

### FIXED CODE ###

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

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

A.insert(0, 0)
B.insert(0,0)

# convert to the cumulative/prefix sum
for i in range(1, len(A)):
    A[i] += A[i-1]

for i in range(1, len(B)):
    B[i] += B[i-1]

# print(A)
# print(B)

books_stack_a = 0

books_stack_b = M

cur_max = 0

for books_stack_a in range(0, N + 1):
    if A[books_stack_a] > K:
        break
    diff = K - A[books_stack_a]
    while diff < B[books_stack_b]:
        books_stack_b -= 1

    cur_max = max(cur_max, books_stack_b + books_stack_a)

print(cur_max)
N = int(input())
A = int(input())
C = 0
C = N % 500
if C <= A;
   print(Yes)
else;
   print(No)

### FIXED CODE ###

N = int(input());
A = int(input());
C = 0;
C = N % 500;
if C <= A:
  print("Yes");  
else:
  print("No");
X, Y, Z = map(int, input().split())
print((X-Z)/Y)

### FIXED CODE ###

X, Y, Z = map(int, raw_input().split())
print((X-Z)/(Y+Z))
from itertools import groupby, accumulate

# 入力
N, K = map(int, input().split())
S = input()

# 連続する0または1の数に関する累積和
A = list(accumulate(len(list(seq)) for _, seq in groupby(S))) + [N]
m = (
    1 if S[0] == '0' else
    0
)
# 累積和を用いて解を求める
ans = (
    max(
        A[2 * K - 1],
        A[-1] - A[-(2 * K)],
        max(
            (
                a - b
                for a, b in zip(A[(2 * K + m)::2], ([0] + A)[m::2])
            ),
            default=0
        )
    ) if m < len(A) else
    A[-1]
)

# 出力
print(ans)


### FIXED CODE ###

from itertools import groupby, accumulate

# 入力
N, K = map(int, input().split())
S = input()

# 連続する0または1の数に関する累積和
A = list(accumulate(len(list(seq)) for _, seq in groupby(S))) + [N]
m = (
    1 if S[0] == '0' else
    0
)
# 累積和を用いて解を求める
ans = (
    max(
        A[min(2 * K - 1, len(A) - 1)],
        A[-1] - A[max(-(2 * K), -len(A))],
        max(
            (
                a - b
                for a, b in zip(A[(2 * K + m)::2], ([0] + A)[m::2])
            ),
            default=0
        )
    ) if m < len(A) else
    A[-1]
)

# 出力
print(ans)
#!/usr/bin/env python3
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall, dijkstra
# G = csgraph_from_dense(edge, null_value=10**9)
# f = floyd_warshall(G)
# d = dijkstra(G, indices=1)
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

xs,ys,xt,yt=map(int,input().split())
n=int(input())
xyr=[(xs,ys,0),(xt,yt,0)]
data=[[0]*(n+2) for i in range(n+2)]
for i in range(n):
    xyr.append(tuple(map(int,input().split())))
for i in range(n+2):
    for j in range(n+2):
        x0=xyr[i][0];y0=xyr[i][1];r0=xyr[i][2]
        x1 = xyr[j][0];y1=xyr[j][1];r1=xyr[j][2]
        data[i][j]=max(((x0-x1)**2+(y0-y1)**2)**.5-r0-r1,0)
G = csgraph_from_dense(data, null_value=10**9)
d = dijkstra(G, indices=0)
print(d[1])



### FIXED CODE ###

def dijkstra(s):
    #始点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

Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

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

res = dijkstra(0)
print(res[1])
N = int(input())
n = N[-1]
if n == 2 or n == 4 or n == 5 or n == 7 or n == 9:
    print("hon")
elif n == 0 or n == 1 or n == 6 or n == 8:
    print("pon")
else:
    print("bon")

### FIXED CODE ###

N = input()
n = N[-1]
if n == "2" or n == "4" or n == "5" or n == "7" or n == "9":
    print("hon")
elif n == "0" or n == "1" or n == "6" or n == "8":
    print("pon")
else:
    print("bon")
n=int(input())
a=list(map(int,input().split()))
b=0
for i in range(n-1):
    minj=i
    for j in range(i+1,n-1):
        if a[minj]>a[j]:
            minj=j
    if i!=minj:
        a[i],a[minj]=a[minj],a[i]
            b+=1
print(*a)
print(b)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=0
for i in range(n):
    minj=i
    for j in range(i,n):
        if a[minj]>a[j]:
            minj=j
    if i!=minj:
        a[i],a[minj]=a[minj],a[i]
        b+=1
print(*a)
print(b)
from numpy import*
a=loadtxt(open(0),'i',skiprows=1)
n=x=len(a)
while a.any():
  t=bincount(a[:,0])
  x,a=min(x,max(t)),reshape(a[a!=argmax(t)],(n,-1))
print(x)

### FIXED CODE ###

from numpy import*
a=loadtxt(open(0),'i',skiprows=1,ndmin=2)
n=x=len(a)
while a.any():
  t=bincount(a[:,0])
  x,a=min(x,max(t)),reshape(a[a!=argmax(t)],(n,-1))
print(x)
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

S = list(input())
check = [0]*26
if len(S)==26:
    else:
        end = S[-1]
        for i in range(24, -1, -1):
            if ord(S[i])<ord(end):
                S[i] = end
                print(''.join(S[:i+1]))
                break
        else:
            if S[0]=='z':
                print(-1)
            else:
                print(chr(ord(S[0])+1))
else:
    for s in S:
        check[ord(s)-97] = 1
    for i in range(26):
        if not check[i]:
            S.append(chr(i+97))
            break
    print(''.join(S))



### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

S = list(input())
# while 1:
if len(S)==26:
    end = S[-1]
    lis = [end]
    for i in range(24, -1, -1):
        if ord(S[i])<ord(end):
            for s in lis:
                if ord(S[i])<ord(s):
                    S[i] = s
                    break
            S = S[:i+1]
            print(''.join(S))
            break
        else:
            lis.append(S[i])
            end = S[i]
    else:
        if S[0]=='z':
            print(-1)
        else:
            S = [chr(ord(S[0])+1)]
            print(S[0])
else:
    check = [0]*26
    for s in S:
        check[ord(s)-97] = 1
    for i in range(26):
        if not check[i]:
            S.append(chr(i+97))
            break
    print(''.join(S))