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

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    K, A, B = map(int, input().split())
    cnt = 0
    if B - A >= 3:
        times = (K - (A - 1)) // 2
        if times >= 1:
            cnt += A
            for i in range(times):
                p,mod=divmod(cnt,A)
                temp = p * B
                cnt = temp + mod
            if (K - (A - 1)) // 2 == (K - (A - 1)) / 2:
                pass
            else:
                cnt += 1
        else:
            cnt = 1 + K
    else:
        cnt = 1 + K

    print(cnt)


resolve()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    K, A, B = map(int, input().split())
    cnt = 0
    if B - A >= 3:
        times = (K - (A - 1)) // 2
        if times >= 1:
            cnt += A
            cnt+=(B-A)*times
            if (K - (A - 1)) // 2 == (K - (A - 1)) / 2:
                pass
            else:
                cnt += 1
        else:
            cnt = 1 + K
    else:
        cnt = 1 + K

    print(cnt)


resolve()
### BUGGY CODE ###

# D - Knapsack Queries on a tree

import bisect

n = int(input())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, input().split())

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2
    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

dpkeys = [[ww for ww, vv in dp[u]] for u in range(len(dp))]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dpkeys[u], l) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l) if u > 0 else 0
    if l >= w[u]:
        s = max(s, v[u] + (solve(parent, l - w[u]) if u > 0 else 0))
    return s

q = int(input())
for i in range(q):
    u, l = map(int, input().split())
    print(solve(u - 1, l))


### FIXED CODE ###

# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, readline().split())

max_l = 10 ** 5
vshift = 21
mask = (1 << vshift) - 1

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0 << vshift) + 0, (w[0] << vshift) + v[0]]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend(x + (w[u] << vshift) + v[u] for x in dp[parent]
              if (x >> vshift) + w[u] <= max_l)
    ls.sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(ls)):
        if (ls[tail] >> vshift) == (ls[i] >> vshift):
            ls[tail] = ls[i]
        elif (ls[tail] & mask) < (ls[i] & mask):
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l << vshift) + mask) - 1
        return dp[u][x] & mask

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
h, w = map(int, input().split())
a = []
a = [[True] * (w + 2)]
for i in range(h):
    a.append([True] + [x == '#' for x in input()] + [True])
a.append([True] * (w + 2))
q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if a[i][j]:
            q.append((i, j))

count = 0
while True:
    qq = []
    for i, j in q:
        if not a[i-1][j]:
            a[i-1][j] = True
            qq.append((i - 1, j))
        if not a[i+1][j]:
            a[i+1][j] = True
            qq.append((i + 1, j))
        if not a[i][j-1]:
            a[i][j-1] = True
            qq.append((i, j - 1))
        if not a[i][j+1]:
            a[i][j+1] = True
            qq.append((i, j + 1))
    q = qq
    if len(q) <= 0:
        break
    count += 1

print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
h, w = map(int, input().split())
a = []
a = [[True] * (w + 2)]
for i in range(h):
    a.append([True] + [x == '#' for x in input()] + [True])
a.append([True] * (w + 2))
q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if a[i][j]:
            q.append((i, j))

count = 0
while True:
    qq = []
    for i, j in q:
        if not a[i-1][j]:
            a[i-1][j] = True
            qq.append((i - 1, j))
        if not a[i+1][j]:
            a[i+1][j] = True
            qq.append((i + 1, j))
        if not a[i][j-1]:
            a[i][j-1] = True
            qq.append((i, j - 1))
        if not a[i][j+1]:
            a[i][j+1] = True
            qq.append((i, j + 1))
    q = qq
    if len(q) <= 0:
        break
    count += 1

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

import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product
from itertools import combinations

# input = sys.stdin.readline
N = int(input())
Cn = list(input())
Cc = copy.copy(Cn)
if (Cn[0] == "R"):
    Rflg = True
else:
    Rflg = False
ans = 0
    
for i in range(N):
    if Rflg and Cc[i] == "R":
        continue
    else:
        Rflg = True
    if Cc[i] == "W":
        for j in range(N-1, i, -1):
            if Cc[j] == "R":
#                 print("change")
                ans += 1
                Cc[i], Cc[j] = Cc[j], Cc[i]
#                 print(Cc)
                break
    else:
#         print("replace")
        ans += 1
        Cc[i] = "W"
#         print(Cc)
print(ans)


















### FIXED CODE ###

import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product
from itertools import combinations

# input = sys.stdin.readline
N = int(input())
Cn = list(input())

Cc = copy.copy(Cn)
if (Cn[0] == "R"):
    Rflg = True
else:
    Rflg = False
ans = 0
K = N-1    
allw = False
for i in range(N):
    if Rflg and Cc[i] == "R":
        continue
    else:
        Rflg = True
    if Cc[i] == "W":
        for j in range(K, i, -1):
            if Cc[j] == "R":
#                 print("change")
                ans += 1
                Cc[i], Cc[j] = Cc[j], Cc[i]
                K = j
#                 print(Cc)
                break
        else:
            allw = True

    else:
#         print("replace")
        ans += 1
        Cc[i] = "W"
#         print(Cc)
    if allw:
        break

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

def gcd(a,b):
    if a<b:
        a,b=b,a
    if b==0:
        return a
    else:
        return gcd(b,a%b)
N=int(input())
A=list(map(int,input().split()))
L=[0]
R=[0]
for i in range(N-1):
    L=L+[gcd(L[-1],A[i])]
    R=[gcd(R[0],A[N-i-1])]+R
M=[gcd(L[n],R[n]) for n in range(N)]
print(max(M))

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

N=int(input())
A=list(map(int,input().split()))
x=A[0]
y=A[1]
D=sorted(list(set(make_divisors(x))|set(make_divisors(y))))[::-1]
for d in D:
    if sum([a%d==0 for a in A])>=N-1:
        break
print(d)
### BUGGY CODE ###

n = int(input().split()[0])
warukazu = 10 ** 9 + 7
x = 1
for i in range(1, n+1):
    x = x * i

print(x % warukazu)

### FIXED CODE ###

n = int(input().split()[0])
warukazu = 10 ** 9 + 7
x = 1
for i in range(1, n+1):
    x = (x * i) % warukazu

print(x % warukazu)
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    from sys import stdin
    def input() : return stdin.readline().rstrip()
    N,M = map(int,input().split())
    dist = [-1 for _ in range(N)]
    G = dict()
    for i in range(N):
        G[i] = []   
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = [0]
    pre = [0] * N
    dist[0] = 0
    while (q != []):
        v = q[0]
        q.remove(q[0])
        for vertex in G[v]:
            if dist[vertex] != -1:
                continue
            dist[vertex] = dist[v] + 1
            pre[vertex] = v
            q.append(vertex)
    print("Yes")
    for v in range(1,N): 
        print(pre[v]+1)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    from sys import stdin
    def input() : return stdin.readline().rstrip()
    N,M = map(int,input().split())
    dist = [-1] * N
    G = dict()
    for i in range(N):
        G[i] = []   
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = [0]
    pre = [0] * N
    dist[0] = 0
    while (q != []):
        v = q[0]
        q.remove(q[0])
        for vertex in G[v]:
            if dist[vertex] != -1:
                continue
            dist[vertex] = dist[v] + 1
            pre[vertex] = v
            q.append(vertex)
    print("Yes")
    for v in range(1,N): 
        print(pre[v]+1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import itertools
def readInt():
    return list(map(int,input().split()))
n, k = readInt()
ans = 0
l = [int(x) for x in range(n+1)]
for i in range(k,n+2):
    # print(i, ".")
    c_l = list(itertools.combinations(l,i))
    a = []
    for j in range(len(c_l)):
        # print(sum(c_l[j]))
        a.append(sum(c_l[j]))
        # print(a)
    # print(a)
    # print(set(a))
    # print(c_l)
    ans += len(set(a))
print(ans)

### FIXED CODE ###

import itertools
def readInt():
    return list(map(int,input().split()))
n, k = readInt()
ans = 0
# l = [int(x) for x in range(n+1)]
for i in range(k,n+2):
    smallest = (i-1)*i /2
    largest = n*(n+1)/2 - (n-i)*(n-i+1)/2
    ans += int(largest - smallest + 1)
    ans %= 10**9 + 7
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

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

# 素因数分解、リストで返す
#############################################################
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)
    a.sort()
    return a
#############################################################

primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# 全て1の時、primesが空になってmaxが取れない
if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
# min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

# 素因数分解、リストで返す
#############################################################


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)
    a.sort()
    return a
#############################################################


primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

from operator import itemgetter

N = int(input())
X=[]
ans=0
for i in range(N):
    H = list(map(int, input().split()))
    O=[]
    O.append(H[0]-H[1])
    O.append(H[0]+H[1])
    X.append(O)
#print(X)
while(len(X)>0):
    X=sorted(X, key=itemgetter(1))
    #print(X)
    ans+=1
    S=X[0][1]
    X.remove(X[0])
    I = []
    for i in range(len(X)):
        if(X[i][0]>=S):
            I.append(X[i])
    X=I
    #print(I)



print(ans)


### FIXED CODE ###

from operator import itemgetter

N = int(input())
X=[]
ans=0
for i in range(N):
    H = list(map(int, input().split()))
    O=[]
    O.append(H[0]-H[1])
    O.append(H[0]+H[1])
    X.append(O)
#print(X)
X=sorted(X, key=itemgetter(1))
S=X[0][1]
ans+=1
for i in range(len(X)):
    if(X[i][0]>=S):
        ans+=1
        S=X[i][1]
"""
while(len(X)>0):
    #print(X)
    ans+=1
    S=X[0][1]
    X.remove(X[0])
    I = []
    for i in range(len(X)):
        if(X[i][0]>=S):
            I.append(X[i])
    X=I
    #print(I)
"""


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

k, s = map(int, input().split())
# print(k, s)
count = 0
for i in range(k+1):
    for j in range(k+1):
        for k in range(k+1):
            # print(i, j, k)
            if i + j + k == s:
                count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
# print(k, s)
count = 0
for x in range(k+1):
    for y in range(k+1):
        # print(x, y)
        if 0 <= s - x - y <= k:
            count += 1
print(count)
### BUGGY CODE ###

import numpy as np
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
count = 0
lis = np.array([0] * (10 ** 5))
lis = np.array(lis)
for n in range(N):
    a, b = map(int, input().split())
    lis[a - 1:] += b
print(bisect_left(lis, K) + 1)

### FIXED CODE ###

import numpy as np
from bisect import bisect_left, bisect_right
N, K = map(int, input().split())
count = 0
lis = np.array([0] * (10 ** 5))
for n in range(N):
    a, b = map(int, input().split())
    lis[a - 1] += b
for n in range(100000):
    K -= lis[n]
    if K <= 0:
        print(n + 1)
        break
### BUGGY CODE ###

n = int(input())
ls = {}
ls[1] = 1
ans = 0
for i in range(2,n+1):
    ls[i] = ls[i-1]+i
for j in range(1,n+1):
    if ls[j] >= n:   
        ans = j
        break
for k in range(1,ans+1):
    if ls[ans] - n != k:
        print(k)
    else:
        continue

### FIXED CODE ###

n = int(input())
a = 1
ans = 0
if a >= n:
    ans = 1
else:
    for i in range(2,n+1):
        a += i
        if a >= n:
            ans = i
            break
for k in range(1,ans+1):
    if a - n != k:
        print(k)
    else:
        continue
### BUGGY CODE ###

n,k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [float('inf')]*n
dp[0] = 0

for i in range(1,n):
    for j in range(1,k+1):
        if i >= j:
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
        else:
            break

print(dp[n-1])

### FIXED CODE ###

n,k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
inf = 10**10
dp = [inf]*n
dp[0] = 0
 
for i in range(1,n):
    dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]) for j in range(min(i,k)+1))
 
print(dp[n-1])
### BUGGY CODE ###

x = int(input())
a,b = 0,0
for i in range(x+1):
    if i**5 > x:
        a = i-1
        break
for i in range(x+1):
    if a**5 - i**5 == x:
        b = i
        break
    elif a**5 + i**5 == x:
        b = -i
        break
print(a,b)

### FIXED CODE ###

x = int(input())
a,b = 0,0
f = 0
for i in range(int(x**0.25)+1):
    for j in range(int(x**0.25)+1):
        if i**5 - j**5 == x:
            a = i
            b = j
            f = 1
            break
        elif i**5 + j**5 == x:
            a = i
            b = -j
            f = 1
            break
    if f:
        break
print(a,b)
### BUGGY CODE ###

from math import sqrt

def is_prime(n):
  if n == 1:
    return False
  for i in range(2, int(sqrt(n))+1):
    if n % i == 0:
      return False
  return True

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(sqrt(n))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
        if len(arr) > 1:
          break

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

base=int(input())
tmp=base
num=[]
if is_prime(base):
  num.append(base)
else:
  for i in range(2, base+1):
    if i > tmp:
      break
    if tmp % i == 0 and len(factorization(i)) == 1:
      num.append(i)
      tmp/=i
print(len(num))

### FIXED CODE ###

from math import sqrt

def is_prime(n):
  if n == 1:
    return False
  for i in range(2, int(sqrt(n))+1):
    if n % i == 0:
      return False
  return True

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(sqrt(n))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
        if len(arr) > 1:
          break

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

base=int(input())
tmp=base
num=[]
if is_prime(base):
  num.append(base)
else:
  for i in range(2, base+1):
    if i > tmp:
      break
    if tmp % i == 0 and len(factorization(i)) == 1:
      num.append(i)
      tmp/=i
      if is_prime(tmp):
        num.append(tmp)
        break
print(len(list(set(num))))
### BUGGY CODE ###

n = int(input())
s = list(str(input()))
l = [0]
for i in s:
  if l[0]!=i:
    l.insert(0,i)
print(len(l)-1)

### FIXED CODE ###

n = int(input())
s = str(input())
count = 1
for i in range(n-1):
  if s[i]!=s[i+1]:
    count+=1
print(count)
### BUGGY CODE ###

#D - Moving_piece
N,K = map(int,input().split())
P =[]
C =[]
P = list(map(int,input().split()))
C = list(map(int,input().split()))

score_output = -1000000010
i = 0
for i in range(N):
    ichi = i
    score = 0
    step  = 0
    loop  = 0
    score_max = -1000000010
    while True:
        step  += 1
        score += C[ichi]
        ichi   = (P[ichi] -1)
        if i ==  (P[ichi] -1):
            score += C[ichi]
            break
        
    path = 0
    cnt  = 0
    
    while True:
        cnt  += 1
        path += C[ichi]
        
        if cnt > K:
            break
        
        loop = int((K - cnt) / (step+ 1))
        if score > 0:
            score_max = path + loop * score
        else:
            score_max = path
        if score_max > score_output:
            score_output = score_max

        ichi   = P[ichi]-1
        if i == (P[ichi] -1):
            break
# 出力
print(score_output)

### FIXED CODE ###

#D - Moving_piece
N,K = map(int,input().split())
P =[]
C =[]
P = list(map(int,input().split()))
C = list(map(int,input().split()))

score_output = -1000000000
i = 0
for i in range(N):
    ichi = i
    score = 0
    step  = 0
    loop  = 0
    score_max = -1000000000
    while True:
        step  += 1
        score += C[ichi]
        ichi   = (P[ichi] -1)
        if i ==  (P[ichi] -1):
            score += C[ichi]
            break
        
    path = 0
    cnt  = 0
    
    while True:
        cnt  += 1
        path += C[ichi]
        
        if cnt > K:
            break
        
        loop = int((K - cnt) / (step+ 1))
        if score > 0:
            score_max = path + loop * score
        else:
            score_max = path
        if score_max > score_output:
            score_output = score_max

        ichi   = P[ichi]-1
        if i == (P[ichi] -1):
            break
# 出力
print(score_output)
### BUGGY CODE ###

import itertools
N,K=[int(i) for i in input().split()]
seq=[i for i in range(K)]
lst=[]
for i in itertools.product(seq, repeat=N):
    lst.append(i)

ans=[]
for tup in lst:
    f=0
    for ind,color in enumerate(tup):
        if(ind==len(tup)-1):
            break
        if(tup[ind+1]==color):
            f=1
            break
    if(f==0):
        ans.append(tup)
print(len(ans))

### FIXED CODE ###

import itertools
N,K=[int(i) for i in input().split()]
seq=[i for i in range(K)]
lst=[]
'''for i in itertools.product(seq, repeat=N):
    lst.append(i)

ans=[]
for tup in lst:
    f=0
    for ind,color in enumerate(tup):
        if(ind==len(tup)-1):
            break
        if(tup[ind+1]==color):
            f=1
            break
    if(f==0):
        ans.append(tup)
print(len(ans))'''

print(K*(K-1)**(N-1))
### BUGGY CODE ###

#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

import math,heapq
def pdist(x1,y1,x2,y2):
    return math.sqrt((x2-x1)**2+(y2-y1)**2)

xs,ys,xt,yt = inm()
n = inn()
cir = []
for i in range(n):
    x,y,r = inm()
    cir.append((x,y,r))
dst = [[0]*(n+2) for i in range(n+2)]
dst[n][n+1] = dst[n+1][n] = pdist(xs,ys,xt,yt)
for i in range(n):
    x,y,r = cir[i]
    dst[n][i] = dst[i][n] = max(0.0,pdist(xs,ys,x,y)-r)
    dst[n+1][i] = dst[i][n+1] = max(0.0,pdist(xt,yt,x,y)-r)
    for j in range(i+1,n):
        xx,yy,rr = cir[j]
        dst[j][i] = dst[i][j] = \
          max(0.0,pdist(xx,yy,x,y)-rr-r)

if False and DBG:
    for i in range(n+2):
        ddprint(dst[i])

cost = [float(BIG)]*(n+2)
q = [(0.0,n)]
while len(q)>0:
    d,p = heapq.heappop(q)
    #ddprint(f"{d=} {p=}")
    if cost[p]<=d:
        continue
    cost[p] = d
    for v in range(n+2):
        if v!=p:
            heapq.heappush(q,(d+dst[p][v], v))

print(cost[n+1])


### FIXED CODE ###

#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

#import math,heapq
from math import sqrt
from heapq import heappush,heappop

def pdist(x1,y1,x2,y2):
    return sqrt((x2-x1)**2+(y2-y1)**2)

xs,ys,xt,yt = inm()
n = inn()
cir = []
for i in range(n):
    x,y,r = inm()
    cir.append((x,y,r))
dst = [[0]*(n+2) for i in range(n+2)]
dst[n][n+1] = dst[n+1][n] = pdist(xs,ys,xt,yt)
for i in range(n):
    x,y,r = cir[i]
    dst[n][i] = dst[i][n] = max(0.0,pdist(xs,ys,x,y)-r)
    dst[n+1][i] = dst[i][n+1] = max(0.0,pdist(xt,yt,x,y)-r)
    for j in range(i+1,n):
        xx,yy,rr = cir[j]
        dst[j][i] = dst[i][j] = \
          max(0.0,pdist(xx,yy,x,y)-rr-r)

if False and DBG:
    for i in range(n+2):
        ddprint(dst[i])

cost = [float(BIG)]*(n+2)
q = [(0.0,n)]
while len(q)>0:
    d,p = heappop(q)
    #ddprint(f"{d=} {p=}")
    if cost[p]<=d:
        continue
    cost[p] = d
    for v in range(n+2):
        newdist = d+dst[p][v]
        if v!=p and newdist<cost[v]:
            heappush(q,(newdist, v))

print(cost[n+1])
### BUGGY CODE ###



import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    d1 = set()
    dN = set()
    for _ in range(iM):
        a,b = [int(_) for _ in sys.stdin.readline().split()]
        if a == 1 :
            d1.add(b)
        if b == iN:
            dN.add(a)
        if d1 & dN :
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")
解()


### FIXED CODE ###

import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    aAB = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    dT = {}
    def addTree(dT,a,b):
        if a in dT:
            dT[a].add(b)
        else:
            dT[a] = {b}
    for a,b in aAB:
        addTree(dT,a,b)
        addTree(dT,b,a)
    if  1 not in dT or iN  not in dT:
        print("IMPOSSIBLE")
    elif 0 < len(dT[1] & dT[iN]) :
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
解()