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

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def bw(i, p):
    if dp[i] != [0, 0]:
        return dp[i]
    b = w = 1
    for ii in h[i]:
        if ii in p: continue
        bwi = bw(ii, p + [ii])
        w *= (bwi[0] + bwi[1])
        b *= bwi[1]
        w %= md
        b %= md
    dp[i] = [b, w]
    return [b, w]


md = 10 ** 9 + 7
n = int(input())
if n == 1:
    print(2)
    exit()
h = {}
c = [0] * n
for _ in range(n - 1):
    a, b = map(int, input().split())
    h.setdefault(a, [])
    h.setdefault(b, [])
    h[a] += [b]
    h[b] += [a]
    c[a - 1] += 1
    c[b - 1] += 1
#print(c)
#print(h)
i = c.index(max(c)) + 1
dp = [[0, 0] for _ in range(n + 1)]
b, w = bw(i, [i])
print((b + w) % md)
#print(dp)


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def bw(i, p):
    if dp[i] != [0, 0]:
        return dp[i]
    b = w = 1
    for ii in h[i]:
        if ii == p: continue
        bwi = bw(ii,i)
        w *= (bwi[0] + bwi[1])
        b *= bwi[1]
        w %= md
        b %= md
    dp[i] = [b, w]
    return [b, w]


md = 10 ** 9 + 7
n = int(input())
if n == 1:
    print(2)
    exit()
h = {}
for _ in range(n - 1):
    a, b = map(int, input().split())
    h.setdefault(a, [])
    h.setdefault(b, [])
    h[a] += [b]
    h[b] += [a]
dp = [[0, 0] for _ in range(n + 1)]
b, w = bw(1, 1)
print((b + w) % md)
### BUGGY CODE ###

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

ans=0

for i in range(2 **N):
    x=0
    y=0
    z=0
    t=0

    for j in range(N):
        if ((i >> j) & 1):
            x += S[j][0]
            y += S[j][1]
            z += S[j][2]
            t += 1
            if t > M:
                break

    hoge = abs(x) + abs(y) + abs(z)
    if hoge > ans and t==M:
        ans=hoge

print(ans)

### FIXED CODE ###

N,M=map(int, input().split())
S = [list(map(int, input().split())) for _ in range(N)]
import copy
import heapq
ans=0

for i in range(8):
    li=[]
    heapq.heapify(li)
    hoge=[1,1,1]

    for j in range(3):
        if ((i >> j) & 1):
            hoge[j]=-1
    for k in range(N):
        tmp=0
        for r in range(3):
            tmp += S[k][r] * hoge[r]
        heapq.heappush(li, tmp)
    re=0
    for t in range(M):
        re += heapq.heappop(li)

    re = abs(re)
    if re > ans :
        ans=re

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

n = int(input())

dic = {}

for i in range(n):
    s = input()
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

max_k_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())]
max_k_list.sort()

for s in max_k_list:
    print(s)


### FIXED CODE ###

n = int(input())

s_list = [""]*n

for i in range(n):
    s_list[i] = input()

s_list.sort()

ans_list = [s_list[0]]
pre_s = s_list[0]
count = 1
max_count = count

if len(s_list) == len(set(s_list)):
    ans_list = s_list
        
    ans_list.sort()

    for s in ans_list:
        print(s)

    exit()


for i in range(1,n):
    if pre_s == s_list[i]:
        count += 1
        if count == max_count:
            ans_list.append(s_list[i])
        if count > max_count:
            max_count = count
            ans_list = [s_list[i]]
    else:
        pre_s = s_list[i]
        count = 1

ans_list.sort()

for s in ans_list:
    print(s)
### BUGGY CODE ###

import sys
import math
def get_prime(m):
    a = [2]+[i for i in range(3,m+1,2)]
    end = int(math.sqrt(m))
    for i in range(3, end, 2):
        if (i in a):
            for j in range(i*2, m, i):
                if (j in a):
                    a.remove(j)
            
    return a
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
primes = get_prime(max(a))
result = 0
for i in range(n):
    if a[i] in primes:
        result+=1
print(result)

### FIXED CODE ###

import math
n = int(input())
cnt = 0
for i in range(n):
    num = int(input())
    flag = True
    for j in range(2, int(math.sqrt(num))+1):
        if num%j == 0:
            flag = False
            break
    if flag:
        cnt+=1
print(cnt)
### BUGGY CODE ###

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    # 総和がx以上になる位置のindex をbinary search
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri <= self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

n = int(input())
a = [[int(x),i] for i,x in enumerate(input().split())]
a.sort()
bit = BIT(n)

ans = 0

for i in range(n):
    x,ind = a[i]
    s = bit.sum(ind)
    if s == 0:
        l = 0
    else:
        l = bit.bsearch(s)
    s2 = s+1
    if s2 > i:
        r = n
    else:
        r = bit.bsearch(s2)-1
    ans += x*(r-ind)*(ind-l+1)
    bit.add(ind,1)
    
print(ans)

### FIXED CODE ###

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    # 総和がx以上になる位置のindex をbinary search
    def bsearch(self,x):
        le = 0
        ri = 1<<(self.size.bit_length()-1)
        while ri > 0:
            if le+ri <= self.size and self.tree[le+ri]<x:
                x -= self.tree[le+ri]
                le += ri
            ri >>= 1
        return le+1

n = int(input())
a = [[int(x),i] for i,x in enumerate(input().split())]
a.sort()
bit = BIT(n)

ans = 0

for i in range(n):
    x,ind = a[i]
    s = bit.sum(ind)
    if s == 0:
        l = 0
    else:
        l = bit.bsearch(s)
    s2 = s+1
    if s2 > i:
        r = n
    else:
        r = bit.bsearch(s2)-1
    ans += x*(r-ind)*(ind-l+1)
    bit.add(ind,1)
    
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)

def f(a):
  global R,G,B,N,ans,Rm,Gm,Bm

  for b in range(N-R*a+1):
    cmod=(N-R*a-G*b)%B
    c=(N-R*a-G*b)//B
    if cmod==0 and  c>=0:
      ans+=1
    elif c<0:
      break

  if a>0:
    f(a-1)


R,G,B,N=list(map(int,input().split(" ")))
Rm=N//R
Gm=N//G
Bm=N//B

ans=0

f(Rm)

print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

def f(a):
  global R,G,B,N,ans,Rm,Gm,Bm

  for b in range(N-R*a+1):
    cmod=(N-R*a-G*b)%B
    c=(N-R*a-G*b)//B
    if cmod==0 and  c>=0:
      ans+=1
    elif c<0:
      break

  if a>0:
    f(a-1)


R,G,B,N=list(map(int,input().split(" ")))

ans=0

f(N//R+1)

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

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

#N=len(sticks)
sticks = sorted(sticks1, reverse=True)
#sticks.sort(reverse = True)
count = 0
fj = fk = True
for i in range(0,N-2):
    for j in range(i+1,N-1):
        if not fj:
            fj=True
            break
        else:
            k=j+1
            while k<N:
                if sticks[i]<sticks[j]+sticks[k]:
                    count += 1
                    k += 1
                    continue
                else:
                    if j+1 == k :
                        fj = False
                    break
      
print(count)

### FIXED CODE ###

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

#N=len(sticks)
sticks = sorted(sticks1, reverse=True)
#sticks.sort(reverse = True)
count = 0
jmax = N-2
kmax = N-1
i=0
while i<N-2:
    j= i+1
    while j<jmax+1:
        k=kmax
        while j<k:
            #sticks[i]>sticks[j]>sticks[k]
            if sticks[i]<sticks[j]+sticks[k]:
                count += k-j
                kmax = k
                break
            else:
                k -= 1
                continue
        jmax = kmax-1
        j += 1
    kmax = N-1
    jmax = N-2
    i += 1
      
print(count)
### BUGGY CODE ###

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

A_set = set(A)
ans = 0

for a in A_set:
    count = A.count(a)
    if count >= a:
        ans += count - a
    else:
        ans += count

print(ans)


### FIXED CODE ###

import collections

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

B = collections.Counter(A)
ans = 0

for key, val in B.items():
    if val > key:
        ans += val - key
    elif val < key:
        ans += val 

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

import sys

x, y, z, k = map(int ,sys.stdin.readline().split())
a, b, c = (sorted(map(int, sys.stdin.readline().split())) for _ in range(3))

def main():
    res = sorted([a[i] + b[j] for i in range(x) for j in range(y)], reverse=True)
    res2 = sorted([res[i] + c[j] for i in range(min(k, x * y)) for j in range(z)], reverse=True)
    return res2[:k]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

### FIXED CODE ###

import sys
import numpy as np
from heapq import heappush, heappop


def main():
    x, y, z, K = map(int, sys.stdin.readline().split())
    abc = np.array(sys.stdin.read().split(), dtype=np.int64)
    a = abc[:x]
    b = abc[x:x + y]
    c = abc[x + y:x + y+ z]
    a = np.sort(a)[::-1]
    b = np.sort(b)[::-1]
    c = np.sort(c)[::-1]

    hq = []
    heappush(hq, (-(a[0]+b[0]+c[0]), 0, 0, 0))
    res = []
    added_before = set()
    # setで確認をO(1)でする
    added_before.add((0, 0, 0))

    for _ in range(K):
        sum_deli, i, j, k = heappop(hq)
        res.append(-sum_deli)
        if i < x - 1 and not (i+1, j, k) in added_before:
            heappush(hq, (-(a[i+1]+b[j]+c[k]), i+1, j, k))
            added_before.add((i+1, j, k))
        if j < y - 1 and not (i, j+1, k) in added_before:
            heappush(hq, (-(a[i]+b[j+1]+c[k]), i, j+1, k))
            added_before.add((i, j+1, k))
        if k < z - 1 and not (i, j, k+1) in added_before:
            heappush(hq, (-(a[i]+b[j]+c[k+1]), i, j, k+1))
            added_before.add((i, j, k+1))

    for s_deli in res:
        print(s_deli)

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

import bisect
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
T.sort()
for i in range(N):
    b = bisect.bisect_left(T,D[i])
    if b<M and D[i]==T[b]:
        T[b] = 0
        T.sort()
print("YES" if T.count(0)==M else "NO")

### FIXED CODE ###

from collections import defaultdict
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))
ans = "YES"
d = defaultdict(lambda : 0)
for i in range(N):
    d[D[i]] += 1
for j in range(M):
    if d[T[j]] == 0:
        ans = "NO"
        break
    d[T[j]] -= 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

@mt
def slv(N, S):
    dp = [[0] * (N+1) for _ in range(N+1)]

    for i in range(N-1, -1, -1):
        for j in range(N-1, -1, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
    
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans = max(ans, min(j-i, dp[i][j]))

    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

@mt
def slv(N, S):
    dp = [[0] * (N+1) for _ in range(N+1)]

    for i in range(N-1, -1, -1):
        for j in range(N-1, -1, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
    
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans = max(ans, min(j-i, dp[i][j]))

    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


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

import sys
input=sys.stdin.readline

def main():
    N,K = map(int, input().split())
    H = list(map(int, input().split()))

    inf = 10**4*N
    dp = [inf]*N
    dp[0] = 0
    for i in range(1, N):
        for j in range(K):
            x = i-(j+1)
            if x >= 0:
                dp[i] = min(dp[i], dp[x] + abs(H[i] - H[x]))
    print(dp[N-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    N,K = map(int, input().split())
    H = list(map(int, input().split()))

    inf = 10**4*N
    dp = [inf]*N
    dp[0] = 0
    for i,h in enumerate(H):
        if i == 0:
            continue
        m = max(0, i-K)
        # 普通なら j=i~m のループを回すが、高速化のためこうする（配列アクセスを減らす）
        dp[i] = min([dpj + abs(h - hj) for dpj, hj in zip(dp[m:i], H[m:i])])
    print(dp[N-1])

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

s = input().split()

n = int(s[0])
m = int(s[1])

ld = {}

for i in range(m):
    t = input().split()
    if int(t[0]) in ld:
        ld[int(t[0])].add(int(t[1]))
    else:
        ld[int(t[0])] = {int(t[1])}
    if int(t[1]) in ld:
        ld[int(t[1])].add(int(t[0]))
    else:
        ld[int(t[1])] = {int(t[0])}


if sum(ld.keys()) < int(((n + 1) * n ) / 2):
    print("No")
else:
    s1 = {1}
    s2 = set()
    count = 0
    mydict = {}

    while len(ld) > 0:
        s2.clear()
        for i in ld:
            if len(s1 & ld[i]) != 0:
                #s3 = list(s1 & ld[i])
                mydict.setdefault(i,list(s1 & ld[i])[0])
                s2.add(i)
        for i in s2:
            del ld[i]
        s1 = s2.copy()

    print("Yes")
    for i in range(2,n+1):
        print(mydict[i])


### FIXED CODE ###

import collections

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

coriddorList = [set() for i in range(n+1)]
deepList = [-1 for i in range(n+1)]


for i in range(m):
    a,b = list(map(int,input().split()))
    coriddorList[a].add(b)
    coriddorList[b].add(a)

checkList = [0] * (n + 1)
ansList = [0] * (n + 1)
checkList[1] = 1
q = collections.deque()
q.appendleft(1)

while len(q) > 0:
    value = q.pop()
    for k in coriddorList[value]:
        if checkList[k] == 0:
            checkList[k] = 1
            ansList[k] = value
            q.appendleft(k)

print("Yes")
for i in range(2,n+1):
    print(ansList[i])
### BUGGY CODE ###

from fractions import*
_,a=open(0)
*a,=map(int,a.split())
s=1
for t in a:s*=t//gcd(s,t)
print(sum(s//i for i in a)%(10**9+7))

### FIXED CODE ###

from fractions import*
from functools import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=reduce(lambda x,y:x//gcd(x,y)*y,a)%M
c=0
for i in a:
    c+=s*pow(i,M-2,M)
    c%=M
print(c)
### BUGGY CODE ###

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

ans = n
while(True):
  if abs(ans-k) < ans:
    ans = abs(ans-k)
  else:
    break

print(ans)

### FIXED CODE ###

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

d = n // k
ans = min(k-(n-k*d), (n-k*(d-1))-k)
print(ans)
### BUGGY CODE ###

s = input()

x = ''
if s[-1] == 'B':
    x = 'W'
else:
    x = 'B'

cnt = 0
while True:
    i = s.rfind(x)
    if i != -1:
        s = s[:i] + "".join([x]*(len(s[i:]) + 1))
        cnt += 1
        if x == 'B':
            x = 'W'
        else:
            x = 'B'
    else:
        break
print(cnt)



### FIXED CODE ###

s = input()

cnt = 0
tmp = s[0]
for i in range(1, len(s)):
    if s[i] != tmp:
        tmp = s[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

from collections import deque
S = input()
Q = int(input())

pre = ""
suf = ""

rev = 0
for i in range(Q):
    q = input().split()
    if len(q) == 1:
        rev = (rev + 1) % 2
    else:
        _, f, c = q
        if f == '1':
            if rev == 0:
                pre += c
            else:
                suf += c
        else:
            if rev == 0:
                suf += c
            else:
                pre += c


ans = pre[::-1] + S + suf
if rev == 0:
    print(ans)
else:
    print(ans[::-1])


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
S = input()
Q = int(input())
#S = "a"*100000
#Q = 200000
pre = ""
suf = ""

rev = 0
for i in range(Q):
    q = input().split()
    '''
    if i % 3 == 0:
        q = ('1')
    if i % 3 == 1:
        q = (2,'1','b')
    if i % 3 == 2:
        q = (2,'2','b')
        '''

    if len(q) == 1:
        rev = (rev + 1) % 2
    else:
        _, f, c = q
        f = f.decode()
        c = c.decode()
        if f == '1':
            if rev == 0:
                pre += c
            else:
                suf += c
        else:
            if rev == 0:
                suf += c
            else:
                pre += c

S = S.decode()[:-1]
ans = pre[::-1] + S + suf
if rev == 0:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

import itertools

n,m,x = map(int,input().split())
ans = 0
tmp = 10 ** 7
ca = [[0]*m for i in range(n)]

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

xx = list(itertools.permutations(ca))


for cax in xx:
    ans = 0
    a = [0 for i in range(m)]

    for _ in range(n):
        cost = cax[_][0]
        chk = 0
        for i in range(m):
            a[i] += cax[_][i+1]
            if a[i] < x:
                chk = 1

        ans += cost
        if chk == 0:
            if tmp > ans:
                tmp = ans
            break
if tmp == 10 ** 7:
    print(-1)
    exit()
print(tmp)

### FIXED CODE ###

def main():
    n,m,x = map(int,input().split())
    a = [[] for _ in range(n)]
    c = [0] * n

    INF = 10 ** 9
    ans = INF

    for i in range(n):
        ca = list(map(int,input().split()))
        c[i],a[i] = ca[0],ca[1:]

    for s in range(0,1<<n):
        smart = [0] * m
        cost = 0
        for i in range(n):
            if(s>>i) % 2 == 0:continue
            cost += c[i]
            for j in range(m):
                smart[j] += a[i][j]
        ok = True
        for i in range(m):
            if smart[i] < x:
                ok = False
        if ok:
            ans = min(ans,cost)
    if ans == INF:
        ans = -1
    
    print(ans)

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

import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect_left,bisect
def main():
    h, w, m = map(int,input().split()) 
    h_lis = [0] * h
    w_lis = [0] * w
    hw_lis = [] 
    for i in range(m):
        hh, ww = map(int,input().split())
        hh -= 1
        ww -= 1
        h_lis[hh] += 1
        w_lis[ww] += 1
        hw_lis.append((hh, ww))
    max_h = max(h_lis)
    max_w = max(w_lis)
    h_max_index = [i for i, h in enumerate(h_lis) if h == max_h]
    w_max_index = [i for i, w in enumerate(w_lis) if w == max_w]
    for h_i in h_max_index:
        for w_i in w_max_index:
            if not (h_i, w_i) in hw_lis:
                print(h_lis[h_i] + w_lis[w_i])
                sys.exit()
    else:
        print(h_lis[h_i] + w_lis[w_i] - 1)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect_left,bisect
def main():
    h, w, m = map(int,input().split()) 
    h_lis = [0] * (h+1)
    w_lis = [0] * (w+1)
    bombs = set([tuple(map(int,input().split())) for i in range(m)])
    for hh, ww in bombs:
        h_lis[hh] += 1
        w_lis[ww] += 1
    max_h = max(h_lis)
    max_w = max(w_lis)
    h_max_index = [i for i, h in enumerate(h_lis) if h == max_h]
    w_max_index = [i for i, w in enumerate(w_lis) if w == max_w]
    for h_i in h_max_index:
        for w_i in w_max_index:
            if not (h_i, w_i) in bombs:
                print(h_lis[h_i] + w_lis[w_i])
                sys.exit()
    else:
        print(h_lis[h_i] + w_lis[w_i] - 1)

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

import math 
import sys
from functools import reduce

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

def gcd_list(numbers):
  return reduce(math.gcd, numbers)

if gcd_list(A) > 1:
  print("not coprime")
  sys.exit()
  
union = set()
intersection = set()

visited = set()
A_set = set()

flag = False
MAX = 10**6
for a in A:
  #print(visited, a)
  if a in visited: 
    print("setwise coprime")
    sys.exit()
    flag = True 
    break
  b = a
  p = 2
  while p <= MAX and b > 1:
    if b % p == 0:
      q = p
      for q in range(p,MAX+1,p): #pの倍数を全てvisitedへ
        visited.add(q)     
    while b % p == 0:
      b = b // p
    p += 1

print("pairwise coprime")



"""
def raise_prime(B):
  n = len(B)
  if n == 1:
    
  C = B[0: n//2]
  D = B[n//2:n]
"""


  
  
"""
for a in A:
  p = 2
  while p <= N:
    if p not in visited:
      
      
    
  
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    union.add()
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
"""
  

  
  

### FIXED CODE ###

import math 
import sys
from functools import reduce

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

def gcd_list(numbers):
  return reduce(math.gcd, numbers)

if gcd_list(A) > 1:
  print("not coprime")
  sys.exit()
  
union = set()
intersection = set()

visited = set()
A_set = set()

flag = False
MAX = 10**6
lim = math.ceil(math.sqrt(MAX))
for a in A:
  #print(visited, a)
  if a in visited: 
    print("setwise coprime")
    sys.exit()
    flag = True 
    break
  b = a
  p = 2
  while p <= lim and b > 1:
    if p in visited: 
      p += 1
      continue
    if b % p == 0:
      q = p
      for q in range(p,MAX+1,p): #pの倍数を全てvisitedへ
        visited.add(q)     
    while b % p == 0:
      b = b // p
    p += 1
  if b > 1:
    q = b
    p = b
    for q in range(p,MAX+1,p): #pの倍数を全てvisitedへ
      visited.add(q) 
      
      

print("pairwise coprime")



"""
def raise_prime(B):
  n = len(B)
  if n == 1:
    
  C = B[0: n//2]
  D = B[n//2:n]
"""


  
  
"""
for a in A:
  p = 2
  while p <= N:
    if p not in visited:
      
      
    
  
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    union.add()
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
"""