Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M,P = inpl()
lines = defaultdict(set)

for _ in range(M):
    a,b,c = inpl()
    a,b = a-1,b-1
    lines[a].add((b,-c+P))

#ベルマンフォード(始点と終点が決まってる時)
def BellmanFord(Start,Goal):
    Costs=[INF]*N
    Costs[Start] = 0
    upd8s = set(range(N))
    for i in range(2*N): #2N回ループ(負閉路の検出までみる)
        will_upd8s = set()
        for s in upd8s:
            for t,c in lines[s]:
                if c + Costs[s] < Costs[t]:
                    Costs[t] = Costs[s]+c
                    will_upd8s.add(t) #更新した点だけ次に見る
                    if i >= N:
                        Costs[t] = -INF

        if i == N-1: #Nループ目のGoalのCostを記録
            tmp = Costs[Goal]

        upd8s = copy.deepcopy(will_upd8s)

    if tmp != Costs[Goal]:
        return -INF
    else:
        return Costs[Goal]

ans = -BellmanFord(0,N-1)
if ans == INF:
    print(-1)
else:
    print(max(0,ans))


Fixed submission:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M,P = inpl()
lines = defaultdict(set)

for _ in range(M):
    a,b,c = inpl()
    a,b = a-1,b-1
    lines[a].add((b,-c+P))

#ベルマンフォード(始点と終点が決まってる時)
def BellmanFord(Start,Goal):
    Costs=[INF]*N
    Costs[Start] = 0
    upd8s = [True]*N
    for i in range(2*N): #2N回ループ(負閉路の検出までみる)
        will_upd8s = [False]*N
        for s in range(N):
            if not upd8s[s]: continue    #前回更新してないので見ない
            for t,c in lines[s]:
                if c + Costs[s] < Costs[t]:
                    Costs[t] = Costs[s]+c
                    will_upd8s[t] = True #更新した点だけ次に見る
                    if i >= N:
                        Costs[t] = -INF

        if i == N-1: #Nループ目のGoalのCostを記録
            tmp = Costs[Goal]

        upd8s = will_upd8s[:]

    if tmp != Costs[Goal]:
        return -INF
    else:
        return Costs[Goal]

ans = -BellmanFord(0,N-1)
if ans == INF:
    print(-1)
else:
    print(max(0,ans))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

H,W = inpl()

MAP = [list(input()) for y in range(H)]

yokoList = [[0]*W for y in range(H)]

for y in range(H):
    l = 0
    while l < W:
        if MAP[y][l] == '#':
            l += 1
            continue
        else:
            r = l
            tmp = 0
            while True:
                if r >= W or MAP[y][r] == '#':
                    break
                else:
                    r += 1
                    tmp += 1
            for x in range(l,r):
                yokoList[y][x] = tmp
            l = r

tateList = [[0]*W for y in range(H)]

for x in range(W):
    l = 0
    while l < H:
        if MAP[l][x] == '#':
            l += 1
            continue
        else:
            r = l
            tmp = 0
            while True:
                if r >= H or MAP[r][x] == '#':
                    break
                else:
                    r += 1
                    tmp += 1
            for y in range(l,r):
                tateList[y][x] = tmp
            l = r



ans = 0
for y in range(H):
    for x in range(W):
        ans = max(tateList[y][x] + yokoList[y][x]-1, ans)

print(ans)


Fixed submission:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

H,W = inpl()

MAP = [list(input()) for y in range(H)]

yokoList = [[0]*W for y in range(H)]

for y in range(H):
    l = 0
    while l < W:
        if MAP[y][l] == '#':
            l += 1
            continue
        else:
            r = l
            tmp = 0
            while True:
                if r >= W or MAP[y][r] == '#':
                    break
                else:
                    r += 1
                    tmp += 1
            for x in range(l,r):
                yokoList[y][x] = tmp
            l = r

tateList = [[0]*W for y in range(H)]

for x in range(W):
    l = 0
    while l < H:
        if MAP[l][x] == '#':
            l += 1
            continue
        else:
            r = l
            tmp = 0
            while True:
                if r >= H or MAP[r][x] == '#':
                    break
                else:
                    r += 1
                    tmp += 1
            for y in range(l,r):
                tateList[y][x] = tmp
            l = r



ans = 0
for y in range(H):
    for x in range(W):
        ans = max(tateList[y][x] + yokoList[y][x]-1, ans)

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
lines = [[] for _ in range(N)]
for _ in range(N-1):
  i,j,w = map(int,input().split())
  lines[i-1].append((j-1,w))
  lines[j-1].append((i-1,w))

ans = [-1]*N 
def dfs(s, c):
  if ans[s] != -1:
    return
  else:
    ans[s] = c
    for t,w in lines[s]:
      if w%2==0:
        dfs(t,c)
      else:
        dfs(t,c^1)
      
dfs(0, 0)

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




Fixed submission:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = int(input())

lines = defaultdict(set)
for i in range(N-1):
    u,v,w = inpl()
    u,v = u-1,v-1
    lines[u].add((v,w))
    lines[v].add((u,w))

ans = [0]*N

def dfs(s,c):
    global ans
    for t,d in list(lines[s]):
        if ans[t] == 0:
            if d%2 == 0:
                ans[t] = c
                dfs(t,c)
            else:
                ans[t] = -c
                dfs(t,-c)


dfs(0,1)
for a in ans:
    if a == -1:
        print(0)
    else:
        print(1)
Buggy python submission (verdict: Runtime Error):
import bisect

X,Y,Z,K = list(map(int,input().split()))
AA = list(map(int,input().split()))
BB = list(map(int,input().split()))
CC = list(map(int,input().split()))
MAX = max(max(AA),max(BB),max(CC))

AB = []
for a in AA:
  for b in BB:
    AB.append(a+b)
    
AB.sort()
XY = len(AB)

def check(n):
  cnt = 0
  for c in CC:
    cnt += (XY - bisect.bisect_left(AB,n-c))
  return cnt >= K

OK = 0
NG = MAX*3+100
while NG - OK >1:
  mid = (OK+NG)//2
  if check(mid):
    OK = mid
  else:
    NG = mid
    
    
ans = []
for c in CC:
    n = bisect.bisect_left(AB,OK-c)
    for i in range(n,XY):
      ans.append(c+AB[i])
      
ans.sort(reverse=True)
for YUI in ans:
  print(

Fixed submission:
import bisect

X,Y,Z,K = list(map(int,input().split()))
AA = list(map(int,input().split()))
BB = list(map(int,input().split()))
CC = list(map(int,input().split()))
MAX = max(max(AA),max(BB),max(CC))

AB = []
for a in AA:
  for b in BB:
    AB.append(a+b)
    
AB.sort()
XY = len(AB)

def check(n):
  cnt = 0
  for c in CC:
    cnt += (XY - bisect.bisect_left(AB,n-c))
  return cnt >= K

OK = 0
NG = MAX*3+100
while NG - OK >1:
  mid = (OK+NG)//2
  if check(mid):
    OK = mid
  else:
    NG = mid
    
    
ans = []
for c in CC:
    n = bisect.bisect_left(AB,OK-c)
    for i in range(n,XY):
      ans.append(c+AB[i])
      
ans.sort(reverse=True)
for YUI in range(K):
  print(ans[YUI])

Buggy python submission (verdict: Runtime Error):
import bisect

X,Y,Z,K = list(map(int,input().split()))
AA = list(map(int,input().split()))
BB = list(map(int,input().split()))
CC = list(map(int,input().split()))
MAX = max(max(AA),max(BB),max(CC))

AB = []
for a in AA:
  for b in BB:
    AB.append(a+b)
    
AB.sort()
XY = X*Y

def check(n):
  cnt = 0
  for c in CC:
    cnt += XY - bisect.bisect_left(AB,n-c)
  return cnt >= K

OK = 0
NG = MAX*3+100
while OK-NG >1:
  mid = (OK+NG)//2
  if check(mid):
    OK = mid
  else:
    NG = mid
    
ans = []
for c in CC:
    n = bisect.bisect_left(AB,n-c)
    for i in range(n,XY):
      ans.append(c+AB[i])
      
ans.sort(reverse=Ture)
for YUI in ans:
  print(YUI)
    

Fixed submission:
import bisect

X,Y,Z,K = list(map(int,input().split()))
AA = list(map(int,input().split()))
BB = list(map(int,input().split()))
CC = list(map(int,input().split()))
MAX = max(max(AA),max(BB),max(CC))

AB = []
for a in AA:
  for b in BB:
    AB.append(a+b)
    
AB.sort()
XY = len(AB)

def check(n):
  cnt = 0
  for c in CC:
    cnt += (XY - bisect.bisect_left(AB,n-c))
  return cnt >= K

OK = 0
NG = MAX*3+100
while NG - OK >1:
  mid = (OK+NG)//2
  if check(mid):
    OK = mid
  else:
    NG = mid
    
    
ans = []
for c in CC:
    n = bisect.bisect_left(AB,OK-c)
    for i in range(n,XY):
      ans.append(c+AB[i])
      
ans.sort(reverse=True)
for YUI in range(K):
  print(ans[YUI])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
ABs = []
for _ in range(N):
    A,B = inpl()
    ABs.append([A+B,A,B])

ABs.sort(reversed=True)
t = a = 0

for i,[AB,A,B] in enumerate(ABs):
    if i%2 == 0:
        t += A
    else:
        a += B

print(t-a)


Fixed submission:
N = int(input())
ABs = [list(map(int,input().split())) for i in range(N)]
li = []
for A,B in ABs:
  li.append([A+B,A,B])
  
li.sort(reverse=True)
flag = True
ans1 = ans2 = 0
for S,A,B in li:
  if flag:
    ans1 += A
  else:
    ans2 += B
  flag = not flag
  
print(ans1-ans2)

Buggy python submission (verdict: Runtime Error):
N = int(input())
ABs = [list(map(int,input.split())) for i in rane(N)]
li = []
for A,B in ABs:
  li.append([A+B,A,B])
  
li.sort(reverse=True)
flag = True
ans1 = ans2 = 0
for S,A,B in li:
  if flag:
    ans1 += A
  else:
    ans2 += B
  flag = not flag
  
print(ans1-ans2)

Fixed submission:
N = int(input())
ABs = [list(map(int,input().split())) for i in range(N)]
li = []
for A,B in ABs:
  li.append([A+B,A,B])
  
li.sort(reverse=True)
flag = True
ans1 = ans2 = 0
for S,A,B in li:
  if flag:
    ans1 += A
  else:
    ans2 += B
  flag = not flag
  
print(ans1-ans2)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
hh = inpl()
dp = [INF]*N
dp[0] = 0

for i in range(1,N):
    tmp = INF
    for j in range(1,K+1):
        tmp = min(abs(hh[i]-hh[i-j])+dp[i-j],tmp)
        if i == j:
            break
    dp[i] = tmp

print(dp[-1])


Fixed submission:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
hh = inpl()
dp = [INF]*N
dp[0] = 0

for i in range(1,N):
    tmp = INF
    for j in range(1,K+1):
        tmp = min(abs(hh[i]-hh[i-j])+dp[i-j],tmp)
        if i == j:
            break
    dp[i] = tmp

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,W = inpl()
wvs = [inpl() for _ in range(N)]
dp = [0]*(W+1)

for w,v in wvs:
    for i in reversed(range(W+1)):
        dp[i] = max(dp[i-w] + v,dp[i])
        if i == w:
            break

print(max(dp))


Fixed submission:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,W = inpl()
wvs = [inpl() for _ in range(N)]
dp = [0]*(W+1)

for w,v in wvs:
    for i in reversed(range(W+1)):
        dp[i] = max(dp[i-w] + v,dp[i])
        if i == w:
            break

print(max(dp))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

H,W = inpl()
MAP = [['#']*(W+2)] + [['#']+list(input())+['#'] for y in range(H)] + [['#']*(W+2)]

dp = np.zeros((H+2,W+2),dtype=np.int)
dp[1][0] = 1

for x in range(1,W+1):
    for y in range(1,H+1):
        if MAP[y][x] == '.':
            dp[y][x] = (dp[y-1][x] + dp[y][x-1])%mod

print(dp[H][W])


Fixed submission:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

H,W = inpl()
MAP = [['#']*(W+2)] + [['#']+list(input())+['#'] for y in range(H)] + [['#']*(W+2)]

dp = [[0]*(W+2) for y in range(H+2)]
dp[1][0] = 1

for x in range(1,W+1):
    for y in range(1,H+1):
        if MAP[y][x] == '.':
            dp[y][x] = (dp[y-1][x] + dp[y][x-1])%mod

print(dp[H][W])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

H,W = inpl()
MAP = [['#']*(W+2)] + [['#']+list(input())+['#'] for y in range(H)] + [['#']*(W+2)]

dp = np.zeros((H+2,W+2),dtype=np.int)
dp[1][0] = 1

for x in range(1,W+1):
    for y in range(1,H+1):
        if MAP[y][x] == '.':
            dp[y][x] = (dp[y-1][x] + dp[y][x-1])%mod

print(dp[H][W])


Fixed submission:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

H,W = inpl()
MAP = [['#']*(W+2)] + [['#']+list(input())+['#'] for y in range(H)] + [['#']*(W+2)]

dp = [[0]*(W+2) for y in range(H+2)]
dp[1][0] = 1

for x in range(1,W+1):
    for y in range(1,H+1):
        if MAP[y][x] == '.':
            dp[y][x] = (dp[y-1][x] + dp[y][x-1])%mod

print(dp[H][W])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

class SegmentTree:
    def __init__(self,N,d):
        self.NN = 1
        while self.NN < N:
            self.NN *= 2
        self.SegTree = [d]*(self.NN*2-1)

    def update(self,i,x): #iの値をxに更新
        i += self.NN - 1
        self.SegTree[i] = x
        while i>0:
            i = (i-1)//2
            self.SegTree[i] = self.process(self.SegTree[i*2+1],self.SegTree[i*2+2])

    def query(self,a,b,k=0,l=0,r=None): #[A,B)の値, 呼ぶときはquery(a,b)
        if r == None: r = self.NN
        if r <= a or b <= l: #完全に含まない
            return -1
        elif a <= l and r <= b : #完全に含む
            return self.SegTree[k]
        else: #交差する
            vl = self.query(a,b,k*2+1,l,(l+r)//2)
            vr = self.query(a,b,k*2+2,(l+r)//2,r)
            return(self.process(vl,vr))

    def process(self,x,y): #x,yが子の時，親に返る値
        return max(x,y)

N = inp()
hh = inpl()
aa = inpl()

seg = SegmentTree(N+1,0)

for i in range(N):
    h,a = hh[i], aa[i]
    tmp = seg.query(0,h) + a
    seg.update(h,tmp)

print(seg.query(0,N+1))


Fixed submission:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

class SegmentTree:
    def __init__(self,N,d):
        self.NN = 1
        while self.NN < N:
            self.NN *= 2
        self.SegTree = [d]*(self.NN*2-1)

    def update(self,i,x): #iの値をxに更新
        i += self.NN - 1
        self.SegTree[i] = x
        while i>0:
            i = (i-1)//2
            self.SegTree[i] = self.process(self.SegTree[i*2+1],self.SegTree[i*2+2])

    def query(self,a,b,k=0,l=0,r=None): #[A,B)の値, 呼ぶときはquery(a,b)
        if r == None: r = self.NN
        if r <= a or b <= l: #完全に含まない
            return -1
        elif a <= l and r <= b : #完全に含む
            return self.SegTree[k]
        else: #交差する
            vl = self.query(a,b,k*2+1,l,(l+r)//2)
            vr = self.query(a,b,k*2+2,(l+r)//2,r)
            return(self.process(vl,vr))

    def process(self,x,y): #x,yが子の時，親に返る値
        return max(x,y)

N = inp()
hh = inpl()
aa = inpl()

seg = SegmentTree(N+1,0)

for i in range(N):
    h,a = hh[i], aa[i]
    tmp = seg.query(0,h) + a
    seg.update(h,tmp)

print(seg.query(0,N+1))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
aa = [inpl() for _ in range(N)]

def Matdot(A,B):
    C = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                C[i][j] += A[i][k]*B[k][j]
            C[i][j] %= mod
    return C

def power(aa,k):
    if k == 1:
        return aa
    elif k%2 == 0:
        tmp = power(aa,k//2)
        return Matdot(tmp,tmp)
    else:
        tmp = power(aa,(k-1)//2)
        return Matdot(Matdot(tmp,tmp),aa)


aa =  power(aa,K)
ans = 0
for a in aa:
    ans += sum(a)
    ans %= mod
print(ans)


Fixed submission:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
aa = [inpl() for _ in range(N)]

def Matdot(A,B):
    C = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                C[i][j] += A[i][k]*B[k][j]
            C[i][j] %= mod
    return C

def power(aa,k):
    if k == 1:
        return aa
    elif k%2 == 0:
        tmp = power(aa,k//2)
        return Matdot(tmp,tmp)
    else:
        tmp = power(aa,(k-1)//2)
        return Matdot(Matdot(tmp,tmp),aa)


aa =  power(aa,K)
ans = 0
for a in aa:
    ans += sum(a)
    ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 998244353
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


# 先にふるってprimesを作る
def hurui(N):
    koho = list(range(2,N))
    prime = []
    limit = math.sqrt(koho[-1])
    while True:
        p = koho[0]
        if limit <= p:
            prime = prime + koho
            break
        else:
            prime.append(p)
            koho = [e for e in koho if e%p != 0]

    return prime

# N を素因数分解
def factorization(N):
    ans = defaultdict(int)
    pind = 0
    while N > 1:
        p = primes[pind]
        while N%p == 0:
            N //= p
            ans[p] += 1
        pind += 1

    return ans


N,P = inpl()

primes = hurui(int(math.sqrt(P))+1)
facs = factorization(P)

ans = 1
for p,n in facs.items():
    if n >= N:
        ans *= p*(n//N)

print(ans)


Fixed submission:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 998244353
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


# 先にふるってprimesを作る
def hurui(N):
    koho = list(range(2,N))
    prime = []
    limit = math.sqrt(koho[-1])
    while True:
        p = koho[0]
        if limit <= p:
            prime = prime + koho
            break
        else:
            prime.append(p)
            koho = [e for e in koho if e%p != 0]

    return prime

# N を素因数分解
def factorization(N):
    ans = defaultdict(int)
    L = len(primes)
    pind = 0
    while N > 1:
        p = primes[pind]
        while N%p == 0:
            N //= p
            ans[p] += 1
        pind += 1
        if pind >= L:
            ans[N] += 1
            break
    return ans

N,P = inpl()

primes = hurui(int(math.sqrt(P))+3)
facs = factorization(P)

ans = 1
for p,n in facs.items():
    if n >= N:
        ans *= p**(n//N)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
hmin = INF
xyh = []
for i in range(N):
    x,y,h = inpl()
    hmin = min(h,hmin)
    xyh.append([x,y,h])

for H in range(hmin,hmin+210):
    for cx in range(101):
        for cy in range(101):
            flag= True
            for x,y,h in xyh:
                if max(H-abs(cx-x)-abs(cy-y),0) != h:
                    flag = False
                    break

            if flag:
                print(cx,cy,H)
                sys.exit()


Fixed submission:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
hmin = INF
xyh = []
for i in range(N):
    x,y,h = inpl()
    hmin = min(h,hmin)
    xyh.append([x,y,h])

for H in range(hmin,hmin+210):
    for cx in range(101):
        for cy in range(101):
            flag= True
            for x,y,h in xyh:
                if max(H-abs(cx-x)-abs(cy-y),0) != h:
                    flag = False
                    break

            if flag:
                print(cx,cy,H)
                sys.exit()