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

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

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graphm():
    n=inp()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((b,w))
        g[b].append((a,w))
    return n,g
def dijkstra(s,to,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d[to-1]

def dijkstra1(s,n,g): # sからの最短距離 頂点数n
    s -= 1
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while len(que)>0:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n,graph = graphm()
    q,k = inpm()
    pre = dijkstra1(k,n,graph)
    for _ in range(q):
        x,y = inpm()
        print( dijkstra(x,k,n,graph) + pre[y-1] )    

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n=int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b,w=map(int,input().split())
        a-=1
        b-=1
        graph[a].append((b,w))
        graph[b].append((a,w))
    graph = tuple(graph)
    q,k = map(int,input().split())
    que = deque([k-1])
    dis = [-1 for _ in range(n)]
    dis[k-1]=0
    while que:
        i = que.pop()
        for j in range(len(graph[i])):
            go = graph[i][j][0]
            d = graph[i][j][1]
            if dis[go]==-1:
                dis[go] = dis[i] + d
                que.append(go)
    for _ in range(q):
        x,y = map(int,input().split())
        print( dis[x-1] + dis[y-1] ) 

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

N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
for i in range(int(pow(P,1/N)//1)+2,0,-1):
    if P%pow(i,N)==0:
        print(i)
        break

### FIXED CODE ###

from collections import Counter
N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
prime = []
f = 2
while f**2 <=P:
    if P%f==0:
        prime.append(f)
        P//=f
    else:
        f += 1
if P != 1:
    prime.append(f)

ans = 1
for k,v in Counter(prime).items():
    if v//N:
        ans *= k**(v//N)
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
#素因数分解(素因数を並べたリスト)(ex:60→[2,2,3,5])
def factorization(n): 
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            for _ in range(cnt):
                arr.append(i)

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)

    return arr
ls = factorization(m)
fi = []
for k in range(2**len(ls)):
    a = 1
    for l in range(len(ls)):
        if (k>>l)&1:
            a *= ls[l]
    if a not in fi:
        fi.append(a)
di = []
for i in range(len(fi)):
    if m//fi[i] >= n:
        di.append(fi[i])
print(max(di))

### FIXED CODE ###

n,m = map(int,input().split())
ls = []
for i in range(1,int(m**(1/2))+1):
    if m % i == 0:
        ls.append(i)
        ls.append(m//i)
ls = sorted(list(set(ls)),reverse=True)
for j in ls:
    if j*n <= m:
        print(j)
        break
### BUGGY CODE ###

N,K = map(int,input().rstrip().split())
A = list(map(int,input().rstrip().split()))
sum =0
while len(A)>=2:
    sum+=1
    A.insert(K,min(A[:K]))
    del A[0:K]
print(sum)

### FIXED CODE ###

import math
N,K = map(int,input().rstrip().split())
print(math.ceil((N-1)/(K-1)))
### BUGGY CODE ###

import itertools
MOD = 10 ** 9 + 7

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i, j in itertools.combinations(a, 2):
    ans += (i ^ j) % MOD

print(ans % MOD)

### FIXED CODE ###

import numpy as np
MOD = 10 ** 9 + 7

n = int(input())
a = np.array(list(map(int, input().split())))
l = len(bin(max(a))) - 2

ans = 0
for i in range(l):
    b = (a >> i) & 1
    x = np.count_nonzero(b)
    now = x * (n - x) * pow(2, i, MOD) % MOD
    ans += now

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

import math
import copy
import fractions
import numpy as np
from functools import reduce

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

n, = map(int, input().split())
data = getInputListInt()

data.sort()

ans = 0

for i in range(n):
    tmp = []
    tmp = copy.deepcopy(data)
    tmp.pop(i)

    gcdans = reduce(fractions.gcd, tmp)

    ans = max(ans, gcdans)

print(ans)


### FIXED CODE ###

import math
import copy
import fractions
import numpy as np
from functools import reduce

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

n, = map(int, input().split())
data = getInputListInt()

gcdNormal = np.zeros(n)
gcdReverse = np.zeros(n)

ans = 0

for i in range(1, n):
    if i==1:
        ans = fractions.gcd(data[i-1], data[i])
        gcdNormal[i] = ans
        gcdNormal[0] = data[0]
    else:
        gcdans = fractions.gcd(ans, data[i])
        ans = min(ans, gcdans)
        gcdNormal[i] = ans

ans = 0

for i in range(n-2, -1, -1):
    if i==n-2:
        ans = fractions.gcd(data[i], data[i+1])
        gcdReverse[i] = ans
        gcdReverse[i+1] = data[i+1]
    else:
        gcdans = fractions.gcd(ans, data[i])
        ans = min(ans, gcdans)
        gcdReverse[i] = ans

ans= 0
for i in range(n):
    if i ==0:
        ans = max(ans, gcdReverse[1])
    elif i == n-1:
        ans = max(ans, gcdNormal[n-2])
    else:
        ans = max(ans, fractions.gcd(gcdNormal[i-1], gcdReverse[i+1]))

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

import sys
input = sys.stdin.readline
M = 10**9+7
n = int(input())
l = list(map(int,input().split()))
x = max(l)
s = bin(x)
u = len(s)-2
o = [0]*u
for i in l:
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u - len(a)
    a = (["0"] * d) + a
    j = 0
    while(j < len(o)):
        if a[j] == "1":
            o[j] = o[j]+1

        j = j+1

cnt = 0
z = len(o)*[0]
for i in range(len(o)):
    z[i] = len(l)-o[i]


for r in range(len(l)-1):
    i = l[r]
    x = bin(i)
    x = x[2:]
    a = list(x)
    d = u-len(a)
    a = (["0"]*d)+a
    j = u-1
    y = 0
    while(j > -1):
        if a[y] == "1":
            #print(o[])
            o[y] = o[y] - 1

        if a[y] == "0":
            z[y] = z[y]-1

        y = y+1
        j = j-1

    j = u-1
    y = 0
    while(j > -1):
        if a[y] == "0":
            cnt = (cnt+((2**j)*o[y])%M)%M

        if a[y] == "1":
            cnt = (cnt + ((2 ** j) * z[y]) % M) % M

        y = y+1
        j = j-1

print(cnt)


### FIXED CODE ###

def readinput():
    n=int(input())
    l=list(map(int,input().split()))
    return n,l

def main(n,a):
    MOD=10**9+7
    hist=[0]*61
    bs=[]
    for i in range(n):
        # s=list(reversed(bin(a[i])[2:]))
        # for j in range(len(s)):
        #     if s[j]=='1':
        #         hist[j]+=1
        # bs.append(s)

        s=bin(a[i])[2:]
        for j in range(len(s)):
            if s[j]=='1':
                hist[len(s)-j-1]+=1
        # j=0
        # ai=a[i]
        # while ai>0:
        #     if ai&1==1:
        #         hist[j]+=1
        #     ai = ai >> 1
        #     j+=1


    #print(bs)
    #print(hist)
    #print(hist)
    sum=0
    # for i in range(n-1):
    #     s=bs[i]
    #     b=1
    #     for j in range(len(s)):
    #         if s[j]=='0':
    #             sum=(sum+hist[j]*b)%MOD
    #         else:
    #             sum=(sum+( n-i-hist[j] )*b)%MOD
    #             hist[j]-=1
    #         b*=2
    #     for j in range(len(s),61):
    #         sum=(sum+hist[j]*b)%MOD
    #         b*=2
    b=1
    for j in range(61):
        sum=(sum+( hist[j]*(n-hist[j])*b )%MOD )%MOD
        b*=2

    return sum

if __name__=='__main__':
    n,l=readinput()
    ans=main(n,l)
    print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)



### FIXED CODE ###

#PythonだとTLEする
N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)
### BUGGY CODE ###

n = int(input())
ans = 0
d = [0] * (n+1)
for i in range(1, n+1):
    for j in range(i, n+1, i):
        d[j] += 1
for i in range(n+1):
    ans += (i * d[i])
print(ans)


### FIXED CODE ###

n = int(input())


def f(x):
    return x * (x + 1) // 2


ans = 0
for x in range(1, n + 1):
    if x * x > n:
        break
    ans += x * x
    y_high = n // x
    ans += 2 * x * (f(y_high) - f(x))
print(ans)
### BUGGY CODE ###

import sys

s =  [0] + [ord(i) for i in sys.stdin.readline()] + [0, 0]

ret = 0
i = 0

while i < len(s) :
    if s[i] == 65 and s[i+1] == 66 and s[i+2] == 67 :
        if s[i - 1] == 65 :
            s[i] += 1
            s[i+1] += 1
            s[i+2] -= 2
            i -= 1
        else :
            s[i+2] -= 2
            i += 2
        ret += 1
        
    else :
        i += 1

print(ret)


### FIXED CODE ###

s =  list(input())

ret = 0
i = 0
a = 0
bc = 0

while True :
    while i < len(s) and s[i] == 'A' :
        a += 1
        i += 1

    while i < len(s) - 1 and s[i:i+2] == ['B', 'C']  :
        bc += 1
        i += 2

    ret += a * bc

    bc = 0

    if i < len(s) and s[i] != 'A' :
        a = 0
        
    while i < len(s) and s[i] != 'A' :
        i += 1

    if i >= len(s) - 1 :
        break
    

print(ret)
### BUGGY CODE ###

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

# 各数値が何個あるか
C = [0]*(2100)
for l in L:
    C[l] += 1

# 累積和を作成する
S = [0]
for i in range(2100):
    S.append(S[i]+C[i])

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue

        left = abs(L[i]-L[j])+1
        right = L[i]+L[j]
        tmp = S[right]-S[left]

        if left <= L[i] <= right:
            tmp -= 1
        if left <= L[j] <= right:
            tmp -= 1
        ans += max(0, tmp)

print(ans//6)


### FIXED CODE ###

import bisect

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

L.sort()
ans = 0
for i in range(N-1):
    for j in range(i+1, N-1):
        idx = bisect.bisect_left(L, L[i]+L[j])
        ans += max(0, idx-j-1)
print(ans)
### BUGGY CODE ###

from fractions import*
n,m,*a=map(int,open(0).read().split())
s=1
d=set()
for i in a:
  i//=2
  s*=i//gcd(s,i)
  t=0
  while i%2<1:t+=1
  d|={t}
print((0--(m//s)//2)*(len(d)<2))

### FIXED CODE ###

from fractions import*
n,m,*a=map(int,open(0).read().split())
s=1
d=set()
for i in a:
  i//=2
  s*=i//gcd(s,i)
  t=0
  while i%2<1:
    t+=1
    i//=2
  d|={t}
print((0--(m//s)//2)*(len(d)<2))
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
s=[list(input()) for _ in range(H)]

white=sum([1 if s[y][x]=='.' else 0 for x in range(W) for y in range(H)])
q = deque([(0,0,1)])
while q:
    x,y,l=q.popleft()
    if x==W-1 and y==H-1:
        print(white-l)
        break
    s[y][x]='*'
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H and s[ny][nx]=='.':
            q.append((nx,ny,l+1))
else:
    print(-1)
    


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
white=0
s=[]
for y in range(H):
    line=input()
    white+=line.count('.')
    s.append(list(line))

q = deque([(0,0,1)])
q_append=q.append
q_popleft=q.popleft
while q:
    x,y,l=q_popleft()
    if s[y][x]!='.':
        continue
    if x==W-1 and y==H-1:
        print(white-l)
        break
    s[y][x]='*'
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H:
            q_append((nx,ny,l+1))
else:
    print(-1)
### BUGGY CODE ###


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

L = sum(X)

dp = [[[0]*(N+1) for _ in range(L+10)] for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(L+10):
        for k in range(N):
            dp[i+1][j][k] += dp[i][j][k]
            if j >= X[i]:
                dp[i+1][j][k+1] += dp[i][j-X[i]][k]
            
ans = 0
for k in range(1,N+1):
    if A*k > L:break
    ans += dp[N][A*k][k]
                
print(ans)
                
                

### FIXED CODE ###


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

L = sum(X)

dp = [[[0]*(N+1) for _ in range(L+10)] for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(L+10):
        for k in range(N):
            dp[i+1][j][k] += dp[i][j][k]
            if j >= X[i]:
                dp[i+1][j][k+1] += dp[i][j-X[i]][k]
            
ans = 0
for k in range(1,N+1):
    if A*k > L:break
    ans += dp[N][A*k][k]
                
print(ans)
### BUGGY CODE ###

def combination(n,r,mod=10**9+7):
    n1 = n+1
    r = min(r,n-r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) % mod
  
mod = int(1e9+7)
n,a,b= map(int,input().split())
 
S = (pow(2,n)-1)%mod
A = combination(n,a)
B = combination(n,b)
ans = (S-A-B)%mod
 
print(ans)

### FIXED CODE ###

def combination(n,r,mod=10**9+7):
    n1 = n+1
    r = min(r,n-r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) % mod

def power_func(a,n,p):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

mod = int(1e9+7)
n,a,b= map(int,input().split())

S = (power_func(2,n,mod) - 1)%mod
A = combination(n,a)
B = combination(n,b)
ans = (S-A-B)%mod

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

import collections

result = 0
n,k = map(int,input().split())
input_list = input().split()
counter_list = collections.Counter(input_list)
if k < len(counter_list):
  for i in range(len(counter_list)-k):
    result += sorted(counter_list.values())[i]
print(result)

### FIXED CODE ###

import collections

result = 0
n,k = map(int,input().split())
input_list = input().split()
counter_list = collections.Counter(input_list)
if k < len(counter_list):
  length = len(counter_list)-k
  sort_list = sorted(counter_list.values())
  for i in range(length):
    result += sort_list[i]
print(result)
### BUGGY CODE ###

N, K = [int(n) for n in input().split()]
P =  [int(n) for n in input().split()]
o = {}
for i in range(1,1001):
    o[i] = sum([(j/i) for j in range(1,i+1)])
ans = 0
for k in range(N-K+1):
    m = sum([o[x] for x in P[k:k+K]])
    if m > ans:
        ans = m
print(ans)

### FIXED CODE ###

N, K = [int(n) for n in input().split()]
P = [(int(n)+1)/2 for n in input().split()]
ans = sum(P[:K])
e = ans
for p,x in zip(P, P[K:]):
    e = e-p+x
    if ans < e:
        ans = e
print(ans)
### BUGGY CODE ###

a = int(input())

l = list(map(int,input().split()))
ans = 1

for i in l:
    ans *= i
if ans > 10**18:
    ans=-1
print(ans)

### FIXED CODE ###


a = input()
l = list(map(int,input().split()))
ans = 1
if 0 in l:
    print(0)
    exit()
for i in l:
    ans *= i
    if ans>10**18:
        print(-1)
        exit()
if ans > 10**18:
    ans=-1
print(ans)
### BUGGY CODE ###

n = input().split()
N = int(n[0])
K = int(n[1])

listb = [1]
C = 1
A = list(map(int, input().split()))
                 
for i in range(N):
    C = A[C-1]
    if C not in listb:
        listb.append(C)
    else:
        D = listb.index(C)
        listb.append(C)
        break

L = len(listb) -1

if K <= N:
    print(listb[K])
else:
    if L-D == 1 or L-D == 0:
        print(C)
    else:
        M = (K-D) % (L-D)
        print(listb[(D+M)%L])

### FIXED CODE ###

n = input().split()
N = int(n[0])
K = int(n[1])

listb = [1]
listc = [0]*N
C = 1
A = list(map(int, input().split()))
                 
for i in range(N):
    C = A[C-1]
    if listc[C-1] == 0:
        listb.append(C)
        listc[C-1] = 1
    else:
        D = listb.index(C)
        listb.append(C)
        break

L = len(listb) -1

if K <= N:
    print(listb[K])
else:
    if L-D == 1 or L-D == 0:
        print(C)
    else:
        M = (K-D) % (L-D)
        print(listb[(D+M)%L])
### BUGGY CODE ###

class MaxHeap():
    def __init__(self, a, h):
        self.a = a
        self.h = h
        
    def parent(self, i):
        return i//2
        
    def left(self, i):
        return 2 * i

    def right(self, i):
        return 2 * i + 1

    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        if l <= self.h and self.a[l] > self.a[i]:
            largest = l
        else:
            largest = i
        if r <= self.h and self.a[r] > self.a[largest]:
            largest = r
        if largest != i:
            self.a[i], self.a[largest] = self.a[largest], self.a[i]
            self.maxHeapify(largest)

    def extract(self):
        if self.h < 1:
            return -1
        maxv = self.a[1]
        self.a[1] = self.a.pop()
        self.h -= 1
        self.maxHeapify(1)
        return maxv
        
    def increaseKey(self, i, k):
        if k < self.a[i]:
            return
        self.a[i] = k
        while i > 1 and self.a[i//2] < self.a[i]:
            self.a[i], self.a[i//2] = self.a[i//2], self.a[i]
            i = i // 2

    def insert(self, k):
        self.h += 1
        self.a.append(-1)
        self.increaseKey(self.h, k)

if __name__ == '__main__':
    a = [-1]
    x = MaxHeap(a, 0)
    while True:
        com = input().rstrip()
        if com == "end":
            break
        elif com.startswith("insert"):
            k = int(com.split(" ")[1])
            x.insert(k)
        elif com.startswith("extract"):
            print(x.extract())
    

### FIXED CODE ###

import heapq
import sys

h = []

for com in sys.stdin.readlines():
    if com[0] == "i":
        heapq.heappush(h, -int(com[7:]))
    elif com[1] == "x":
        print(-heapq.heappop(h))
### BUGGY CODE ###

MAX_A = 10**6 + 1
MAX_P = MAX_A // 2
is_prim = [i%2==1 for i in range(MAX_P)]
is_prim[1] = False; is_prim[2] = True
for i in range(3, MAX_P):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_P, i): is_prim[j] = False

def solve():
    c = 0
    C = [0] * MAX_A
    for a in A:
        # for p in [i for i in range(MAX_P) if is_prim[i] and a%i==0]:
        for p, f in zip(range(MAX_P), is_prim):
            if not f: continue
            if a%p: continue
            C[p] += 1
            c = max(c, C[p])
    if c <= 1: return "pairwise"
    elif c <= n-1: return "setwise"
    return "not"

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')


### FIXED CODE ###

n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for i in range(2, MAX_A):
        if sum(C[i:MAX_A:i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')
### BUGGY CODE ###


N=int(input())

S=[]
for n in range(N):
    s=input()
    s=''.join(sorted(s))
    S.append(s)

total=0
for i in range(len(S)):
    key=S[i]
    for j in range(i+1,N):
        if key==S[j]:
            total+=1

print(total)

### FIXED CODE ###


N=int(input())
S=[]
total=0

for s in range(N):
    tmp=input()
    S.append("".join(sorted(tmp)))

S=sorted(S)
S_key=list(set(S))
count=[0]*len(S_key)
S_dict=dict(zip(S_key,count))


for s in S:
    total+=S_dict[s]
    S_dict[s]+=1

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

#DAGの最長有向パスをトポロジカルソートで解く
from collections import defaultdict

N,M=map(int,input().split(' '))
se=set()
d=defaultdict(int)
for i in range(M):
    x,y=map(int,input().split(' '))
    se.add(x*(10**5)+y)
n=set(i for i in range(1,N+1))
while N>0:
    m=set([x%10**5 for x in se])
    for i in n-m:
        n.remove(i)
        N-=1
        de=[x for x in se if x//10**5==i]
        for j in de:
            k=j%10**5
            se.remove(j)
            if d[k]<=d[i]:
                d[k]=d[i]+1
print(max(d.values()))

### FIXED CODE ###

from collections import defaultdict, deque

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

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1
length=defaultdict(int)

q = deque(set(i for i in range(1,N+1))-set(ins.keys()))
length=defaultdict(int)
while q:
    v1 = q.popleft()
    for v2 in outs[v1]:
        ins[v2] -= 1
        if length[v2]<=length[v1]:
            length[v2]=length[v1]+1
        if ins[v2] == 0:
            q.append(v2)

print(max(length.values()))