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

from collections import Counter

n = int(input())
box = list(map(int, input().split()))

for i in range(len(box)):
    tmp = box.copy()
    tmp.pop(i)
    c = Counter(tmp)
    keys = c.keys()
    cnt = 0
    for k in keys:
        #print('k, c[k]: ',k ,c[k])
        if c[k] != 1:
            cnt += int(1/2 * c[k] * (c[k] - 1))
    print(cnt)
    
    


### FIXED CODE ###

from collections import defaultdict

n = int(input())
box = list(map(int, input().split()))
c = defaultdict(int)
for b in box:
    c[b] += 1
    
anss = sum([int(1/2 * c[k] * (c[k] - 1)) for k in c.keys()])
for b in box:
    fi = anss - int(1/2 * c[b] * (c[b] - 1)) + int(1/2 * (c[b]-1) * (c[b] - 2)) 
    print(fi)
### BUGGY CODE ###

#!/usr/bin/python3

import sys
from bisect import bisect_left

sys.setrecursionlimit(1000000)

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

nbs = [ [] for _ in range(n) ]

for _ in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    for ch in nbs[cur]:
        if ch == p:
            continue

        idx = bisect_left(dp, a[ch])
        ov = dp[idx]

        ntail = max(ctail, idx)
        dp[idx] = a[ch]
        mlen[ch] = ntail + 1
        getmlen(ch, cur, ntail)
        dp[idx] = ov

        

dp[0] = a[0]
mlen[0] = 1
getmlen(0, -1, 0)

for i in range(n):
    print(mlen[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print(ret[i])
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
c = []
for i in A:
    if i in c:
        c.remove(i)
    else:
        c.append(i)
print(len(c))

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
count = 1
ans = 0
for i in range(1,N):
    if A[i - 1] == A[i]:
        count += 1
    else:
        if count % 2 == 1:
            ans += 1
        count = 1
if count % 2 == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

# @profile
def calc_lcs(s, t):
  dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  # dp = numpy.zeros((len(s)+1, len(t)+1))
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max((dp[i-1][j-1] + 1) if si==tj else 0, dp[i-1][j], dp[i][j-1])

  lcs = ''
  i, j = len(s), len(t)
  while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
      i -= 1
    elif dp[i][j] == dp[i][j-1]:
      j -= 1
    elif dp[i][j] == dp[i-1][j-1]+1:
      lcs = s[i-1] + lcs
      i -= 1
      j -= 1
  return lcs

def main():
  s = input().strip()
  t = input().strip()
  print(calc_lcs(s, t))


if __name__=='__main__':
  main()

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

# @profile
def calc_lcs(s, t):
  dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]
  # dp = numpy.zeros((len(s)+1, len(t)+1))
  for i, si in enumerate(s, 1):
    for j, tj in enumerate(t, 1):
      dp[i][j] = max((dp[i-1][j-1] + 1) if si==tj else 0, dp[i-1][j], dp[i][j-1])

  lcs = ''
  i, j = len(s), len(t)
  while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
      i -= 1
    elif dp[i][j] == dp[i][j-1]:
      j -= 1
    else:
      lcs = s[i-1] + lcs
      i -= 1
      j -= 1
  return lcs

def main():
  s = input().strip()
  t = input().strip()
  print(calc_lcs(s, t))


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

n = int(raw_input())
a = []
for i in range(n):
    a.append(int(raw_input()))

max = a[1] - a[0]
for i in range(n - 1):
    for j in range(i+1, n):
        if a[j] - a[i] > max:
            max = a[j] - a[i]

print max

### FIXED CODE ###

n = int(raw_input())
a = []
for i in range(n):
    a.append(int(raw_input()))

max = a[1] - a[0]
min_num = a[0]
for i in a[1:]:
    if i - min_num > max:
        max = i - min_num
    if min_num > i:
        min_num = i
print max
### BUGGY CODE ###

X,Y,A,B,C=map(int,input().split())
P=sorted(list(map(int,input().split())))
Q=sorted(list(map(int,input().split())))
R=sorted(list(map(int,input().split())))
S=sorted(P[A-X:]+Q[B-Y:])
ans=sum(S)
for i in range(X+Y):
    if len(R)==0 or len(S)==0 or S[0]>R[-1]:
        break
    ans-=S.pop(0)
    ans+=R.pop(-1)
print(ans)

### FIXED CODE ###

X,Y,A,B,C=map(int,input().split())
P=sorted(list(map(int,input().split())))
Q=sorted(list(map(int,input().split())))
R=sorted(list(map(int,input().split())))
S=sorted(P[A-X:]+Q[B-Y:])
ans=sum(S)
for i in range(min(len(R),len(S))):
    if S[i]<R[-1-i]:
        S[i]=R[-1-i]
    else:
        break
print(sum(S))
### BUGGY CODE ###

n = int(input())
cs = [[0] * (n + 1) for _ in range(n + 1)]
es = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    cs[a][b] = cs[b][a] = c
    es[a].append(b)
    es[b].append(a)
ds = [0] * (n + 1)
qs = []


def bfs():
    cur, prev = qs.pop()
    ds[cur] = ds[prev] + cs[prev][cur]
    for e in es[cur]:
        if e != prev:
            qs.append((e, cur))


q, k = map(int, input().split())
qs.append((k, k))
while qs:
    bfs()

for _ in range(q):
    x, y = map(int, input().split())
    print(ds[x] + ds[y])

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

n = int(input())
ls = [list(map(int, input().split())) for _ in range(n - 1)]

es = [[] for _ in range(n + 1)]
for a, b, c in ls:
    es[a].append((b, c))
    es[b].append((a, c))
ds = [0] * (n + 1)


def dfs(cur, prev, c):
    ds[cur] = ds[prev] + c
    for e, c in es[cur]:
        if e != prev:
            dfs(e, cur, c)


q, k = map(int, input().split())
qs = [list(map(int, input().split())) for _ in range(q)]

dfs(k, k, 0)
for x, y in qs:
    print(ds[x] + ds[y])
### BUGGY CODE ###

import math
n,m = map(int,input().split())
price = list(map(int,input().split()))
price.sort(reverse=True)
real_price = 0
while m != 0:
    price[0] = price[0]/2
    price.sort(reverse=True)
    m -= 1

for i in range(n):
    real_price += math.floor(price[i])
print(real_price)

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
p = list(map(int,input().split()))
price = [x*(-1) for x in p]
heapq.heapify(price)
while m != 0:
    max_price = heapq.heappop(price)*(-1)
    heapq.heappush(price,(max_price//2)*(-1))
    m -= 1
print(sum(price)*(-1))
### BUGGY CODE ###

from bisect import bisect_left
def main():
    n = int(input())
    s = input().rstrip()
    q = int(input())
    ans = []
    al = [[] for _ in range(26)]
    for i in range(n):
        al[ord(s[i]) - ord("a")].append(i)
    for _ in range(q):
        x, y, z = map(str, input().rstrip().split())
        if x == "1":
            y = int(y) - 1
            if s[y] == z:
                continue
            p = ord(z) - ord("a")
            al[p].insert(bisect_left(al[p], y), y)
            al[ord(s[y]) - ord("a")].remove(y)
            s = s[:y] + z + s[y+1:]
        else:
            y = int(y)
            y -= 1
            z = int(z)
            cnt = 0
            for i in range(26):
                index = bisect_left(al[i], y)
                if index < len(al[i]) and al[i][index] < z:
                    cnt += 1
            ans.append(cnt)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from bisect import bisect_left, insort
def main():
    n = int(input())
    s = list(input().rstrip())
    q = int(input())
    ans = []
    al = [[] for _ in range(26)]
    for i, c in enumerate(s):
        al[ord(c) - ord("a")].append(i)
    for _ in range(q):
        x, y, z = map(str, input().rstrip().split())
        if x == "1":
            y = int(y) - 1
            if s[y] == z:
                continue
            p = bisect_left(al[ord(s[y])-ord("a")],y)
            al[ord(s[y])-ord("a")].pop(p)
            insort(al[ord(z)-ord("a")],y)
            s[y] = z
        else:
            y = int(y) - 1
            z = int(z)
            cnt = 0
            for i in range(26):
                index = bisect_left(al[i], y)
                if index < len(al[i]) and al[i][index] < z:
                    cnt += 1
            ans.append(cnt)
    for v in ans:
        print(v)

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

import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()
        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:  # 枠外
                    break
                if y2 < 0 or y2 >= W:  # 枠外
                    break
                if m[x2][y2] == '@':  # 蓮の葉
                    break
                if M[x2][y2] < d + 1:  # より良い経路を探索済み。
                    break
                if M[x2][y2] == d + 1:  # 同等の良さの経路を探索済み。　飛び越えて次のマスを探索する。
                    continue

                q.append((d + 1, x2, y2))
                # M[x2][y2] = d + 1

    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)


### FIXED CODE ###

from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])
### BUGGY CODE ###

n,k = map(int,input().split())
h = []
ans = 10**10

for i in range(n):
    h.append(int(input()))
h.sort()

for i in range(n-k+1):
    tmp = h[i:i+k]
    buf = tmp[-1] - tmp[0]
    if buf < ans:
        ans = buf
print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
h = []
ans = 10**10

for i in range(n):
    h.append(int(input()))
h.sort()

for i in range(n-k+1):
    buf = h[i+k-1] - h[i]
    if buf < ans:
        ans = buf
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(an) for an in input().split()]
    divider = 10 ** 9 + 7
    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            ans = (ans + a[i] * a[j]) % divider
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = [int(an) for an in input().split()]
    divider = 10 ** 9 + 7
    ans = 0
    total = sum(a)
    tmp = 0
    for i in range(n - 1):
        ai = a[i]
        tmp += ai
        ans = (ans + a[i] * (total - tmp)) % divider
    print(ans)


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

MAX = 5 * (10**5)
MOD = 10**9 + 7
def inv(p):
    q = MOD - 2
    res = 1
    while q:
        if q % 2 == 1:
            res = (res*p) % MOD
        p = (p*p) % MOD
        q //= 2
    return res

_fact = [0] * (MAX + 1)
_inv = [0] * (MAX + 1)
_fact[0] = 1
_inv[0] = 1
for k in range(1, MAX + 1):
    _fact[k] = _fact[k-1] * k % MOD
    _inv[k] = inv(_fact[k])

def P(m, n):
    return _fact[m] * _inv[m-n] % MOD

def C(m, n):
    return _fact[m] * _inv[m-n] * _inv[n] % MOD

def solve(n, m):
    res = 0
    for k in range(n+1):
        sign = 1 - 2 * (k%2)
        cur = sign * C(n, k) * P(m, k) * (P(m-k, n-k) ** 2)
        res = (res + cur) % MOD
    return res

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

### FIXED CODE ###

MAX = 5 * (10**5)
MOD = 10**9 + 7

_fact = [1,1] + [0] * MAX
_inv = [0,1] + [0] * MAX
_fact_inv = [1,1] + [0] * MAX
for k in range(2, MAX + 1):
    _fact[k] = _fact[k-1] * k % MOD
    _inv[k] = (-_inv[MOD % k] * (MOD // k)) % MOD
    _fact_inv[k] = _fact_inv[k-1] * _inv[k] % MOD

def P(m, n):
    return _fact[m] * _fact_inv[m-n] % MOD

def C(m, n):
    return _fact[m] * _fact_inv[m-n] * _fact_inv[n] % MOD

def solve(n, m):
    res = 0
    for k in range(n+1):
        sign = 1 - 2 * (k%2)
        cur = sign * C(n, k) * P(m, k) * (P(m-k, n-k) ** 2)
        res = (res + cur) % MOD
    return res

n, m = map(int, input().split())
print(solve(n, m))
### BUGGY CODE ###

s = input()
q = int(input())
l = []
r = []
flg = False
for i in range(q):
    try:
        t,f,c = input().split()
        if flg:
            if f == '1':
                r.append(c)
            else:
                l.insert(0,c)
        else:
            if f == '1':
                l.insert(0,c)
            else:
                r.append(c)
    except ValueError:
        if flg:
            flg = False
        else:
            flg = True
if flg:
    print((''.join(r[::-1]))+(s[::-1])+(''.join(l[::-1])))
else:
    print((''.join(l))+(s)+(''.join(r)))

### FIXED CODE ###

from collections import deque
s = deque(list(input()))
q = int(input())
flg = True
for _ in range(q):
    try:
        t,f,c = input().split()
        if flg:
            if f == "1":
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if f == "1":
                s.append(c)
            else:
                s.appendleft(c)
    except ValueError:
        if flg:
            flg = False
        else:
            flg = True
if flg:
    print(''.join(s))
else:
    s = list(reversed(s))
    print(''.join(s))
### BUGGY CODE ###

import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = 61

    ans = 0
    one_cnt = [0] * B
    for b in range(B):
        for i in range(N):
            one_cnt[b] += (A[i] >> b) & 1
        ans += 2 ** b * one_cnt[b] * (N - one_cnt[b])
        ans %= P
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

import numpy as np

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = np.array(A)

    ans = 0
    for b in range(60 + 1):
        cnt_1 = int(np.sum((A >> b) & 1))
        ans += 2 ** b * cnt_1 * (N - cnt_1)
        ans %= P
    print(ans)


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

s=input()
t=input()

dp=[["" for i in range(len(s)+1)] for j in range(len(t)+1)]
for i in range(len(t)):
  for j in range(len(s)):
    if t[i]==s[j]:
      dp[i+1][j+1]=dp[i][j]+t[i]
    else:
      if len(dp[i+1][j])>len(dp[i][j+1]):
        dp[i+1][j+1]=dp[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]

print(dp[len(t)][len(s)])


### FIXED CODE ###

import sys
readline = sys.stdin.readline

S = readline().rstrip()
T = readline().rstrip()

# dp[i][j] = Sをi文字目、Tをj文字目まで進めたときの最長
# S[i] == S[j]のとき
# dp[i][j] = dp[i - 1][j - 1] + 1
# S[i] != S[j]のとき
# dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])

# その際、自分がどこから来たか？を記録する
# dp[i - 1][j] > dp[i][j - 1]であれば
# route[i][j] = (i,j)を記録

dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
route = [[(0,0)] * (len(T) + 1) for i in range(len(S) + 1)]

for i in range(len(S)):
  for j in range(len(T)):
    if S[i] == T[j]:
      dp[i + 1][j + 1] = dp[i][j] + 1
      route[i + 1][j + 1] = (i,j)
    else:
      if dp[i][j + 1] > dp[i + 1][j]:
        dp[i + 1][j + 1] = dp[i][j + 1]
        route[i + 1][j + 1] = (i,j + 1)
      else:
        dp[i + 1][j + 1] = dp[i + 1][j]
        route[i + 1][j + 1] = (i + 1,j)

# routeのとびさきの文字を追加していく
x,y = len(S),len(T)
ans = ""
while x != 0 and y != 0:
  if S[x - 1] == T[y - 1]:
    ans += S[x - 1]
  x,y = route[x][y]

print(ans[::-1])
### BUGGY CODE ###

from  heapq import heappush, heappop, heapify

n,m,s,t=map(int,raw_input().split())

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while Q:
		u=heappop(Q)
	#	print u, nl[u]
		for i in nl[u]:
			#print "i::",i
			v=i[0]
			yen=i[1]
			sunuku=i[2]
		#	print v,yen,sunuku,d
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+sunuku

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

### FIXED CODE ###

import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)
### BUGGY CODE ###

k = int(input())

def gcd(x,y):
    while y:
        x ,y = y ,x%y
    return x



total = 0

for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            total += gcd(a , gcd(b,c))

print(total)

### FIXED CODE ###

k = int(input())

def gcd(x,y):
    while y:
        x ,y = y ,x%y
    return x

total = 0

for a in range(1,k+1):
    for b in range(1,k+1):
        subg = gcd(a,b)
        subtotal = 0
        for c in range(1,k+1):
            subtotal += gcd(subg, c)
        total += subtotal

print(total)
### BUGGY CODE ###

n=int(input())
s=input()
r=[[0]*(n+1) for _ in range(n+1)]

#print(r)

maxV=0
for i in range(n):
  for j in  range(n):
    ii=n-1-i
    jj=n-1-j
    if s[ii]==s[jj]:
      r[ii][jj]=min(r[ii+1][jj+1]+1,abs(ii-jj))
      maxV=max(maxV,r[ii][jj])

print(maxV)

### FIXED CODE ###

n=int(input())
s=input()
r=[[0]*(n+1) for _ in range(n+1)]

#print(r)

maxV=0
for i in range(n):
  for j in  range(n):
    ii=n-1-i
    jj=n-1-j
    if s[ii]==s[jj]:
      r[ii][jj]=min(r[ii+1][jj+1]+1,abs(ii-jj))
      maxV=max(maxV,r[ii][jj])

print(maxV)
### BUGGY CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np    # numpy.lcm()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk
# import networkx as nx
# G = Graph()

# slist = "abcdefghijklmnopqrstuvwxyz"
N,P = map(int,input().split())

if N == 1:
    print(P)
    exit()

ans = 1
i = 1
while i**N <= P:
    if P % (i**N)==0:
        ans = i
    i += 1
 
print(ans)
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
from collections import deque,Counter
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np    # numpy.lcm()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk
# import networkx as nx
# G = Graph()

# slist = "abcdefghijklmnopqrstuvwxyz"
N,P = map(int,input().split())

def prime_factorize(n):  #nの素因数分解結果をリストで返す。Counterで素数ごとの指数確認可能 
    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)
    return a

cnt =Counter(prime_factorize(P))

ans = 1
for k,v in cnt.items():
    if v >= N:
        ans *= k**(v//N)

print(ans)
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))
### BUGGY CODE ###

import sys


def resolve():
    H, N = map(int, sys.stdin.readline().split())
    m = map(int, sys.stdin.read().split())
    AB = zip(m, m)
    INF = 10**20
    dp = [INF]*(H+10**4)
    dp[0] = 0
    for a, b in AB:
        for j in range(H+10**4):
            dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
    return min(dp[H:])


if __name__ == '__main__':
    print(resolve())


### FIXED CODE ###

import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))
### BUGGY CODE ###

N = int(input())

A = set([i for i in range(1, 10**5)])
s = [[] for _ in range(N)]
r = []
for _ in range(N-1):
  a, b = map(int, input().split())
  n = min(A - set(s[a-1] + s[b-1]))
  s[a-1] += [n]
  s[b-1] += [n]
  r.append(n)

print(max(r))
print(*r, sep='\n')

### FIXED CODE ###

from collections import deque

N = int(input())

G = [[] for _ in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  G[a-1].append([b-1, i])
  G[b-1].append([a-1, i])


q = deque()
q.append([0, 0, 0])

colors = [0] * (N-1)
while q:
  node, parent, edge_color = q.popleft()
  c = 1
  for child, index in G[node]:
    if child == parent:
      continue
    
    if c == edge_color:
      c += 1
    
    q.append([child, node, c])
    colors[index] = c
    c += 1

print(max(colors))
print(*colors, sep='\n')