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

from heapq import heappush, heappop

sX, sY, tX, tY = map(int, input().split())
N = int(input())

XYR = [tuple(map(int, input().split())) for _ in range(N)] + [(sX, sY, 0), (tX, tY, 0)]
S, T = N, N + 1
N += 2

edges = [[] for _ in range(N)]
for i, (x, y, r) in enumerate(XYR):
    for j, (u, v, w) in enumerate(XYR[i + 1:], start=i + 1):
        dist = max(0, ((x - u)**2 + (y - v)**2)**0.5 - (r + w))
        edges[i].append((j, dist))
        edges[j].append((i, dist))

minDist = [10**18] * N
minDist[S] = 0
que = [(0, S)]
while que:
    dist, now = heappop(que)
    for to, cost in edges[now]:
        d = dist + cost
        if minDist[to] > d:
            minDist[to] = d
            heappush(que, (d, to))
print(minDist[T])


### FIXED CODE ###

sX, sY, eX, eY = map(int, input().split())
N = int(input())

circles = [(sX, sY, 0)]
for _ in range(N):
    cx, cy, r = map(int, input().split())
    circles.append((cx, cy, r))
circles.append((eX, eY, 0))

edges = [[float('inf')] * (N + 2) for _ in range(N + 2)]

for i, (cx1, cy1, r1) in enumerate(circles):
    for j, (cx2, cy2, r2) in enumerate(circles):
        cDist = ((cx1 - cx2)**2 + (cy1 - cy2)**2)**0.5
        dist = max(0, cDist - r1 - r2)

        edges[i][j] = dist
        edges[j][i] = dist

minDist = [float('inf')] * (N + 2)
minDist[0] = 0
confilm = [False] * (N + 2)

for _ in range(N + 2):
    md = float('inf')
    minNode = -1
    for n in range(N + 2):
        if not confilm[n] and md > minDist[n]:
            minNode = n
            md = minDist[n]
    confilm[minNode] = True
    for to in range(N + 2):
        minDist[to] = min(minDist[to], minDist[minNode] + edges[minNode][to])

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

N=int(input())
A=[]
for i in range(5):
    A.append(int(input()))
B=[N,0,0,0,0,0]
j=0
while B[5]!=N:
        C=[]
        C.append(B[0]-min(B[0],A[0]))
        for i in range(4):
             C.append(B[i+1]+min(B[i],A[i])-min(B[i+1],A[i+1]))
        C.append(B[5]+min(B[4],A[4]))
        B=C
        j=j+1
print(j)

### FIXED CODE ###

N=int(input())
A=[]
for i in range(5):
    A.append(int(input()))
a=min(A)
if N%a==0:
    print(5+N//a-1)
else:
    print(5+N//a)
### BUGGY CODE ###

N=int(input())
word=set()
number=[]
S=list(map(int,input()))
for i in range(10):
    for j in range(10):
        for k in range(10):
           number.append([str(i)+str(j)+str(k)])
ans=0
for i in number:
    count=0
    for s in range(N):
        if int(i[0][count])==S[s]:
            count+=1
            if count==3:
                ans+=1
                break

print(ans)




### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=str(input())
l=[0]*q
r=[0]*q
for i in range(q):
        l[i],r[i]=map(int,input().split())

t=s.replace('A'+'C','*_')
a=[0]
for i in range(n):
        if t[i]=='*':
                a.append(i+1)
a.append(len(s))
for i in range(q):
        count=0
        for j in range(len(a)):
                if l[i]<=a[j]<=r[i]-1:
                        count+=1
        print(count)




### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=str(input())

t=[0]*n
for i in range(n-1):
        t[i+1]=t[i]+(1 if s[i:i+2]=='AC' else 0)
for j in range(q):
        l,r=map(int,input().split())
        print(t[r-1]-t[l-1])
### BUGGY CODE ###

X, K, D = map(int, input().rstrip().split())
before = X
for i in range(K):
  buf = X
  if X<0:
    X += D
  else:
    X -= D
  if X == before:
    if (K-i)%2 == 0:
      if X<0:
        X += D
      else:
        X -= D
    else:
      X = before
    break
  before=buf
print(abs(X))

### FIXED CODE ###

X, K, D = map(int, input().rstrip().split())
before = X

if abs(X)//D>=K:
  print(abs(X)-D*K)
else:
  for i in range(K):
    buf = X
    if X<0:
      X += D
    else:
      X -= D
    if X == before:
      if (K-i)%2 == 0:
        if X<0:
          X += D
        else:
          X -= D
      else:
        X = before
      break
    before=buf
  print(abs(X))
### BUGGY CODE ###

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

for m in range(M):
    list.sort(A, reverse=True)
    A[0] = int(A[0] / 2)
print(sum(A))

### FIXED CODE ###

import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))
q = []
for x in A:
    heapq.heappush(q, -x)
for m in range(M):
    x = heapq.heappop(q)
    x /= 2
    heapq.heappush(q, x)
ans = 0
for x in q:
    ans += int(-x)
print(ans)
### BUGGY CODE ###

sn,sm = input().split(" ")
n = int(sn)
m = int(sm)
sa = input().split(" ")
l = len(sa)
a = []
 
for i in range(l):
  a.append(int(sa[i]))
 
for i in range(m):  
  ind = a.index(max(a))
  a[ind] = a[ind] //2
  
print(sum(a))

### FIXED CODE ###

class Heap:

    # 初期化
    def __init__(self):
        self.array = []

    def num(self):
        return len(self.array)
        
    # valを追加する
    def put(self, val):
        pos = len(self.array)
        # valを末尾に追加する
        self.array.append(val)
        # valを適当な位置まで上にあげる
        self.pop_up(pos)
        
    # 最大の要素を取り出す
    def get(self):
        assert len(self.array) > 0

        val = self.array[0]
        
        # 末尾の要素を0に移動してから下に下げる
        t_val = self.array[-1]
        self.array[0] = t_val
        del self.array[-1]
        self.push_down(0)
        return val

    # posの位置の要素を適当な位置まで上げる
    def pop_up(self, pos):
        while pos > 0:
            p_pos = (pos - 1) // 2
            val = self.array[pos]
            p_val = self.array[p_pos]
        
            if val > p_val:
                self.array[pos] = p_val
                self.array[p_pos] = val
                pos = p_pos
            else:
                break
            
    def push_down(self, pos):
        while True:
            l_pos = 2 * pos + 1
            r_pos = 2 * pos + 2
            n = len(self.array)
            
            if n <= l_pos:
                # 子がいない場合
                break
            
            elif n == r_pos:
                # 子が一人の場合
                val = self.array[pos]
                l_val = self.array[l_pos]
                
                if val < l_val:
                    self.array[pos] = l_val
                    self.array[l_pos] = val
                    
                break #
            
            else:
                # 子が二人いるとき
                val = self.array[pos]
                l_val = self.array[l_pos]
                r_val = self.array[r_pos]
                
                if l_val > r_val:
                    if val < l_val:
                        self.array[pos] = l_val
                        self.array[l_pos] = val
                        pos = l_pos
                    else:
                        break
                else:
                    if val < r_val:
                        self.array[pos] = r_val
                        self.array[r_pos] = val
                        pos = r_pos
                    else:
                        break

                        
h = Heap()
sn,sm = input().split(" ")
n = int(sn)
m = int(sm)
sa_list = input().split(" ")


for sa in sa_list:
  a = int(sa)  
  h.put(a)
 
for i in range(m):  
    max_a = h.get()
    h.put(max_a // 2)

    

print(sum(h.array))
### BUGGY CODE ###

n=int(input())
s=[]
for i in range(n):
    s.append(int(input()))
ans=0
for i in range(2**n):
    score=0
    for j in range(n):
        if i>>j&1:
            score+=s[j]
    if score%10!=0:
        ans=max(ans,score)
print(ans)


### FIXED CODE ###

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

if sum(s)%10==0:
    for i in range(n):
        if s[i]%10!=0:
            print(sum(s)-s[i])
            exit()
    print(0)
    exit()
print(sum(s))
### BUGGY CODE ###

s = input()
t = input()

ss = len(s)
tt = len(t)

dp = [[[] for _ in range(tt)] for __ in range(ss)]

if s[0] == t[0]:
    dp[0][0].append(s[0])

for i in range(1,ss):
    if s[i] == t[0]:
        dp[i][0].append(t[0])
    else:
        dp[i][0] = dp[i-1][0][:]

for j in range(1,tt):
    if s[0] == t[j]:
        dp[0][j].append(s[0])
    else:
        dp[0][j] = dp[0][j-1][:]

for i in range(1, ss):
    for j in range(1, tt):
        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1][:]
            dp[i][j].append(s[i])
            if len(dp[i][j]) < len(dp[i][j-1]):
                dp[i][j] = dp[i][j-1][:]
            if len(dp[i][j]) < len(dp[i-1][j]):
                dp[i][j] = dp[i-1][j][:]
        else:
            if len(dp[i][j-1]) < len(dp[i-1][j]):
                dp[i][j] = dp[i-1][j][:]
            else:
                dp[i][j] = dp[i][j-1][:]

print(''.join(dp[ss-1][tt-1]))


### FIXED CODE ###

s = input()
t = input()

ss = len(s)
tt = len(t)

dp = [[0 for _ in range(tt+1)] for __ in range(ss+1)]

for i in range(1, ss+1):
    for j in range(1, tt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i-1][j-1] + 1, dp[i][j-1], dp[i-1][j])
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])

i = ss
j = tt
ans = []

while i>0 and j>0:
    if s[i-1] == t[j-1]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    else:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            j -= 1

print(''.join(reversed(ans)))
### BUGGY CODE ###

N,M,Q = map(int,input().split())
abcd = []
for i in range(Q):
    abcd.append(list(map(int,input().split())))
abcd.sort()

import itertools
LIST = []
for i in range(1,M+1):
    LIST.extend([i for j in range(N)])
A = list(itertools.combinations(LIST,N))
# print(A)
ans = 0
for item in A:
    tmp = 0
    for req in abcd:
        if item[req[1]-1] - item[req[0]-1] == req[2]:
            tmp+= req[3]
    ans = max(ans,tmp)
print(ans)

### FIXED CODE ###

N,M,Q = map(int,input().split())
abcd = []
for i in range(Q):
    abcd.append(list(map(int,input().split())))
abcd.sort()

import itertools
A = list(itertools.combinations_with_replacement(range(1,M+1),N))
# print(A)
ans = 0
for item in A:
    tmp = 0
    for req in abcd:
        if item[req[1]-1] - item[req[0]-1] == req[2]:
            tmp+= req[3]
    ans = max(ans,tmp)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = []
if n % k == 0:
  print(0)
else :
  while n > 0 :
    n -= k
    a.append(n)
    
  if len(a) == 1 : 
    if a[-1] * -1 > n + k :
      print(n + k)
    else :
      print(a[-1] * -1)

  else :
    if (a[-1]) * -1 > a[-2] :
      print(a[-2])
    else :
      print((a[-1]) * -1)

### FIXED CODE ###

n, k = map(int, input().split())
a = []
if n % k == 0:
  print(0)

elif n // k == 0 :
  if -(n - k) > n :
    print(n)
  else :
    print(-(n - k))

else :
  if n % k > (n % k) - k :
    print(-((n % k) - k))
  else :
    print(n % k)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, S, n):
        self.size = n
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


n = int(input())
S = list(input())
S = [s for s in S]
segtree = SegmentTree(S, 19)
for _ in range(int(input())):
    t, i, c = input().split()
    if t == '1':
        segtree.update(int(i)-1, c)
    if t == '2':
        print(segtree.query(int(i)-1, int(c)))


### FIXED CODE ###

import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, S):
        self.size = 19
        self.array = [set()] * (2**(self.size + 1) - 1)
        for i, c in enumerate(S):
            self.array[i + 2**self.size - 1] = {c}
        for i in range(2**self.size - 1)[::-1]:
            self.array[i] = self.array[2 * i + 1] | self.array[2 * i + 2]

    def subquery(self, l, r, k, i, j):
        # 区間[i,j)の中で区間[l,r)の文字列の集合を返す
        if j <= l or r <= i:
            return set()
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_set = self.subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_set = self.subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return l_set | r_set

    def query(self, l, r):
        # [l,r)に含まれる文字の種類数
        return len(self.subquery(l, r, 0, 0, 2**self.size))

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = {c}
        while tmp > 0:
            tmp = (tmp - 1) // 2
            self.array[tmp] = self.array[2 * tmp + 1] | self.array[2 * tmp + 2]


def main():
    N = int(input())
    S = [ord(_) - 97 for _ in list(input())]
    Q = int(input())
    tree = SegmentTree(S)
    for q in range(Q):
        t, i, c = input().split()
        if t == '1':
            i = int(i) - 1
            tree.update(i, ord(c) - 97)
        else:
            l, r = int(i) - 1, int(c)
            print(tree.query(l, r))


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

n = int(input())
s = list(map(int,input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    if n%2 ==0:
        dp[i][i]=-s[i]
        turn =0
    else:
        dp[i][i]=s[i]
        turn = 1
def findMax(i,j):
    dp[i][j] = max(dp[i+1][j]+s[i],dp[i][j-1]+s[j])
def findMin(i,j):
    dp[i][j]= min(dp[i+1][j]-s[i],dp[i][j-1]-s[j])
for length in range(2,n+1):
    for j in range(n-length+1):
        if not turn:
            findMax(j,j+length-1)
        else:
            findMin(j,j+length-1)
    turn^=1

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



### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    if n%2 ==0:
        dp[i][i]=-s[i]
        turn =0
    else:
        dp[i][i]=s[i]
        turn = 1
def findMax(i,j):
    dp[i][j] = max(dp[i+1][j]+s[i],dp[i][j-1]+s[j])
def findMin(i,j):
    dp[i][j]= min(dp[i+1][j]-s[i],dp[i][j-1]-s[j])
for length in range(2,n+1):
    for j in range(n-length+1):
        if not turn:
            findMax(j,j+length-1)
        else:
            findMin(j,j+length-1)
    turn^=1

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

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

MOD = 10**9+7
def MakeCombList(n,r, MOD): #iCrをi=0...nまで
    ret = []
    for i in range(n):
        if i < r:
            ret = ret+[0]
        elif i == r:
            ret = ret+[1]
        else:
            ret = ret+[ int(ret[-1]*(i)/(i-r)) % MOD]
    return ret
combB1 = MakeCombList(B+W, B-1, MOD)
combW1 = MakeCombList(B+W, W-1, MOD)

y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
for i in range(B+W):
    y_pi = 0 if i < B else 2*y_pi + combB1[i-1] 
    y_qi = 0 if i < W else 2*y_qi + combW1[i-1]
    xi = pow(2,i+1,MOD)
    yi = (pow(2,i,MOD)-y_pi+y_qi) % MOD
    z = yi*pow(xi, MOD-2, MOD) % MOD
    print(z)

### FIXED CODE ###

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

MOD = 10**9+7

facts = [1,1] #階乗
invs = [1,1] #整数の逆元
invfacts = [1,1] #階乗の逆元
for ind in range(1, B+W):
    i = ind+1
    facts.append(facts[-1]*i % MOD)
    invs.append( -(MOD//i)*invs[MOD%i] % MOD )
    invfacts.append( invfacts[-1]*invs[i] % MOD )

def Comb(n, r, MOD=MOD):
    if n < r:
        return 0
    return facts[n]*invfacts[n-r]*invfacts[r] % MOD

y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
pow2 = 1
invxi = 1
inv2 = invs[2]
for i in range(B+W):
    #y_pi = 0 if i < B else 2*y_pi + ((facts[i-1]*invfacts[i-B] % MOD)*invfacts[B-1] % MOD)
    y_pi = (2*y_pi + Comb(i-1, B-1))%MOD
    #y_qi = 0 if i < W else 2*y_qi + ((facts[i-1]*invfacts[i-W] % MOD)*invfacts[W-1] % MOD)
    y_qi = (2*y_qi + Comb(i-1, W-1))%MOD
    invxi = invxi * inv2 % MOD
    yi = (pow2-y_pi+y_qi) % MOD
    z = yi*invxi % MOD
    print(z)
    pow2 = pow2*2 %MOD
### BUGGY CODE ###

L, R = list(map(int, input().split()))

min_value = 2019

for i in range(L, R+1):
	for j in range(L, R+1):
		if i >= j:
			continue

		value = (i * j) % 2019
		if value < min_value:
			min_value = value

print(min_value)


### FIXED CODE ###

L, R = list(map(int, input().split()))

min_value = 2019

for i in range(L, R+1):
	for j in range(L, R+1):
		if i >= j:
			continue

		value = (i * j) % 2019
		if value < min_value:
			min_value = value

		if min_value == 0:
			print(min_value)
			exit()

print(min_value)
### BUGGY CODE ###

s = input()
num =list(map(int, list(s)))
k = int(input())
days = int(5e15)
for i in range(days):
    temp = s[:k]
    for j in num:
         s = s.replace(str(j), str(j)*j)
    if temp == s[:k]:
        break 
print(s[k-1])


### FIXED CODE ###

s,k = [input() for i in range(2)]
for i in range(int(k)):
    if int(s[i]) > 1:
        print(s[i])
        exit()
print(1)
### BUGGY CODE ###

N,X=map(int,input().split())
x=list(map(int,input().split()))
L=sorted(x+[X])
if N==1:
	print(abs(X-x[0]))
else:
	LL=[L[i+1]-L[i] for i in range(N)]
	M=min(LL)
	while any([l%M!=0 for l in LL]):
		M=M-1
	print(M)


### FIXED CODE ###

from functools import reduce
N,X=map(int,input().split())
x=list(map(int,input().split()))
L=x+[X]
if N==1:
	print(abs(X-x[0]))
else:
	LL=[abs(L[i+1]-L[i]) for i in range(N)]
	def gcd(a,b):
		while b>0:
			a,b=b,a%b
		return a
	print(reduce(gcd,LL))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

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

    lst = [[0] * (N + 1) for _ in range(N + 1)]

    for _ in range(M):
        L, R = map(int, input().split())
        for l in range(L + 1):
            lst[l][R] += 1

    for l in range(N + 1):
        for r in range(N):
            lst[l][r + 1] += lst[l][r]

    # for tmp in lst:
    #     print (tmp)

    for _ in range(Q):
        p, q = map(int, input().split())
        print (lst[p][q])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
N, M, Q = map(int, input().split())

#input
lst = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    L, R = map(int, input().split())
    lst[R][L] += 1

lst = np.array(lst)
# print (lst)

#2次元累積和
for i in range(1, N + 1):
    lst[:,i] += lst[:, i - 1]
for j in range(1, N + 1):
    lst[j,:] += lst[j - 1, :]


#output
for _ in range(Q):
    p, q = map(int, input().split())
    print (lst[q, q] - lst[p-1, q] - lst[q, p-1] + lst[p-1, p-1])

# print (lst)
### BUGGY CODE ###

N = int(input())
p = list(map(int, input().split()))
M = []
for i in range(N):
    M.append(min(p[:i+1]))

cnt = 0
for i in range(N):
    if p[i]==M[i]:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
m = 10**6
for i in p:
    if i < m:
        m = i
        cnt += 1
print(cnt)
### BUGGY CODE ###

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

I = []
J = []
K = []

for n in range(1,N+1):
  if S[n-1] == "R":
    I.append(n)
  elif S[n-1] == "G":
    J.append(n)
  else:
    K.append(n)
    
cnt = 0
for a in I:
  for b in J:
    for c in K:
      ls = [a,b,c]
      ls.sort()
      if ls[1] - ls[0] != ls[2] - ls[1]:
        cnt += 1
    
print(cnt)

### FIXED CODE ###

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

ans = S.count("R") * S.count("G") * S.count("B")

for i in range(1,N-1):
  for j in range(i+1,N):
    k = 2 * j - i
    if k > N:
      break
    if S[i-1] != S[j-1] and S[j-1] != S[k-1] and S[k-1] != S[i-1]:
      ans -= 1
      
print(ans)
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))
result = 1
 
for a in As:
  result *= a
 
if result > 10**18:
  print(-1)
else:
  print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
result = 1
 
if 0 in A:
  print(0)
  exit()

for a in A:
  result *= a
  if result > 10**18:
    print(-1)
    exit()

print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

dp = {}
for i in range(1, n + 1):
    dp[(i, 0)] = 0
    dp[(i, 1)] = c[p[i]]

def score(i, k, route):
    if (i, k) in dp:
        return dp[(i, k)]
    else:
        if i in route and k >= len(route):
            tmp_ans = 0
            for r in route:
                tmp_ans += dp[(r, 1)]
            return (tmp_ans * (k // len(route))) + score(p[i], k % len(route), route)
        else:
            route = route.copy()
            route.add(i)
            return c[p[i]] + score(p[i], k - 1, route)

ans = None
for i in range(1, n + 1):
    for j in range(1, k + 1):
        tmp_ans = score(i, j, set())
        if ans == None:
            ans = tmp_ans
        else:
            ans = max(ans, tmp_ans)
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

from collections import deque

def bfs(queue, cycle_index, cycle_num):
    cycle = []
    score = 0
    while queue:
        current = queue.popleft()
        cycle_index[current] = cycle_num
        cycle.append(current)
        score += c[current]

        if p[current] not in cycle_index:
            queue.append(p[current])
    return cycle, score

cycle_index = {}
cycle_num = 0
cycles = []
for i in range(1, n + 1):
    if i in cycle_index:
        continue
    queue = deque([i])
    cycle, score = bfs(queue, cycle_index, cycle_num)
    cycles.append((cycle, score))
    cycle_num += 1

ans = None
for i in range(1, n + 1):
    cycle, score = cycles[cycle_index[i]]
    tmp_ans = 0

    cum = [0]
    current = i
    for j in range(1, len(cycle)):
        current = p[current]
        cum.append(cum[-1] + c[current])

    if score > 0:
        q = (k // len(cycle))
        r = k % len(cycle)
        # 一周しない方がいいケースがある
        # FYI: https://atcoder.jp/contests/abc175/submissions/15968040
        if r == 0:
            tmp_ans = max((score * q), (score * (q - 1)) + max(cum[1:]))
        else:
            tmp_ans = (score * q) + max(cum[1:r+1])
    else:
        r = min(k, len(cycle))
        tmp_ans = max(cum[1:r+1])

    if ans is None:
        ans = tmp_ans
    else:
        ans = max(ans, tmp_ans)
print(ans)
### BUGGY CODE ###

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

i=1
gcd=1
if(n==1):
    print(p)
else:
    while((i**n)<=p):
        if(p%(i**n)==0):
            gcd*=i
            n=n//(i**n)
            i+=1
    print(gcd)

### FIXED CODE ###

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

i=2
gcd=1
if(n>40):
    print(1)
elif(n==1):
    print(p)
else:
    while((i**n)<=p):
        if(p%(i**n)==0):
            #print(i)
            gcd*=i
            p/=(i**n)
            i-=1
        i+=1
        
    print(gcd)