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

# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def bfs(graph, start, query):
    queue = deque([])
    acc = query[start] if start in query else 0
    queue.append([start, acc])
    ans = {start:acc}

    while queue:
        idx, acc = queue.popleft()
        for child in graph[idx].keys():
            if child in ans:
                continue
            ans[child] = acc
            if child in query:
                ans[child] += query[child]
            queue.append([child, ans[child]])
    return ans

n,q = map(int, input().split())
tree = {}
start = 1
for i in range(n-1):
    a,b = map(int, input().split())
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

query = {}
for _ in range(q):
    p, x = map(int,input().split())
    if p not in query:
        query[p] = x
    else:
        query[p] += x
ans = bfs(tree, start, query)
[print(ans[i], end=' ') for i in range(1, n+1)]


### FIXED CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def bfs(graph, start, query, n):
    queue = deque([])
    acc = query[start] if start in query else 0
    queue.append([start, acc])
    ans = [-1] * n
    ans[start] = acc

    while queue:
        idx, acc = queue.popleft()
        for child in graph[idx].keys():
            if ans[child] >= 0:
                continue
            ans[child] = acc
            if child in query:
                ans[child] += query[child]
            queue.append([child, ans[child]])
    
    print(' '.join(map(str, ans)))

n,q = map(int, input().split())
tree = {}
start = 0
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

query = {}
for _ in range(q):
    p, x = map(int,input().split())
    p -= 1
    if p not in query:
        query[p] = x
    else:
        query[p] += x
bfs(tree, start, query, n)
### BUGGY CODE ###

import itertools

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

total = 0
mod = 10 ** 9 + 7
ls = []
max_length = len(bin(max(A))) - 2
for i in range(max_length+1):
    d = {0: 0, 1: 0}
    ls.append(d)
for i in range(N):
    idx = 0
    for j in range(max_length + 1):
        try:
            b = int(bin(A[i])[-j - 1])
        except Exception:
            b = 0
        ls[j][b] += 1
        idx += 1

ans = 0
for i in range(len(ls)):
    zero = ls[i][0]
    one = ls[i][1]
    ans += zero*one * 2**i
    ans %= mod
print(ans)


### FIXED CODE ###

import numpy as np

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

A = np.array(A)
mod = 10 ** 9 + 7
ans = 0
for i in range(60):
    b = np.count_nonzero(A >> i & 1)
    ans += 2 ** i * b * (N - b)
    ans %= mod
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split(" "))
a = [-1] + list(map(int, input().split(" ")))

i = 1
head = []
used = []
roop = []

inte=False
for _ in range(k):
    i = a[i]
    if i in used:
        used.append(i)
        head = used[0: used.index(i)]
        roop = used[used.index(i): -1]
        inte =True
        break
    else:
        used.append(i)

if inte:
    if len(head) >= k:
        print(head[k-1])
    else:
        x = (k - 1 - len(head)) % len(roop)
        print(roop[x])
else:
    print(used[k-1])

### FIXED CODE ###

import sys

n, k = map(int, input().split(" "))
a = [-1] + list(map(int, input().split(" ")))

i = 1
head = []
used = {}
roop = []

index = 0
for _ in range(k):
    index += 1
    i = a[i]
    if i in used:
        head = [ k for k, v in sorted(used.items(), key=lambda x:x[1]) if v < used[i]]
        roop = [ k for k, v in sorted(used.items(), key=lambda x:x[1]) if v >= used[i]]
        if len(head) >= k:
            print(head[k-1])
        else:
            x = (k - 1 - len(head)) % len(roop)
            print(roop[x])
            sys.exit()
    else:
        used[i] = index

print([ k for k, v in sorted(used.items(), key=lambda x:x[1])][k-1])
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
ans=1
for i in range(n):
    ans=ans*L[i]
if ans > 1e18:
    print(-1)
else:
    print(ans)



### FIXED CODE ###

n=int(input())
L=list(map(int,input().split()))
L.sort()
if L[0]==0:
    print(0)
else:
    ans=1
    for i in range(n-1,-1,-1):
        ans=ans*L[i]
        if ans >1e18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

from math import floor
a,b,n = map(int, input().split())
x = n
com = 0
while x >= 0:
    val = floor((a*x)/b)-a*floor(x/b)
    if val < com:
        pass
    else:
        com = val
    x-=1
print(com)

### FIXED CODE ###

a,b,n = map(int, input().split())
com = 0
if n < b:
    x = n
else:
    x = b-1
val = (a*x)//b
print(val)
### BUGGY CODE ###

N,M =map(int,input().split())
A = [0] + list(map(int,input().split()))
for i in range(N):
  A[i+1] = (A[i]+A[i+1])%M
ans = 0
for l in range(N):
  ans += A[l+1:].count(A[l])
print(ans)

### FIXED CODE ###

import collections
N,M =map(int,input().split())
A = [0] + list(map(int,input().split()))
for i in range(N):
  A[i+1] = (A[i]+A[i+1])%M
ans = 0
c = collections.Counter(A)
for a in set(A):
  n = c[a]
  ans += int(n*(n-1)/2)
print(ans)
### BUGGY CODE ###

fact_list=[None]*300001
fact_list[0]=1
def inv(n):
    if n==1:
        return 1
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*n)%998244353
        n=(n**2)%998244353
    return s

def comb(n,r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    return (((fact_list[n]*inv(fact_list[n-r]))%998244353)*inv(fact_list[r]))%998244353

for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353

s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n+1):
    if k-a*i<0:
        break
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res=(res+comb(n,i)*comb(n,(k-a*i)//b))%998244353
print(res)

"""
def enc(n):
    if n==0:
        return "("
    s=""
    while n>0:
        s+=chr(n%86+40)
        n//=86
    return s

def dec(s):
    n=0
    for i in range(len(s)):
        n+=(86**i)*(ord(s[i])-40)
    return n
"""

### FIXED CODE ###

fact_list=[None]*300001
inv_fact_list=[None]*300001
fact_list[0]=1
inv_fact_list[0]=1
"""
def inv(n):
    if inv_fact_list[n]!=None:
        return inv_fact_list[n]
    m=fact_list[n]
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*m)%998244353
        m=(m**2)%998244353
    inv_fact_list[n]=s
    return s
def enc(n):
    if n==0:
        return "("
    s=""
    while n>0:
        s+=chr(n%86+40)
        n//=86
    return s
 
def dec(s):
    n=0
    for i in range(len(s)):
        n+=(86**i)*(ord(s[i])-40)
    return n
"""
def comb(n,r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    if inv_fact_list[n-r]!=None:
        invnr=inv_fact_list[n-r]
    else:
        m=fact_list[n-r]
        invnr=1
        for i in range(30):
            if i!=23 and i!=26:
                invnr=(invnr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[n-r]=invnr
    if inv_fact_list[r]!=None:
        invr=inv_fact_list[r]
    else:
        m=fact_list[r]
        invr=1
        for i in range(30):
            if i!=23 and i!=26:
                invr=(invr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[r]=invr
    return (((fact_list[n]*invnr)%998244353)*invr)%998244353
 
for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353
 
s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n+1):
    if k-a*i<0:
        break
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res=(res+comb(n,i)*comb(n,(k-a*i)//b))%998244353
print(res)
### BUGGY CODE ###

import sys,math
N = int(input())
s = []
ans = 0
for i in range(N):
    tmp = input()
    li_tmp = list(tmp)
    s_tmp = sorted(li_tmp)
    st = "".join(s_tmp)
    s.append(st)

a = []
a.append(s[N-1])
for i in range(N-2,-1,-1):
    ans += a.count(s[i])
    a.append(s[i])
print(ans)

### FIXED CODE ###

import sys,math,itertools
def r(x):
    sum = 0
    for i in range(1,x+1):
        sum += i
    return sum

N = int(input())
s = []
ans = [0] * N
for i in range(N):
    tmp = input()
    li_tmp = list(tmp)
    s_tmp = sorted(li_tmp)
    st = "".join(s_tmp)
    s.append(st)

data = {}
a = set()
a.add(s[N-1])
for i in range(N-2,-1,-1):
    if s[i] in a:
        if s[i] in data:
            data[s[i]] += 1
        else:
            data[s[i]] = 1 
    else:
        a.add(s[i])
for i in data:
    data[i] = r(data[i])
print(sum(data.values()))
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(b-a +1):
  if(a+i>=b-(k-1)):
    print(a+i)
  elif(a+i<=a+(k-1)):
    print(a+i)
  

### FIXED CODE ###

a,b,k=map(int,input().split())
if(b-a<300):
  for i in range(b-a+1):
    if(a+i<=a+(k-1)):
      print(a+i)
    elif(a+i>=b-(k-1)):
      print(a+i)
else:
  for i in range(k):
    print(a+i)
  for i in range(k):
    print(b-(k-1)+i)
### BUGGY CODE ###

from collections import deque

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

c = [i-1 for i in c]
d = [i-1 for i in d]

t0 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t1 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        t1.append((i, j))
for i in t0:
    t1.remove(i)
t1.remove((0, 0))

check = [[-1]*w for _ in range(h)]
q = deque()
q.appendleft((c[0], c[1], 0))

while q:
    y, x, b = q.pop()
    if x == d[1] and y == d[0]:
        print(b)
        exit()
    if check[y][x] == -1:
        check[y][x] = b
        for dy, dx in t0:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.append((ydy, xdx, b))
        for dy, dx in t1:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.appendleft((ydy, xdx, b+1))
print(-1)


### FIXED CODE ###

from collections import deque

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

c = [i-1 for i in c]
d = [i-1 for i in d]

t0 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t1 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        t1.append((i, j))
for i in t0:
    t1.remove(i)
t1.remove((0, 0))

check = [[-1]*w for _ in range(h)]
q = deque()
q.appendleft((c[0], c[1], 0))

while q:
    y, x, b = q.pop()
    if x == d[1] and y == d[0]:
        print(b)
        exit()
    if check[y][x] == -1:
        check[y][x] = b
        for dy, dx in t0:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.append((ydy, xdx, b))
        for dy, dx in t1:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.appendleft((ydy, xdx, b+1))
print(-1)
### BUGGY CODE ###

X = list(input())

i = 0
check = 0

while check == 0 :
    if i == len(X) - 1 or i == len(X):
        check = 1
    else:
        #print(i, X)
        if X[i] == 'S' and X[i+1] == 'T':
            X.pop(i)
            X.pop(i)
            i = max(0, i-1)
        else:
            i += 1
        
    
print(len(X))


### FIXED CODE ###

X = list(input())

count_S = 0
count_T = 0
TS_max = 0

for i in range(len(X)):
    if X[i] == 'S':
        count_S += 1
    elif X[i] == 'T':
        count_T += 1
    tmp = count_T - count_S
    TS_max = max(TS_max, tmp)

ans = TS_max * 2
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from bisect import bisect_left
n = int(input())
s = input()
c = 0
f = defaultdict(list)
for i in range(n):
	f[s[i]].append(i)
for i in f:
	f[i].sort()
for i in range(n):
	for j in range(i+1, n):
		if  s[i] != s[j]:
			for k in f:
				if k != s[i] and k != s[j]:
					t = bisect_left(f[k], j+1)
					if(2*j - i) in f[k][t:]:
						c += len(f[k][t:]) - 1
					else:
						c += len(f[k][t:])
print(c)

### FIXED CODE ###

n = int(input())
s = input()
# B_map = set()
R, G, B = 0, 0, 0
for i in range(n):
	if s[i] == 'R':
		R += 1
	elif s[i] == 'G':
		G += 1
	else:
		B += 1

res = R * G * B

for i in range(n):
	for j in range(i+1, n):
		temp = 2*j - i
		if temp < n and s[i] != s[j] and s[j] != s[temp] and s[temp] != s[i]:
			res -= 1
print(res)
### BUGGY CODE ###

x, y = map(int, input().split())

s = min(x,y)
l = max(x,y)
for i in reversed(range(s+1)):
    if s % i == 0:
        if l % i == 0:
            print(i)
            break


### FIXED CODE ###

x, y = map(int, input().split())
l = max(x, y)
s = min(x, y)

for i in range(x):
    olds = s
    oldl = l
    s = oldl % olds
    l = olds

    if s == 0:
        print(l)
        break
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    
    out = 1
    for n in A:
        out = n * out
    
    if out > 1000000000000000000:
        print(-1)
    else:
        print(out)



main()

### FIXED CODE ###

#!/usr/bin/env python3

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

    if 0 in A:
        print(0)
    else:
        out = 1
        for n in A:
            out = n * out
            if out > 1000000000000000000:
                break
            else:
                continue
    
        if out > 1000000000000000000:
            print(-1)
        else:
            print(out)


main()
### BUGGY CODE ###

n, m = map(int, input().split())
cities = []
for _ in range(m):
  cities.append(list(map(int, input().split())))
  sort_cities = sorted(cities, key=lambda x:x[1])
pre = [0 for _ in range(n)]
ans = {}
for city in sort_cities:
  pre[city[0]-1]+=1
  ans[(6-len(str(city[0])))*'0'+str(city[0])+str(city[1])] = (6-len(str(city[0])))*'0'+str(city[0])+(6-len(str(pre[city[0]-1])))*'0'+str(pre[city[0]-1])
for a in cities:
  print(ans[(6-len(str(a[0])))*'0'+str(a[0])+str(a[1])])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
cities = []
for _ in range(m):
  cities.append(list(map(int, input().split())))
sort_cities = sorted(cities, key=lambda x:x[1])
pre = [0 for _ in range(n)]
ans = {}
for city in sort_cities:
  pre[city[0]-1]+=1
  st_city = str(city[0])
  st_pre = str(pre[city[0]-1])
  len_0 = (6-len(st_city))*'0'
  ans[len_0+st_city+str(city[1])] = len_0+st_city+(6-len(st_pre))*'0'+st_pre
for a in cities:
  print(ans[(6-len(str(a[0])))*'0'+str(a[0])+str(a[1])])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
t = A[0]
i = 1
while i < N:
    t *= A[i]
    i += 1
if t <= 1e18:
    print(t)
else:
    print(-1)


### FIXED CODE ###

#import numpy as np
N = int(input())
A = list(map(int, input().split()))
#A = np.array(A)
t = A[0]
for i in range(1,N):
    t *= A[i]
    if int(t) > 1e18:
        for j in range(i,N):
            if A[j] == 0:
                t = 0
        break
if int(t) <= 1e18:
    print(int(t))
else:
    print(-1)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
n = int(input())

p = 1
for i in range(n):
    p *= (i+1)
o = p%(10**9+7)
print(o)


### FIXED CODE ###

# -*- coding:utf-8 -*-
n = int(input())

p = 1
for i in range(n):
    p = (p * (i+1))%1000000007
print(p)
### BUGGY CODE ###

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

ans = 0
given_water = False
while True:
  is_continuous = False
  for i in range(N):
    if h[i] > 0:
      if is_continuous is False:
        ans += 1
        is_continuous = True
      h[i] -= 1
      given_water = True
    else: # h[i] == 0
      is_continuous = False
  if given_water is False:
    break
      
print(ans)

### FIXED CODE ###

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

ans = 0

while True:
  given_water = False
  is_continuous = False
  for i in range(N):
    if h[i] > 0:
      if is_continuous is False:
        ans += 1
        is_continuous = True
      h[i] -= 1
      given_water = True
    else: # h[i] == 0
      is_continuous = False
  if given_water is False:
    break
      
print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
a_list = [None for _ in range(n)]
num = 0
day = 0
for i in range(n):
    a_list[i] = deque([int(i) - 1 for i in input().split()])

for kkk in range(n * (n - 1) // 2):
    visit = set([])
    day += 1
    for j in range(n):
        if j not in visit:
            if len(a_list[j]) > 0:
                k = a_list[j][0]
                if k not in visit:
                    if a_list[k][0] == j:
                        num += 1
                        visit.add(a_list[j].popleft())
                        visit.add(a_list[k].popleft())
    if (len(visit) == 0):
        day = -1
        break
    if num >= n * (n - 1) // 2:
        break
print(day)

### FIXED CODE ###

from collections import deque
n = int(input())
a_list = []
for i in range(n):
    a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
    if battle == n * (n - 1) // 2:
        break
    day += 1
    battle_today = 0
    tomorrow = set([])
    if (day == 1):
        player = set([i for i in range(n)])
    for i in player:
        if len(a_list[i]) == 0:
            continue
        j = a_list[i][0]
        if (i == a_list[j][0]) & (j not in tomorrow) & (len(a_list[j]) > 0) & (i not in tomorrow):
            tomorrow.add(i)
            tomorrow.add(a_list[i][0])
            battle += 1
            battle_today += 1
            a_list[i].popleft()
            a_list[j].popleft()
    player = tomorrow
    if battle_today == 0:
        day = -1
        break
print(day)
### BUGGY CODE ###

# [時間、変数、処理の種類]をイベントに追加。処理の種類は1：工事開始、2：工事終了、3：判定
from heapq import *

n, q = map(int, input().split())
events = []
ans = [-1] * q
koji = set()
for _ in range(n):
    s, t, x = map(int, input().split())
    events += [[s - x - 0.3, x, 1]]
    events += [[t - x - 0.7, x, 2]]
for i in range(q):
    d = int(input())
    events += [[d, i, 3]]
heapify(events)
cnt=0
for _ in range(n * 2 + q):
    j, h, s = heappop(events)
    if s == 1:
        koji.add(h)
    elif s == 2:
        koji.remove(h)
    else:
        if koji:
            ans[h] = min(koji)
        cnt+=1
    if cnt==q:
        break
print(*ans, sep="\n")


### FIXED CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

    print(*ans, sep="\n")

n, q = map(int, input().split())
f(n, q)
### BUGGY CODE ###

#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)

S_ = np.array(S)

def count_answer(x,y,num_b,num_w):
    # print(used)
    # global num_b,num_w
    count = 0
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)

        if next_x == -1 or next_y == -1:
            pass
        elif next_x >= H or next_y >= W:
            pass
        elif used[next_x][next_y] == 1:
            pass
        elif S_[next_x][next_y] != S_[x][y]:
            used[next_x][next_y] = 1
            if S_[next_x][next_y] == "#":
                num_b += 1
            else:
                num_w += 1
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            pass
        elif S_[i,j] == "#":
            num_b = 0
            num_w = 0
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)


### FIXED CODE ###

#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)


def count_answer(x,y,num_b,num_w):
    # print(used)

    if S[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S[next_x][next_y] != S[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S[i][j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)
### BUGGY CODE ###

N,P=map(int,input().split())
for x in range(max(int(P**(1/N))+1,1),0,-1):
  if P%(x**N)==0:
    print(x)
    exit()


### FIXED CODE ###

def primes(n):
  ps = {}
  while n%2==0:
    n//=2
    if 2 not in ps:
      ps[2] = 1
    else:
      ps[2] += 1
  
  for i in range(3,int(n**.5)+1,2):
    while n%i==0:
      n//=i
      if i not in ps:
        ps[i] = 1
      else:
        ps[i] += 1
  
  if n!=1:
    ps[n] = 1
  
  return ps
  
N,P = map(int,input().split())
if N==1:
  print(P)
  exit()
ps = primes(P)
ans = 1
for p, num in ps.items():
  if num>=N:
    ans *= p**(num//N)
print(ans)
### BUGGY CODE ###

import sys
s = input()
n = len(s)

if n < 4:
    print(0)
    sys.exit()

ans = 0
for i in range(n-3):
    for j in range(i+3, n):
        a = int(s[i:j+1])
        # print(i, j, a, a%2019)
        if a % 2019 == 0:
            ans += 1
            # print(i+1, j)
print(ans)



### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

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

a, b = map(int, input().split())

ans = [1]

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf
 
cflist = cf(a,b)
 
import fractions
import itertools
 
for i in cflist:
        ans.append(i)
        for j in itertools.combinations(ans, 2):
                if 1 == fractions.gcd(j[0],j[1]):
            		    pass
                else:
                        ans.pop()
                        break
 
print(len(ans))

### FIXED CODE ###

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

a, b = map(int, input().split())
import fractions
print(len(set(prime_decomposition(fractions.gcd(a,b))))+1)