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

import collections, itertools

h, w = map(int, input().split())
ch, cw = tuple(int(s) - 1 for s in input().split())
dh, dw = tuple(int(s) - 1 for s in input().split())
s = [input() for _ in range(h)]

q = collections.deque()
q.append((ch, cw))
score = [[float('inf')] * w for _ in range(h)]
score[ch][cw] = 0
while q:
    x, y = q.popleft()

    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == '.' and score[x][y] < score[nx][ny]:
            score[nx][ny] = score[x][y]
            q.append((nx, ny))
    
    for dx, dy in itertools.product(range(-2, 3), repeat=2):
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == '.' and score[x][y] + 1 < score[nx][ny]:
            score[nx][ny] = score[x][y] + 1
            q.append((nx, ny))

if score[dh][dw] == float('inf'):
    print(-1)
else:
    print(score[dh][dw])

### FIXED CODE ###

import collections, itertools

h, w = map(int, input().split())
ch, cw = tuple(int(s) - 1 for s in input().split())
dh, dw = tuple(int(s) - 1 for s in input().split())
s = [input() for _ in range(h)]

q = collections.deque()
q.append((ch, cw, 0))
score = [[float('inf')] * w for _ in range(h)]
score[ch][cw] = 0
while q:
    x, y, p = q.popleft()

    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == '.' and p < score[nx][ny]:
            score[nx][ny] = p
            q.appendleft((nx, ny, p))
    
    for dx, dy in itertools.product(range(-2, 3), repeat=2):
        nx, ny = x + dx, y + dy
        if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == '.' and p + 1 < score[nx][ny]:
            score[nx][ny] = p + 1
            q.append((nx, ny, p + 1))

if score[dh][dw] == float('inf'):
    print(-1)
else:
    print(score[dh][dw])
### BUGGY CODE ###

import sys
 
def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split(" ")))
 
    mod = 10**9+7
    res = 0

    for i in range(N-1):
        for j in range(i, N):
            if i >= j: continue
            res += A[i] * A[j]
    print(res % mod)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
 
def main():
    def input():return sys.stdin.readline()[:-1]
    N = int(input())
    A = list(map(int, input().split(" ")))
 
    mod = 10**9+7
    res = 0

    S = sum(A)
    S2 = sum(map(lambda x: x**2, A))
    print((S**2-S2) // 2 % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
def main():

    N = int(input())

    d = [2 for _ in range(N+1)]
    d[1] = 1

    v = int(math.sqrt(N))

    for i in range(2, v+1):
        for j in range(i+i, N+1, i):
            if j//i > v: d[j] += 2
            else: d[j] += 1

    ans = 0
    for i in range(1, N+1):
        ans += i * d[i]
    return ans

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

### FIXED CODE ###

import math
import collections
def main():

    N = int(input())
    d = dict()
    for i in range(1, N+1):
        d[i] = 0

    ans = 0
    for i in range(1, N+1):
        p = N//i
        ans += p * (p+1)//2 * i
    return ans

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

n = int(input())
b = [''.join(sorted(input())) for i in range(n)]
c = list(set(b))
d = len(c)
cnt = [b.count(c[i]) for i in range(d) if b.count(c[i]) >1]
ans = 0
for i in cnt:
  ans += int(i*(i-1)/2)
print(ans)

### FIXED CODE ###

N = int(input())
s_sort = [''.join(sorted(input())) for _ in range(N)]
dic = {}
ans = 0
for i in s_sort:
  if i not in dic:
    dic[i] = 0
  else:
    dic[i] += 1
    ans += dic[i]
print(ans)
### BUGGY CODE ###

import numpy as np
N, K=map(int, input().split())
P=np.array(list(map(int, input().split())))

best=0

for i in range(N-K+1):
  point=P[i:i+K].sum()
  
  if point>best:
    best=point
    
    


print(best/2+K/2)

### FIXED CODE ###

N, K=map(int, input().split())
P=list(map(int, input().split()))

#n面サイコロの出る目の期待値
def n_mean(n):
  return 0.5*(n+1)

Pmean=list(map(lambda x: n_mean(x), P))
Psum=[0]*N
Psum[0]=Pmean[0]
for i in range(1,N):
  Psum[i]=Psum[i-1]+Pmean[i]
#print(Psum)
ans=0
for i in range(N-K+1):
  if i==0:
    ans=Psum[K-1]
  else:
    #1~6 
    ans=max(ans, (Psum[i+K-1]-Psum[i-1]))
  
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
# n1 = int((N/K + 0.5)//1)
# n2 = int((N/K - 0.5)//1)
# if (N/K - 0.5)%1 != 0: n2 += 1

# print(min(abs(n1*K-N),abs(n2*K-N)))
i = N
while i >= K//2:
    i = abs(i-K)
print(i)

### FIXED CODE ###

N,K = map(int,input().split())
n = int((N/K + 0.5)//1)
i = abs(n*K-N)
while i >= K/2:
    i = abs(K-i)

print(i)
### BUGGY CODE ###

s = input()
q = int(input())
for _ in range(q):
    query = input()
    if query == '1':
        s = s[::-1]
    else:
        _, f, c = query.split()
        if f == '1':
            s = c + s
        else:
            s = s + c
print(s)

### FIXED CODE ###

from collections import deque
s = input()
queue = deque(list(s))
q = int(input())
pre = 0
reverse = 0
for _ in range(q):
    query = input()
    if query == '1':
        if pre:
            pre = 0
        else:
            pre = 1
        reverse += 1
    else:
        _, f, c = query.split()
        if f == '1':
            if pre == 0:
                # s = c + s
                queue.appendleft(c)
            else:
                # s = s + c
                queue.append(c)
        else:
            if pre == 1:
                # s = c + s
                queue.appendleft(c)
            else:
                # s = s + c
                queue.append(c)
if reverse % 2 == 1:
    queue = reversed(queue)
print(''.join(queue))
### BUGGY CODE ###

from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i in range(h) for j in range(w) if S[i][j]=='#']
    q = deque(q)
    ans = 0
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < h*w:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

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

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

l = []
for i in range(N):
    l.append(((1/2)*p[i]*(p[i]+1))/p[i])

k = []
for i in range(len(l)):
    k.append(sum(l[i:i+K]))

print(max(k))

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
p = list(map(int,input().split()))

l = []
for i in range(N):
    l.append((1+p[i])/2)

a = [0] * N
a[0] = l[0]
for i in range(1,len(l)):
    a[i] = a[i-1] + l[i]

ans = 0
for i in range(K,len(l)):
    ans = max(ans,a[i]-a[i-K])

if N == 1 or N - K == 0:
    print(max(a))
else:
    print(ans)
### BUGGY CODE ###

import sys
f = sys.stdin

def create_prime(n):
    prime = [1] * (n + 1)
    prime[:2] = [0, 0]
    for i in range(len(prime)):
        if prime[i]:
            for j in range(2 * i, len(prime), i):
                prime[j] = 0
    return prime

sieve = create_prime(50000)

prime = []
for i in range(25001):
    if sieve[i]:
        prime.append(i)

while True:
    n = int(f.readline())
    if n == 0:
        break
    cnt = 0
    for i in prime:
        if i > n // 2 + 1:
            break
        if sieve[n - i]:
            cnt += 1
    print(cnt)

### FIXED CODE ###

import sys
f = sys.stdin

def create_prime(n):
    prime = [1] * (n + 1)
    prime[:2] = [0, 0]
    for i in range(len(prime)):
        if prime[i]:
            for j in range(2 * i, len(prime), i):
                prime[j] = 0
    return prime

sieve = create_prime(50000)

prime = []
for i in range(25001):
    if sieve[i]:
        prime.append(i)

while True:
    n = int(f.readline())
    if n == 0:
        break
    cnt = 0
    temp = n // 2
    for i in prime:
        if i > temp:
            break
        if sieve[n - i]:
            cnt += 1
    print(cnt)
### BUGGY CODE ###

import sys

input=sys.stdin.readline

N=int(input())
p=[]
for i in range(N):
    x,y=map(int,input().split())
    p.append([x,y])

p.sort()
for i in range(N):
    p[i][0]=i+1

p.sort(key=lambda x:x[1])
for i in range(N):
    p[i][1]=i+1


data=[[0 for i in range(4)] for i in range(N)]
#A1 ... AnのBIT(1-indexed)
n=N
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

p.sort()
for i in range(N):
    x,y=p[i]
    data[i][0]=BIT_query(N)-BIT_query(y)
    if y==1:
        data[i][1]=0
    else:
        data[i][1]=BIT_query(y-1)
    BIT_update(y,1)

BIT=[0]*(n+1)
for i in range(N-1,-1,-1):
    x,y=p[i]
    data[i][2]=BIT_query(N)-BIT_query(y)
    if y==1:
        data[i][3]=0
    else:
        data[i][3]=BIT_query(y-1)
    BIT_update(y,1)

ans=0
mod=998244353
for i in range(N):
    ban=0
    for j in range(4):
        ban+=pow(2,data[i][j],mod)-1
        ban%=mod
    ban+=(pow(2,data[i][0],mod)-1)*(pow(2,data[i][2],mod)-1)
    ban+=(pow(2,data[i][2],mod)-1)*(pow(2,data[i][3],mod)-1)
    ban+=(pow(2,data[i][3],mod)-1)*(pow(2,data[i][1],mod)-1)
    ban+=(pow(2,data[i][1],mod)-1)*(pow(2,data[i][0],mod)-1)
    ban%=mod
    ans+=pow(2,N,mod)-ban-1
    ans%=mod
print(ans)

### FIXED CODE ###

import sys

input=sys.stdin.readline

N=int(input())
p=[]
for i in range(N):
    x,y=map(int,input().split())
    p.append([x,y])
mod=998244353

pow=[1]
for i in range(N):
    pow.append((pow[-1]*2)%mod)

p.sort(key=lambda x:x[1])
for i in range(N):
    p[i][1]=i+1


data=[[0 for i in range(4)] for i in range(N)]
#A1 ... AnのBIT(1-indexed)
n=N
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    if idx==0:
        return 0
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

p.sort()
for i in range(N):
    x,y=p[i]
    a,b=i,BIT_query(y)
    data[i][0]=a-b
    data[i][3]=b
    BIT_update(y,1)

BIT=[0]*(n+1)
for i in range(N-1,-1,-1):
    x,y=p[i]
    a,b=N-1-i,BIT_query(y)
    data[i][1]=a-b
    data[i][2]=b
    BIT_update(y,1)

ans=0
for i in range(N):
    ban=0
    for j in range(4):
        ban+=(pow[data[i][j]]-1)*pow[data[i][j-1]]
        ban%=mod
    ans+=pow[N]-ban-1
    ans%=mod
print(ans)
### BUGGY CODE ###

import sys
import numpy as np

sys.setrecursionlimit(5000)
input=sys.stdin.readline

N, T = [int(a) for a in input().split()]
time = np.full(N + 1, -1, dtype = np.int32)
value = np.full(N + 1, -1, dtype = np.int32)
for i in range(1, N + 1):
    time[i], value[i] = [int(a) for a in input().split()]

# Sort the array in the increasing order of value
time = time[np.argsort(value)]
value.sort()

# table for knapsack problem
# maximum possible time is T-1
dp_table = np.full((N + 1, T + 1), -1, dtype = np.int32)

# Fill in dp_table
def knapsack():

    for t in range(0, T):
        dp_table[0, t] = 0

    for n in range(1, N + 1):
        dp_table[n, 0] = 0
        for t in range(1, T):
            if time[n] > t:
                dp_table[n, t] = dp_table[n - 1, t]
            else:
                dp_table[n, t] = max(dp_table[n - 1, t], value[n] + dp_table[n - 1, t - time[n]])

    return None


def all_you_can_eat(n, t):
    if n <= 0 or t <= 0:
        return 0
    else:
        # Eat the most delicious food at the beginning
        tmp1 = value[n] + all_you_can_eat(n - 1, t - time[n])
        # Eat the most delicious food at the end
        tmp2 = value[n] + dp_table[n - 1, t - 1]
        return max(tmp1, tmp2)

knapsack()
print(all_you_can_eat(N, T))


### FIXED CODE ###

import sys
from operator import itemgetter

sys.setrecursionlimit(5000)
input = sys.stdin.readline


TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [None] * (N + 1)
time_value[0] = (-1, -1)
for i in range(1, N + 1):
    time_value[i] = tuple(int(a) for a in input().split())

# Sort the array in the increasing order of value
time_value.sort(key = itemgetter(VAL))


# T by (N + 1) table for knapsack problem
# maximum possible time is T-1
dp_table = [[-1] * T for _ in range(N + 1)]

# Fill in dp_table i.e. solve knapsack problem
for t in range(0, T):
    dp_table[0][t] = 0

for n in range(1, N + 1):
    dp_table[n][0] = 0
    for t in range(1, T):
        if time_value[n][TIME] > t:
            dp_table[n][t] = dp_table[n - 1][t]
        else:
            dp_table[n][t] = max(dp_table[n - 1][t],
                             time_value[n][VAL] + dp_table[n - 1][t - time_value[n][TIME]])


val_acum = time_value[N][VAL]
t = T - 1
max_val = val_acum + dp_table[N - 1][t]

for n in range(N - 1, 0, -1):  # food to eat at the end
    val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
    t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
    if t < 0: break
    tmp = val_acum + dp_table[n - 1][t]
    max_val = max(max_val, tmp)

print(max_val)
### BUGGY CODE ###

n, x, y = map(int, input().split())
ans = [0 for i in range(n-1)]
for i in range(n-1):
  for j in range(i+1, n):
    k = i + 1
    l = j + 1
    a = l - k
    b_1 = k - x
    b_2 = l - y
    c_1 = k - y
    c_2 = l - x
    if b_1 < 0:
      b_1 = - b_1
    if b_2 < 0:
      b_2 = - b_2
    if c_1 < 0:
      c_1 = - c_1
    if c_2 < 0:
      c_2 = - c_2
    b = b_1 + b_2 + 1
    c = c_1 + c_2 + 1
    if b < a:
      a = b
    if c < a:
      a = c
    ans[a-1] += 1
for i in ans:
  print(i)

### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0 for i in range(n-1)]
for i in range(n-1):
  k = i + 1
  b_1 = k - x
  c_1 = k - y
  if b_1 < 0:
      b_1 = - b_1
  if c_1 < 0:
      c_1 = - c_1
  for j in range(i+1, n):
    l = j + 1
    a = l - k
    b_2 = l - y
    c_2 = l - x
    if b_2 < 0:
      b_2 = - b_2
    if c_2 < 0:
      c_2 = - c_2
    b = b_1 + b_2 + 1
    c = c_1 + c_2 + 1
    if b < a:
      a = b
    if c < a:
      a = c
    ans[a-1] += 1
for i in range(n-1):
  print(ans[i])
### BUGGY CODE ###

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

A.sort(reverse=True)
#print(A)

for i in range(M):
    A[0] = int(A[0] / 2.0)
    A.sort(reverse=True)

ans = 0
for i in range(N):
    ans += A[i]

print(ans)

### FIXED CODE ###

import heapq

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

for i in range(N):
    A[i] = -A[i]

heapq.heapify(A)

for j in range(M):
    a = heapq.heappop(A)
    b = -1*((-a) // 2)
    heapq.heappush(A,b)

print(-sum(A))
### BUGGY CODE ###

N, K = map(int, input().split())
hs = sorted([int(input()) for _ in range(N)])[::-1]
 
min_diff = 10 ** 10
for i in range(0, N-K+1):
    tmp = hs[i:i+K]
    min_diff = min(min_diff, tmp[0] - tmp[-1])
 
print(min_diff)

### FIXED CODE ###

N, K = map(int, input().split())
hs = sorted([int(input()) for _ in range(N)])

min_diff = 10 ** 10
for i in range(N-K+1):
    min_diff = min(min_diff, hs[i+K-1] - hs[i])

print(min_diff)
### BUGGY CODE ###

N,M = map(int,input().split())
H = list(map(int,input().split()))
AB = [list(map(int,input().split())) for i in range(M)]

graph={}
for i in range(1,N+1):
    graph[i]=[]
    for j in range(M):
        if AB[j][0]==i:
            graph[i].append(H[AB[j][1]-1])
        if AB[j][1]==i:
            graph[i].append(H[AB[j][0]-1])

ans = 0
for i in range(1,N+1):
    tmp = graph[i]
    if len(graph[i]) == 0:
        ans+=1
    else:
        mh = max(graph[i])
        if H[i-1] > mh:
            ans += 1
        else:
            continue
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
H = list(map(int,input().split()))
AB = [list(map(int,input().split())) for i in range(M)]

ans = [0] * N
for i in range(M):
    if H[AB[i][0]-1] > H[AB[i][1]-1]:
        ans[AB[i][1]-1] += 1
    if H[AB[i][0]-1] < H[AB[i][1]-1]:
        ans[AB[i][0]-1] += 1
    if H[AB[i][0]-1] == H[AB[i][1]-1]:
        ans[AB[i][0]-1] += 1
        ans[AB[i][1]-1] += 1
print(ans.count(0))
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

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

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


list.sort(key = lambda x: x[0])

ans = 0
heap = []
for day in range(1,M+1):
	for i in list:		
		if i[0] == day:
			heappush(heap, -i[1])
		elif i[0] > day:
			break
    
	if len(heap) != 0:
		ans += -heappop(heap)

print(ans)

### FIXED CODE ###

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):  # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す

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

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)


N = inp()
S = input()

cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[j] == S[i]: continue
        for k in range(j + 1, N):
            if j - i == k - j: continue
            if (S[i] == S[k]) or (S[j] == S[k]): continue
            cnt += 1
print(cnt)


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inp_list(): return list(map(int, sys.stdin.readline().split()))


def lcm(x, y): return (x * y) // gcd(x, y)


N = inp()
S = input()

"""
    Conditions:
        1. S[i] \ne S[j] and S[j] \ne S[k] and S[k] \ne S[i]
        2. j - i \ne k - j
"""

r = S.count('R')
g = S.count('G')
b = S.count('B')
# 条件1を満たす組は rgb 個。それから「条件1を満たしてかつ条件 2 を満たさない」組を引く。条件を満たさないもののほうが多い。


cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        k = j + (j - i) # => k - j == j - i
        if k > N - 1: break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            cnt += 1

print(r * g * b - cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def chmin(min,cur):
	if min > cur:
		min = cur
	return min

n,k = map(int,input().split())
h = list(map(int,input().split()))

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

for i in range(n):
	for j in range(k):
		try:
			dp[i+j+1] = chmin(dp[i+j+1],dp[i]+abs(h[i]-h[i+j+1]))
		except:
			break

print(dp[n-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def chmin(min,cur):
	if min > cur:
		min = cur
	return min

n,k = map(int,input().split())
h = list(map(int,input().split()))

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

for i in range(n):
	for j in range(k):
		try:
			dp[i+j+1] = chmin(dp[i+j+1],dp[i]+abs(h[i]-h[i+j+1]))
		except:
			break

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

N, P = [int(a) for a in input().split()]
# N, P = 4, 972439611840
prod = P
ans = 1
for i in range(2, P):
    if prod < i ** N:
        break
    count = 0
    while prod % i == 0:
        prod /= i
        count += 1
        if count % N == 0:
            ans *= i

print(str(ans))

### FIXED CODE ###

N, P = [int(a) for a in input().split()]
# N, P = [10, 2972439611840]
prod = P
ans = 1
if N == 1:
    ans = P
elif N > 40:
    ans = 1
else:
    for i in range(2, P):
        if i > 2 and i % 2 == 0:
            continue
        if prod < i ** N:
            break
        count = 0
        while prod % i == 0:
            prod /= i
            count += 1
            if count % N == 0:
                ans *= i
print(str(ans))
### BUGGY CODE ###

_, _, _, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = [x+y for x in a for y in b]
ab.sort()

abc = [x+y for x in ab[:-k-1:-1] for y in c]

abc.sort()
for i in abc[:-k-1:-1]:
  print(i)

### FIXED CODE ###

x, y, z, k = list(map(int, input().split()))
a = sorted(map(int, input().split()))
b = sorted(map(int, input().split()))
c = sorted(map(int, input().split()))

ab = sorted(x+y for x in a for y in b)[:-k-1:-1]
abc = sorted(x+y for x in ab[:k] for y in c)[:-k-1:-1]
print(*abc, sep='\n')
### BUGGY CODE ###

import numpy as np

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

a_list = np.zeros(100005)
# a_list = [0 for _ in range(100005)]

for a in A_uniq:
    a_cnt = A.count(a)
    a_list[a] += a_cnt
    a_list[a+1] += a_cnt
    a_list[a+2] += a_cnt
    
print(int(a_list.max())) 

### FIXED CODE ###

import numpy as np
from collections import Counter

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

ans = 0
counter = Counter(A)
for a, cnt in counter.most_common():
    tmp = counter[a-1] + cnt + counter[a+1]
    if ans < tmp:
        ans = tmp
        

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

S = str(input())
l = len(S)
mod = [0] * 2019
dp = 0
for i in range(l):
    dp = dp + pow(10,i)*int(S[-1-i])
    mod[dp % 2019] += 1
mod[0] += 1
cnt = 0
for i in range(2019):
    if mod[i] > 1:
        cnt += (mod[i]*(mod[i]-1))//2
print(cnt)

### FIXED CODE ###

S = str(input())
l = len(S)
mod = [0] * 2019
dp = 0
pw = 1
for i in range(l):
    mod[dp % 2019] += 1
    dp = dp + pw * int(S[-1-i])
    pw = (pw * 10) % 2019
mod[dp % 2019] += 1
cnt = 0
for i in range(2019):
    cnt += (mod[i]*(mod[i]-1))//2
print(cnt)
### BUGGY CODE ###

from heapq import heappush, heappop
N, Q = map(int, input().split())
ls = []
for i in range(N):
  s, t, x = map(int, input().split())
  ls += [(s-x,1,x)]
  ls += [(t-x,0,x)]
for i in range(Q):
  d = int(input())
  ls += [(d,2,i)]
ls.sort()
se = set()
q = []
for a,b,c in ls:
  if b==1:
    se.add(c)
    heappush(q,c)
  elif b==0:
    se.remove(c)
  else:
    while q and q[0] not in se:
      heappop(q)
    ans = q[0] if q else -1
    print(ans)


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))