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

import math
N, P = map(int, input().split())
x = math.ceil(pow(P, 1/N))

for i in range(x, 0, -1):
    if P % pow(i, N) == 0:
        print(i)
        break


### FIXED CODE ###

import math
N, P = map(int, input().split())
x = math.floor(math.pow(P, 1/N))
if x==1:
    print(1)
    exit()
x+=1
for i in range(x, 0, -1):
    if P % pow(i, N) == 0:
        print(i)
        break
### BUGGY CODE ###

def score(a,b):
    if b-a >= 0:
        return a
    else:
        return 10**6+1-b

N = int(input())

S = [0]*N
A = [0]*N
B = [0]*N

for i in range(N):
    S[i] = input()
    a = 0
    b = 0
    for j in range(len(S[i])):
        if S[i][j] == ')':
            a += 1
        else:
            a -= 1
        A[i] = max(A[i],a)

        if S[i][-j-1] == '(':
            b += 1
        else:
            b -= 1
        B[i] = max(B[i],b)

#print('S',S)
#print('A',A)
#print('B',B)

L = sorted(list(range(N)),key = lambda i:score(A[i],B[i]))

#print('L',L)
SS = ""

for x in L:
    SS += S[x]

#print('SS',SS)
SA = 0
SB = 0
a = 0
b = 0
for j in range(len(SS)):
    if SS[j] == ')':
        a += 1
    else:
        a -= 1
    
    if SS[-j-1] == '(':
        b += 1
    else:
        b -= 1
    #print(j,a,b)
    SA = max(SA,a)
    SB = max(SB,b)

#print(SA,SB)
if SA == 0 and SB == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

def score(a,b):
    if b-a >= 0:
        return a
    else:
        return 10**6+1-b

N = int(input())

A = [0]*N
B = [0]*N

for i in range(N):
    S = input()
    a = 0
    b = 0
    for j in range(len(S)):
        if S[j] == ')':
            a += 1
        else:
            a -= 1
        A[i] = max(A[i],a)

        if S[-j-1] == '(':
            b += 1
        else:
            b -= 1
        B[i] = max(B[i],b)

#print('S',S)
#print('A',A)
#print('B',B)

L = sorted(list(range(N)),key = lambda i:score(A[i],B[i]))

SA = 0
SB = 0

#print('L',L)

for i in range(N):
    if SB > A[L[i]]:
        SB += B[L[i]] - A[L[i]]
    else:
        SA += A[L[i]]-SB
        SB = B[L[i]]
    #print(SA,SB)

if SA == 0 and SB == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

def get_divisors(n):
    from math import sqrt, ceil
    divisors = []
    for num in range(ceil(sqrt(n)), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.append(num)
    divisors.sort(reverse=True)
    return divisors

total = sum(A)
divisors = get_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if nr+pr >= 0:
            if pr <= K and nr+pr == 0:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)


### FIXED CODE ###

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

# nの約数を求める。計算量O(sqrt(N))
def get_divisors(n):
    from math import sqrt, ceil
    from collections import deque
    divisors = deque([])
    for num in range(ceil(sqrt(n)), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.appendleft(num)
    return list(divisors)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors

total = sum(A)
divisors = make_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if nr+pr >= 0:
            if pr <= K and nr+pr == 0:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)
### BUGGY CODE ###

h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]

c=[[0]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    c[i][j]=abs(a[i][j]-b[i][j])

dp=[[() for i in range(w)] for j in range(h)]
dp[0][0]+=(c[0][0],)
for i in range(h):
  for j in range(w):
    for k in range(len(dp[i-1][j])):
      dp[i][j]+=(abs(dp[i-1][j][k]-c[i][j]),)
      dp[i][j]+=(dp[i-1][j][k]+c[i][j],)
    for k in range(len(dp[i][j-1])):
      dp[i][j]+=(abs(dp[i][j-1][k]-c[i][j]),)
      dp[i][j]+=(dp[i][j-1][k]+c[i][j],)
    dp[i][j]=tuple(set(dp[i][j]))
print(min(dp[h-1][w-1]))

### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  dp=[[[0]*(80*(h+w+1)+1) for i in range(w)] for j in range(h)]
  dp[0][0][abs(a[0][0]-b[0][0])]=1
  for i in range(h):
    for j in range(w):
      c=abs(a[i][j]-b[i][j])
      if i!=0 or j!=0:
        for k in range(80*(i+j+1)+1):
          dp[i][j][k]=dp[i-1][j][abs(k-c)]|dp[i-1][j][k+c]|dp[i][j-1][abs(k-c)]|dp[i][j-1][k+c]
  for i in range(80*(h+w+1)+1):
    if dp[h-1][w-1][i]==1:
      print(i)
      break

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

h,w=map(int, input().split())
s=[[0 for _ in range(w)] for _ in range(h)]
for j in range(h):
    s[j]=list(input())
l=[[0 for _ in range(w)] for _ in range(h)]
r=[[0 for _ in range(w)] for _ in range(h)]
u=[[0 for _ in range(w)] for _ in range(h)]
d=[[0 for _ in range(w)] for _ in range(h)]
max=0

for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            l[i][j]=0
            u[i][j]=0
        else:
            if j==0:
                l[i][j]=1
            else:
                l[i][j]=l[i][j-1]+1
            if i==0:
                u[i][j]=1
            else:
                u[i][j]=u[i-1][j]+1
                      
for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if s[i][j]=='#':
            r[i][j]=0
            d[i][j]=0
        else:
            if j==w-1:
                r[i][j]=1
            else:
                r[i][j]=r[i][j+1]+1
            if i==h-1:
                d[i][j]=1
            else:
                d[i][j]=d[i+1][j]+1
                   
for i in range(h):
    for j in range(w):        
        total=l[i][j]+r[i][j]+d[i][j]+u[i][j]

        if max<total:
            max=total

print(max-3)

### FIXED CODE ###

h,w=map(int, input().split())
s=[[0 for _ in range(w)] for _ in range(h)]
for j in range(h):
    s[j]=list(input())
l=[[0 for _ in range(w)] for _ in range(h)]
r=[[0 for _ in range(w)] for _ in range(h)]
u=[[0 for _ in range(w)] for _ in range(h)]
d=[[0 for _ in range(w)] for _ in range(h)]
max=0

for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            l[i][j]=0
            u[i][j]=0
        else:
            if j==0:
                l[i][j]=1
            else:
                l[i][j]=l[i][j-1]+1
            if i==0:
                u[i][j]=1
            else:
                u[i][j]=u[i-1][j]+1
                      
for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if s[i][j]=='#':
            r[i][j]=0
            d[i][j]=0
        else:
            if j==w-1:
                r[i][j]=1
            else:
                r[i][j]=r[i][j+1]+1
            if i==h-1:
                d[i][j]=1
            else:
                d[i][j]=d[i+1][j]+1
                   
for i in range(h):
    for j in range(w):        
        total=l[i][j]+r[i][j]+d[i][j]+u[i][j]

        if max<total:
            max=total

print(max-3)
### BUGGY CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline
S = S()
S = [S[i] for i in range(len(S))]
Q = I()
rev = False
for i in range(Q):
    q = LS()
    if q[0] == '1':
        rev = not rev
        continue
    if (q[1] == '1') ^ rev:
        S = [q[2]]+S
    else:
        S = S+[q[2]]
if rev:
    ans = ''.join(S[::-1])
else:
    ans = ''.join(S)

print(ans)




### FIXED CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline
S = S()
S = [S[i] for i in range(len(S))]
QS= deque(S)
S = QS
Q = I()
rev = False
for i in range(Q):
    q = LS()
    if q[0] == '1':
        rev = not rev
        continue
    if (q[1] == '1') ^ rev:
        S.appendleft(q[2])
    else:
        S.append(q[2])
if rev:
    ans = ''.join(reversed(S))
else:
    ans = ''.join(S)

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

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

stack=[]

import copy

stack.append([0,[],-1])
Nhalf=None
while stack:
  node=stack.pop()
  v=node[0]
  route=node[1]
  parent=node[2]
  if v==N-1:
    route.append(v)
    if len(route)%2==0:
      Nhalf=route[len(route)//2-1]
      NhalfNext=route[len(route)//2]
    else:
      Nhalf=route[len(route)//2]
      NhalfNext=route[len(route)//2+1]
      
    E[Nhalf].remove(NhalfNext)
    E[NhalfNext].remove(Nhalf)
    break
  route.append(v)
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    newroute=copy.copy(route)
    stack.append([child,newroute,v])

stack=[]
stack.append([0,-1])
count=0
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
  count+=1
  childs=E[v]
  if childs==None:
    continue
  for child in childs:
    if child==parent:
      continue
    stack.append([child,v])
  
if count>N-count:
  print("Fennec")
else:
  print("Snuke")

### FIXED CODE ###

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

F=[0]*N
S=[0]*N

stack=[]
# 番号、距離、親
stack.append([0,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  F[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])
  
stack=[]
# 番号、距離、親
stack.append([N-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  S[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])

FenWin=0
SunWin=0
for i in range(N):
  if F[i]<=S[i]:
    FenWin+=1
  else:
    SunWin+=1
print(("Snuke","Fennec")[FenWin>SunWin])
### BUGGY CODE ###

import numpy as np

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

L = np.zeros(N, dtype=int)
R = np.zeros(N, dtype=int)
for m in range(M):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    
    L *= 2
    R *= 2
    
    L[:l+1] += 1
    R[r:] += 1

for _ in range(Q):
    p, q = map(int, input().split())
    
    print (bin(L[p - 1] & R[q - 1]).count("1"))

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def main():
    N, M, Q = read_values()
    S = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
    
    for _ in range(M):
        l, r = read_values()
        S[l][r] += 1

    for l in range(N):
        for r in range(N):
            S[l + 1][r + 1] += S[l + 1][r] + S[l][r + 1] - S[l][r] 

    res = [0] * Q
    for i in range(Q):
        p, q = read_values()
        res[i] = str(S[q][q] - S[p - 1][q] - S[q][p - 1] + S[p - 1][p - 1])
    print("\n".join(res))


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

def d():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    # print('A = {}'.format(A))
    warps = [1]

    for i in range(K):
        city = A[warps[-1] - 1]
        # print('city, warps = {}, {}'.format(city, warps))
        if city in warps:
            loop_start_index = warps.index(city)
            loop = warps[loop_start_index:]
            K -= loop_start_index
            print(loop[K % len(loop)])
            return
        else:
            warps.append(city)
    print(warps[-1])


##########
if __name__ == "__main__":
    d()


### FIXED CODE ###

def d():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    # print('A = {}'.format(A))
    warps = [1]
    w = {}

    for i in range(K):
        city = A[warps[-1] - 1]
        # print('city, warps = {}, {}'.format(city, warps))
        if city in w:
            lsi = warps.index(city)
            Kn = (K - lsi) % (len(warps) - lsi)
            print(warps[lsi + Kn])
            return
        else:
            warps.append(city)
            w[city] = city
    print(warps[-1])


def dd():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    v = []
    w = {}
    now = 0
    for i in range(K):
        print('i, v, w, now = {}, {}, {}, {}'.format(i, v, w, now))
        p = A[now]
        now = p-1
        if p in w:
            j = v.index(p)
            df = i-j
            Kn = (K-i-1) % df
            p = v[j+Kn]
            break
        else:
            v.append(p)
            w[p] = p
    print(p)


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

n=int(input())
for i in range(1,n+1):
  ans=0
  for x in range(1,50):
    for y in range(x,50):
      for z in range(y,50):
        if (x+y)**2+(y+z)**2+(z+x)**2==2*i:
          if x==y==z:
            ans+=1
          elif (x==y and y!=z) or (x!=y and y==z):
            ans+=3
          elif x!=y and y!=z:
            ans+=6
  print(ans)


### FIXED CODE ###

n=int(input())
ans=[0 for i in range(10050)]
for i in range(1,105):
  for j in range(1,105):
    for k in range(1,105):
      v=i*i+j*j+k*k+i*j+i*k+j*k
      if v<10050:
        ans[v]+=1
for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

N = int(input()); MOD = pow(10,9)+7
C= list(map(int,input().split()))
C.sort()

#L = [48,20,8,3,1]
L = [1]
for i in range(1,N):
  temp = (i+2)*pow(2,i-1)
  L.append(temp)
  
L.reverse()
ans = 0
for i in range(N):
  ans = (ans + L[i]*pow(2,i)*C[i])%MOD
#ans = ans%MOD
print(ans*pow(2,N,MOD)%MOD)


### FIXED CODE ###

N = int(input()); MOD = pow(10,9)+7
C= list(map(int,input().split()))
C.sort()

#L = [48,20,8,3,1]
L = [1]
for i in range(1,N):
  temp = (i+2)*pow(2,i-1,MOD)
  L.append(temp)
  
L.reverse()
ans = 0
for i in range(N):
  ans = (ans + L[i]*pow(2,i,MOD)*C[i])%MOD
#ans = ans%MOD
print(ans*pow(2,N,MOD)%MOD)
### BUGGY CODE ###

import itertools
import heapq
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = []
for i in comb:
  l.append(list(i))
  
A = []
one = [1]*len(l)
for i in range(len(l)):
  for j in range(k):
    one[i]*=l[i][j]
    A.append(one[i])
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

from collections import defaultdict

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

lamp = {}
for i in range(1, N+1):
    lamp[i] = A[i-1]

for k in range(K):
    lamp_next = defaultdict(lambda: 0)
    for i in range(1, N+1):
        l = i - lamp[i]
        if l < 1:
            l = 1
        r = i + lamp[i]
        if r > N:
            r = N
        for j in range(l, r+1):
            lamp_next[j] += 1
    lamp = lamp_next

ans = [lamp[i] for i in range(1, N+1)]
print(*ans)

### FIXED CODE ###

import itertools

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

for _ in range(K):
    B = [0] * N
    for i in range(N):
        l = max(0, i-A[i])
        r = min(N-1, i+A[i])
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
    B = list(itertools.accumulate(B))
    A = B.copy()
    if A == [N] * N:
        break
print(*A)
### BUGGY CODE ###

N = int(input())
data = list(map(int, input().split()))
exist_tuple = tuple(data)
for i in range(1, N + 1):
    if i in exist_tuple:
        print(data.count(i))
    else:
        print("0")

### FIXED CODE ###

from collections import Counter

N = int(input())
data = Counter(list(map(int, input().split())))
for i in range(1, N + 1):
    print(data[i])
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,n=map(int,input().split())
    lis=[]
    for i in range(n):
        lis.append(tuple(map(int,input().split())))
    dp=[10**10]*(h+1)
    dp[0]=0
    for l in lis:
        a,b=l[0],l[1]
        for i in range(1,h+1):
            dp[i]=min(dp[i],min(dp[max(i-a,0):i])+b)
    print(dp[h])



if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    dp=np.zeros(10**4+1,int)
    dp[0]=0
    for l in lis:
        dp[1:l[0]+1]=np.minimum(dp[1:l[0]+1],l[1])
    for i in range(1,h+1):
        dp[i]=np.min(dp[i-lis[:,0]]+lis[:,1])
    print(dp[h])

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

N = int(raw_input())
S = [list(raw_input()) for t in range(N)]
ans = 0
for n in range(N):
  isSym = True
  for i in range(N):
    for j in range(i,N):
      if S[i][j] != S[j][i]:
        isSym = False
        break
    if not isSym:
      break
  ans += 1 if isSym else 0
  s = S.pop()
  S.insert(0, s)
print ans*N


### FIXED CODE ###

N = int(raw_input())
S = [list(raw_input()) for t in range(N)]
ans = 0
for n in range(N):
  t = S[n:]+S[:n]
  t_t = list(map(list, zip(*t)))
  if t == t_t:
    ans += 1
#for n in range(N):
#  isSym = True
#  for i in range(N):
#    for j in range(i,N):
#      if S[i][j] != S[j][i]:
#        isSym = False
#        break
#    if not isSym:
#      break
#  ans += 1 if isSym else 0
#  s = S.pop()
#  S.insert(0, s)
print ans*N
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

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

T=[[] for i in range(N)]

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

O=[0 for i in range(N)]

for i in range(Q):
    p,x=map(int,input().split())
    O[p-1]+=x

def dfs(n,r):
    for i in T[n]:
        if i!=r:
            O[i]+=O[n]

            dfs(i,n)

dfs(0,-1)

print(*O)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
input=sys.stdin.readline

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

T=[[] for i in range(N)]

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

O=[0 for i in range(N)]

for i in range(Q):
    p,x=map(int,input().split())
    O[p-1]+=x

def dfs(n):
    for i in T[n]:
        if r[i]:continue
        r[i]=1
        O[i]+=O[n]
        dfs(i)

r=[1]+[0]*(N-1)

dfs(0)

print(*O)
### BUGGY CODE ###

n,m=map(int,input().split())
L=list(map(int,input().split()))
import bisect
from collections import deque
L.sort()
Ld=deque(L)
for i in range(m):
    x=L.pop()//2
    y=bisect.bisect_left(L,x)
    L.insert(y,x)
print(sum(L))

### FIXED CODE ###

n,m=map(int,input().split())
L=list(map(int,input().split()))
Lh=list(map(lambda x: x*(-1), L))
import heapq
#heapqは置き直さなくてOK
heapq.heapify(Lh)
for _ in range(m):
    x=heapq.heappop(Lh)
    heapq.heappush(Lh,(x+1)//2)#負の数の割り算のため+1
print(sum(Lh)*(-1))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod = 10**9+7

ans = 0
for i in range(n-1):
    aa = a.pop()
    # print(a,aa)
    ans +=  (aa * sum(a)) % mod
    ans %= mod

print(ans%mod)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod = 10**9+7

ans = 0
aa = 0
for i in range(n-1):
    aa += a.pop()
    # print(a,aa)
    ans +=  (aa * a[-1]) % mod
    ans %= mod

print(ans%mod)
### BUGGY CODE ###

import fractions as math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
N=int(input())
A=list(map(int,input().split()))
tmp=lcm_list(A)
ans=0
for i in A:
  ans+=tmp//i
  ans%=(10**9+7)
print(int(ans))


### FIXED CODE ###

import fractions 
N=int(input())
A=list(map(int,input().split()))
t=A[0]
for i in range(1,N):
  t=(t*A[i])//fractions.gcd(t,A[i])
ans=0
for i in range(N):
  ans+=t//A[i]
print(ans%(10**9+7))
### BUGGY CODE ###

h,a=map(int,input().split())
att=0
while(h!=0):
  att+=1
  h=h-a
print(att)

### FIXED CODE ###

h,a=map(int,input().split())
if(h%a!=0):
  print(h//a+1)
else:
  print(h//a)
### BUGGY CODE ###

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

ans = 0
while(len(a)):
    a_min = a.pop(0)
    if len(a) == 0:
        ans += 1
        break
    if a_min == a[0]:
       ans -= 1 
    a = [el for el in a if el % a_min != 0]
    ans += 1
    
print(ans)

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
max_a = a[-1]

q = [0] * (max_a + 1)
for i in a:
    if q[i] == 1 or q[i] == -1:
        q[i] = -1
        continue
    for j in range(2*i, max_a+1, i):
        q[j] = -1
    q[i] = 1

total = 0
for i in q:
    if i == 1:
        total += 1
print(total)