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

# -*- coding: utf-8 -*-
import re
# input
n, q = map(int, input().split())
s = input()
startPosition = [m.start() for m in re.finditer('AC', s)]
for i in range(q):
    l, r = map(int, input().split())
    print(len([j for j in startPosition if (j >= l-1 and j <= r-2)]))

### FIXED CODE ###

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

import heapq

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

for i in range(n-1):
    a,b=list(map(int,input().split()))

    g[a].append([b,i])
    g[b].append([a,i])


q=[(1,0)]
k=0

while len(q)>0:
    u,c=heapq.heappop(q)

    clrs=list(range(1,c))+list(range(c+1,len(g[u])+1))
    cnt=0

    for v,i in g[u]:
        if clst[i]==c:
            continue
        clst[i]=clrs[cnt]
        heapq.heappush(q,(v,clst[i]))
        cnt+=1


    if len(clrs)>0:
        k=max(k,clrs[-1])

print(k)

for i in range(n-1):
    print(clst[i])


### FIXED CODE ###

from collections import deque

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

for i in range(n-1):
    a,b=list(map(int,input().split()))

    g[a].append([b,i])
    g[b].append([a,i])


q=deque([[1,0]])
k=0

while len(q)>0:
    u,c=deque.popleft(q)

    clr=1

    for v,i in g[u]:
        if clst[i]==c:
            continue
        if clr==c:
            clr+=1
        
        clst[i]=clr
        deque.append(q,[v,clr])

        clr+=1


    k=max(k,clr-1)

print(k)

for i in range(n-1):
    print(clst[i])
### BUGGY CODE ###

n=int(input())
s=list(input() for i in range(n))
t=[]

for i in range(n):
    if s[i] not in t:
        t.append(s[i])
print(len(t))

### FIXED CODE ###

n=int(input())
s=list(input() for i in range(n))
t=set(s)

print(len(t))
### BUGGY CODE ###

x = int(input())
rep = 10**4
for i in range(rep):
    for j in range(rep):
        if (i-(rep//2))**5-(j-(rep//2))**5 == x:
            print(i-(rep//2),j-(rep//2))
            exit()

### FIXED CODE ###

x = int(input())
rep = 10**3
for i in range(rep):
    for j in range(rep):
        if (i-(rep//2))**5-(j-(rep//2))**5 == x:
            print(i-(rep//2),j-(rep//2))
            exit()
### BUGGY CODE ###

#解説解答
n,a = map(int,input().split())
x = list(map(int,input().split()))
dp0 = [[0 for s in range(n*a+1)] for k in range(n+1)]
dp0[0][0] = 1
dp = dp0
for j in range(n):
  now = []
  for k in range(n+1):
    add = []
    for s in range(n*a+1):
      t = s-x[j]
      if t >= 0 and k >= 1:
        add.append( dp[k][s] + dp[k-1][t] )
      else:
        add.append( dp[k][s] )
    now.append(add)
  dp = now
ans = 0
for k in range(1,n+1):
  ans += dp[k][k*a]
print(ans)

### FIXED CODE ###

#解説解答
n,a = map(int,input().split())
x = list(map(int,input().split()))
dp0 = [[0 for s in range(n*a+1)] for k in range(n+1)]
dp0[0][0] = 1
dp = dp0
for j in range(n):
  now = []
  for k in range(n+1):
    add = []
    for s in range(n*a+1):
      t = s-x[j]
      if t >= 0 and k >= 1:
        add.append( dp[k][s] + dp[k-1][t] )
      else:
        add.append( dp[k][s] )
    now.append(add)
  dp = now
ans = 0
for k in range(1,n+1):
  ans += dp[k][k*a]
print(ans)
### BUGGY CODE ###

import sys
#大きすぎるとダメ
sys.setrecursionlimit(2503)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)




### FIXED CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])
### BUGGY CODE ###

import sys


def bit_add(arr, n, i, x):
    while i <= n:
        arr[i] += x
        i += i & -i


def bit_sum(arr, i):
    result = 0
    while i > 0:
        result += arr[i]
        i ^= i & -i
    return result


n, q = map(int, sys.stdin.buffer.readline().split())
ccc = list(map(int, sys.stdin.buffer.readline().split()))
mp = map(int, sys.stdin.buffer.read().split())
queries = sorted((r, l, i) for i, (l, r) in enumerate(zip(mp, mp)))

bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0

for r, l, i in queries:
    while p < r:
        c = ccc[p]
        before_appeared = appeared[c]
        if before_appeared != -1:
            bit_add(bit, bn, before_appeared + 2, -1)
        bit_add(bit, bn, p + 2, 1)
        appeared[c] = p
        p += 1

    ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)

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


### FIXED CODE ###

import os
import sys

import numpy as np


def solve(inp):
    def bit_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def bit_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    n = inp[0]
    q = inp[1]
    ccc = inp[2:2 + n]
    lll = inp[2 + n::2] - 1
    rrr = inp[3 + n::2] - 1

    just_left = {}
    segments = []
    for i in range(n):
        c = ccc[i]
        if c in just_left:
            segments.append((i, 0, just_left[c], 0))
        just_left[c] = i

    for i in range(q):
        segments.append((rrr[i], 1, lll[i], i))

    segments.sort()
    bit = np.zeros(n + 2, dtype=np.int64)
    ans = np.zeros(q, dtype=np.int64)

    for r, tp, l, i in segments:
        if tp == 0:
            bit_add(bit, n + 2, l + 2, 1)
        else:
            base = r - l + 1
            ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
N, K = [int(x) for x in input().split()]
h = []
for _ in range(N):
    h.append(int(input()))
h.sort()
i = 0
ans = 10 ** 9
while N - i >= K:
    temp = h[i:i+K]
    ans = min(ans,temp[-1] - temp[0])
    i += 1
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))
### BUGGY CODE ###

N,M=map(int,input().split())
ans=0
A=[]
for i in range(N):
  a,b=map(int,input().split())
  if a<=M:
    d=[a,b]
    A.append(d)
ans=0
now=0
sortedA=sorted(A, key=lambda x: x[0])
#print("sortedA",sortedA)
after=[]
i=0
stop=0
while sortedA or i<M:
  i+=1
  #print("i",i)
  if len(sortedA)==0 and len(after)!=0:
    ans+=after[-1][1]
    after.pop(-1)
    #print("ans",ans,"after",after,"sortedA" ,sortedA)
  elif sortedA:
    while sortedA[0][0]==i:
      a=sortedA.pop(0)
      after.append(a)
      if len(sortedA)==0: break
    after.sort(key=lambda x:x[1])
    if after:
      ans+=after[-1][1]
      after.pop(-1)
    #print("ans",ans,"after",after,"sortedA" ,sortedA)
print(ans)




### FIXED CODE ###

import heapq
N,M=map(int,input().split())
l=[[] for i in range(M+1)]
#print(l)
for i in range(N):
  a,b=map(int,input().split())
  if a<=M:
  #print(a,b)
  #print(l[a])
    l[a].append(b)
#print(l)
ans=0
que=[]
for i in range(1,M+1):
  for j in l[i]:
    heapq.heappush(que,-j)
  if len(que)>0:
    #print(i,que)
    ans-=heapq.heappop(que)
    
    
print(ans)
### BUGGY CODE ###

cnt = 0

def merge(A, l, m, r):
    n1, n2 = m - l, r - m
    L = [A[l + i] for i in range(n1)]
    R = [A[m + i] for i in range(n2)]
    L.append(10 ** 10)
    R.append(10 ** 10)
    i, j = 0, 0
    global cnt
    for k in range(l, r):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, l, r):
    if r - l > 1:
        m = (l + r) // 2
        mergeSort(A, l, m)
        mergeSort(A, m, r)
        merge(A, l, m, r)

n = int(input())
A = list(map(int, input().split()))
mergeSort(A, 0, n)
print(" ".join(list(map(str, A))))
print(cnt)

### FIXED CODE ###

def merge(A, l, m, r):
    L = A[l:m] + [10 ** 9 + 1]
    R = A[m:r] + [10 ** 9 + 1]
    i, j = 0, 0
    for k in range(l, r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    global cnt
    cnt += r - l

def mergeSort(A, l, r):
    if r - l > 1:
        m = (l + r) // 2
        mergeSort(A, l, m)
        mergeSort(A, m, r)
        merge(A, l, m, r)

n = int(input())
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, n)
print(" ".join(list(map(str, A))))
print(cnt)
### BUGGY CODE ###

H,W = map(int,input().split())
height, width_max, ans = [0] * (W+1), [0] * (W+1), 0
for i in range(H):
    s = list(input()) + ['#']
    length = 0
    for j in range(W+1):
        if s[j] == '.':
            length += 1
            height[j] += 1
        else:
            if length > 0:
                for k in range(j-length, j):
                    if width_max[k] < length:
                        width_max[k] = length
                length = 0
            if height[j] > 0:
                temp = width_max[j] + height[j] - 1
                if ans < temp:
                    ans = temp
                width_max[j], height[j] = 0, 0
                

for j in range(W):
    if height[j] > 0:
        temp = width_max[j] + height[j] - 1
        if ans < temp:
            ans = temp
        height[j] = 0 

print(ans)


### FIXED CODE ###

H,W = map(int,input().split())
height, width_max, ans = [0] * (W+1), [0] * (W+1), 0
for i in range(H):
    s = input() + '#'
    length = 0
    for j in range(W+1):
        if s[j] == '.':
            length += 1
            height[j] += 1
        else:
            if length > 0:
                for k in range(j-length, j):
                    if width_max[k] < length:
                        width_max[k] = length
                length = 0
            if height[j] > 0:
                temp = width_max[j] + height[j] - 1
                if ans < temp:
                    ans = temp
                width_max[j], height[j] = 0, 0
for j in range(W):
    if height[j] > 0:
        temp = width_max[j] + height[j] - 1
        if ans < temp:
            ans = temp
print(ans)
### BUGGY CODE ###

from collections import defaultdict as dd
import queue
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(str(b))
    dic[str(b)].append(str(a))
seen = set()
def BFS(dic,node):
    cc = set()
    q = queue.Queue()
    q.put(node)
    cc.add(node)
    while not q.empty():
        now_node = q.get()
        cc.add(now_node)
        target = set(dic[now_node]) - cc
        for tgt in target:
            #if tgt not in cc:
            q.put(tgt)
            #seen.add(tgt)
    return cc
c_comp=[]
for i in range(1,N+1):
    if str(i) not in seen:
        # 連結判定
        tmp = BFS(dic,str(i))
        seen = seen & set(tmp)
        c_comp.append(list(tmp))
uf = [0]*N
for i,ls in enumerate(c_comp):
    for val in ls:
        uf[int(val)-1] = i
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(str(b))
        dic[str(b)].append(str(a))
res = [0]*N
for ls in c_comp:
    leng = len(ls)-1
    for idx in ls:
        res[int(idx)-1] = leng - len(dic[idx])
print(*res)


### FIXED CODE ###

from collections import defaultdict as dd
import queue
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
uf = [-1]*N
def BFS(ufid, dic, node):
    leng = -1
    q = queue.Queue()
    q.put(node)
    while not q.empty():
        now_node = q.get()
        if uf[now_node-1] > 0:
            continue
        leng += 1
        uf[now_node-1] = ufid
        target = [val for val in dic[str(now_node)] if uf[val-1]==-1]
        for tgt in target:
            q.put(tgt)
            uf[tgt-1] = 0
    return leng

len_ls = []
var = 1
for i in range(N):
    if uf[i] == -1:
        # 連結判定
        leng = BFS(var, dic, i+1)
        len_ls.append(leng)
        var += 1
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[uf[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)
### BUGGY CODE ###

N,W = input().split()
aArr = list()
ans = 0
tmp = int(N)
for i in range(int(W)):
    inputInt = int(input())
    aArr.append(inputInt)
    if inputInt - tmp == 1:
        print(ans)
        exit()
    tmp = inputInt

tmp = 0
tmpB = 0
ans = 1
for i in range(int(N)):
    if(i in aArr):
        tmp = 0
    elif i < 2:
        tmp = 1
    else:
        tmp = ans
    ans = tmp + tmpB
    tmpB = tmp
print(ans % 1000000007)

### FIXED CODE ###

import sys
N, W = input().split()
aArr = list()
ans = 0
tmp = int(N)
MOD = 10 ** 9 + 7
aArr = set(map(int, sys.stdin))

tmp = 0
tmpB = 0
ans = 1
for i in range(int(N)):
    if (i in aArr):
        tmp = 0
    elif i < 2:
        tmp = 1
    else:
        tmp = ans
    ans = (tmp + tmpB) % MOD
    tmpB = tmp
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    sum = A.count(i+1)
    print(sum)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
ans = np.zeros(N)
for i in A:
    ans[i-1] +=1
for i in ans:
    print(int(i))
### BUGGY CODE ###

n = int(input())
alist = list(map(int,input().split()))
b = []
c = []
for i in range(n):
    b.append(alist[i])
    blen = len(b)
    c = b[::-1]
    b = [c[j] for j in range(blen)]
    c = []        
blen = len(b)
for k in range(blen):
    print(b[k],end=" ")

### FIXED CODE ###

#C問題
N = int(input())
A = list(map(int,input().split()))
if N%2 == 0:
    front = []
    back = []
    for i in range(N):
        if i%2 == 1:
            front.append(A[i])
        else:
            back.append(A[i])
    front = front[::-1]
    for i in range(N//2):
        print(front[i],end=" ")
    for i in range(N//2):
        print(back[i],end=" ")
        
else:
    front = []
    back = []
    for i in range(N):
        if i%2 == 0:
            front.append(A[i])
        else:
            back.append(A[i])
    front = front[::-1]
    for i in range(N//2 + 1):
        print(front[i],end=" ")
    for i in range(N//2):
        print(back[i],end=" ")
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,p]=i2()
s=input()

  
if p==2 or p==5:
   x1=0
   for i in range(n):
     if int(s[i])%p==0:
        x1+=i+1  
   print(x1)
else:
  t=0
  x2=0
  d={0:1}
  a=1
  for i in range(n)[::-1]:
     t+=int(s[i])*a
     t%=p
     a*=10
     if t in d:
        x2+=d[t]
        d[t]+=1
     else:
        d[t]=1
  print(x2)

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,p]=i2()
s=input()

  
if p==2 or p==5:
   x1=0
   for i in range(n):
     if int(s[i])%p==0:
        x1+=i+1  
   print(x1)
else:
  t=0
  x2=0
  d={0:1}
  a=1
  for i in range(n)[::-1]:
     t+=int(s[i])*a
     t%=p
     a*=10
     a%=p
     if t in d:
        x2+=d[t]
        d[t]+=1
     else:
        d[t]=1
  print(x2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
max_count = 0
for i in range(max(a) + 1):
    count = 0
    for j in range(n):
        if a[j] - 1 <= i <= a[j] + 1:
            count += 1
    max_count = max(max_count, count)
print(max_count)

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
counter = collections.Counter(a)
max_count = 0
for i in range(0, max(a) + 1):
    max_count = max(max_count, counter[i - 1] + counter[i] + counter[i + 1])
print(max_count)
### BUGGY CODE ###

from collections import deque


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

tree = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)

set_ = set([])
for i in range(n):
    for j in tree[i]:
        set_.add(j)

start = set([])
for i in range(n):
    if i not in set_:
        start.add(i)

q = deque([])
for i in start:
    q.append(i)
dp = [0]*n
while q:
    pos = q.popleft()
    for next_pos in tree[pos]:
        if dp[pos] + 1 > dp[next_pos]:
            dp[next_pos] = dp[pos] + 1
            q.append(next_pos)
print(max(dp))

### FIXED CODE ###

import sys


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

n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
tree = [[] for i in range(n)]
start_point = [True] * n
for i in range(m):
    tree[info[i][0] - 1].append(info[i][1] - 1)
    start_point[info[i][1] - 1] = False
     
dp = [-1]*n

def dfs(pos):
    if dp[pos] !=-1:
        return dp[pos]
    if not tree[pos]:
        dp[pos] = 0
        return 0
    ans = 0
    for i in tree[pos]:
        ans = max(ans, dfs(i) + 1)
    dp[pos] = ans
    return ans

for i in range(n):
    dfs(i)
print(max(dp))
### BUGGY CODE ###

n = int(input())
s = list(input())
b = 27
mod = pow(2, 61) - 1
m = n // 2
x = [1] * (m + 1)
for i in range(1, m + 1):
    x[i] = (x[i - 1] * b) % mod
for i in range(m, 0, -1):
    h = 0
    d = {}
    for j in range(i):
        h += (x[i - j - 1] * (ord(s[j]) - 96) % mod)
        h %= mod
    d[h] = 0
    for j in range(i, n):
        h *= b
        h %= mod
        h -= (x[i] * (ord(s[j - i]) - 96) % mod)
        h += (ord(s[j]) - 96)
        h %= mod
        if h in d:
            if (j - m + 1 - d[h]) >= i:
                print(i)
                exit()
        else:
            d[h] = j - m + 1
print(0)

### FIXED CODE ###

n = int(input())
s = list(input())
b = 27
mod = 67280421310721
m = n // 2
x = [1] * (m + 1)
for i in range(1, m + 1):
    x[i] = (x[i - 1] * b) % mod
h0 = [0] * m
h0[0] = ord(s[0]) - 96
d = [{} for _ in range(m + 1)]
for i in range(1, m):
    h0[i] = (h0[i - 1] * b + (ord(s[i]) - 96)) % mod
for i in range(m, 0, -1):
    h = h0[i - 1]
    d[i][h] = 0
    for j in range(i, n):
        h *= b
        h %= mod
        h -= (x[i] * (ord(s[j - i]) - 96) % mod)
        h += (ord(s[j]) - 96)
        h %= mod
        if h in d[i]:
            if (j - i + 1 - d[i][h]) >= i:
                print(i)
                exit()
        else:
            d[i][h] = j - i + 1
print(0)
### BUGGY CODE ###

def divs(p):
  divs = []
  for i in range(1,int(p**.5)+1):
    if p%i==0:
      divs.append(i)
      if i != p//i:
        divs.append(p//i)
  return divs  

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

divs = sorted(divs(P),reverse=True)
for div in divs:
  if P%div**N==0:
    print(div)
    exit()
print(1)

### 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 ###

N,W = map(int,input().split())
WV = [[0,0]] + [list(map(int,input().split())) for _ in range(N)]
vrng = (10**3)*N+1
dp = [[float('inf') for _ in range(vrng)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
  tmpw, tmpv = WV[i]
  for j in range(vrng):
    if j-tmpv>=0:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-tmpv]+tmpw)
    else:
      dp[i][j] = dp[i-1][j]

ans = -float('inf')
for row in dp:
  for j,w in enumerate(row):
    if w<=W and ans<j:
      ans = j
print(ans)

### FIXED CODE ###

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

sumV = sum([v for _,v in WV])
dp = [[float('inf') for _ in range(sumV+1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
  tmpw, tmpv = WV[i]
  for j in range(sumV+1):
    if j-tmpv>=0:
      dp[i][j] = min(dp[i-1][j],dp[i-1][j-tmpv]+tmpw)
    else:
      dp[i][j] = dp[i-1][j]

ans = -float('inf')
for row in dp:
  for j,w in enumerate(row):
    if w<=W and ans<j:
      ans = j
print(ans)
### BUGGY CODE ###

# coding: utf-8
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

H,W=map(int, input().split())
M = list( list(input()) for _ in range(H) )

#p(H,W)
#p(M)

for h in range(H):
	for w in range(W):
		c=M[h][w]
		if c==".": M[h][w]=0
		if c=="#": M[h][w]=1

#p(M)


for h in range(H):
	for w in range(W-1):
		i=M[h][0+w]
		if i>0:
			j=M[h][1+w]
			if (j==0)or(j>i+1): M[h][1+w]=i+1

		i=M[h][-1-w]
		if i>0:
			j=M[h][-2-w]
			if (j==0)or(j>i+1): M[h][-2-w]=i+1

#p(M)

for w in range(W):
	for h in range(H-1):
		i=M[0+h][w]
		if i>0:
			j=M[1+h][w]
			if (j==0)or(j>i+1): M[1+h][w]=i+1
	
		i=M[-1-h][w]
		if i>0:
			j=M[-2-h][w]
			if (j==0)or(j>i+1): M[-2-h][w]=i+1

#p(M)

ans=0
for h in range(H):
	ans=max(ans, max(M[h]))

print( max(0,ans-1) )



### FIXED CODE ###

H, W = map(int, input().split())


HW=[ [-1 for w in range(W)] for h in range(H) ]

#print(HW)
from collections import deque
Q = deque()

for h in range(H):
  S = input()
  for w in range(W):
    if S[w]=="#":
      Q.append([h,w])
      HW[h][w]=0

X = [0,0,-1,1]
Y = [-1,1,0,0]
ans=0

while Q:
  h,w = Q.popleft()

  for i in range(len(X)):
    ih,iw = h + Y[i], w + X[i]

    if not ((0 <= ih < H) and (0 <= iw < W)): continue
    if HW[ih][iw] >= 0: continue

    HW[ih][iw] = HW[h][w]+1
    ans = max(ans, HW[ih][iw])
    Q.append([ih,iw])

print(ans)