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

from itertools import combinations
n = int(input())
s = input()

res = 0
for cl in combinations(range(2*n),n):
    sl = []
    for i in cl:
        sl.append(s[i])
    sr = []
    for i in range(2*n):
        if i in cl:
            continue
        sr.append(s[i])
    valid = True
    for i in range(n):
        if sl[i]!=sr[n-1-i]:
            valid = False
            break
    if valid:
        res += 1

print(res)

### FIXED CODE ###

from itertools import combinations
from collections import defaultdict
n = int(input())
s = input()

d = defaultdict(int)
left = set()
for r in range(n+1):
    for cl in combinations(range(n),r):
        sl = ""
        sr = ""
        for i in range(n):
            if i in cl:
                sl += s[i]
            else:
                sr += s[i]
        left.add(sl+","+sr)
        d[sl+","+sr] += 1

res = 0
for r in range(n+1):
    for cl in combinations(range(n,2*n),r):
        sl = ""
        sr = ""
        for i in range(n,2*n):
            if i in cl:
                sl = s[i] + sl
            else:
                sr = s[i] + sr
        if sr+","+sl in left:
            res += d[sr+","+sl]

print(res)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()

data=[]

for i in range(0,X):
  a=int(A[i])
  
  for j in range(0,Y):
    b=int(B[j])
    
    for k in range(0,Z):
      c=int(C[k])
      data.append(int(a+b+c))
    
data.sort()
data.reverse()

for l in range(K):
  print(data[l])


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
A.reverse()
B.reverse()
C.reverse()

data=[]

for i in range(0,X):
  if i+1>K: break
    
  for j in range(0,Y):
    if (i+1)*(j+1)>K: break
    
    for k in range(0,Z):
      if (i+1)*(j+1)*(k+1)>K: break
      data.append(int(A[i]+B[j]+C[k]))
        
    
data.sort()
data.reverse()

for l in range(K):
  print(data[l])
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [-1]*n
def dfs(s):
    if dp[s] >= 0:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    dp[s] = max(list((i+1+j) for i,j in enumerate(tmp)))
    return dp[s]

print(dfs(0))

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""
import bisect
n, m, qn = list(map(int, input().split()))

l= []
r = []
lr = []
p = []
q = []

for i in range(m):
    lri = list(map(int, input().split()))
    lr.append(lri)
    l.append(lri[0])
    r.append(lri[1])

lr.sort(key=lambda x:x[0])
l.sort()

for i in range(qn):
    pi, qi = list(map(int, input().split()))
    idxl =  bisect.bisect_left(l, pi)
    lrtmp2 = [z[1] for z in lr[idxl:]]
    lrtmp2.sort()
    idxr = bisect.bisect_right(lrtmp2, qi)
    print(idxr)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""

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

lr = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    li, ri = list(map(int, input().split()))
    lr[li][ri] += 1
    
for i in range(n+1):
    for j in range(n):
        lr[i][j+1] += lr[i][j]
for i in range(n+1):
    for j in range(n):
        lr[j+1][i] += lr[j][i]

for _ in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = lr[qi][qi] - lr[qi][pi-1] - lr[pi-1][qi] +lr[pi-1][pi-1]
    
    print(ans)
### BUGGY CODE ###

from collections import Counter
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
B = list(set(A[:]))
count = 0

for i in B:
    j = A.count(i)
    if j > i:
        count += j-i
    elif j < i:
        count += j
print(count)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
B = list(set(A[:]))
count = 0

B = Counter(A).most_common()
for k, v in B:

    if k < v:
        count += v-k
    elif k > v:
        count += v
print(count)
### BUGGY CODE ###

S = str(input())
Q = int(input())
t = 0

for _ in range(Q):
    A = list(input().split())
    if A[0] == "1":
        if t == 0:
            t = 1
        else:
            t = 0

    elif (A[1] == "1" and t == 0) or (A[1] == "2" and t == 1):
        S = A[2] + S
    else:
        S = S + A[2]

if t == 1:
    S = S[::-1]

print(S)

### FIXED CODE ###

from collections import deque

S = str(input())
Q = int(input())
t = 0

d = deque()
d.append(S)

for _ in range(Q):
    A = list(input().split())
    if A[0] == "1":
        if t == 0:
            t = 1
        else:
            t = 0

    elif (A[1] == "1" and t == 0) or (A[1] == "2" and t == 1):
        d.appendleft(A[2])
    else:
        d.append(A[2])

l = list(d)
ans = "".join(l)
if t == 1:
    ans = ans[::-1]
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
B.sort()
C = list(map(int, input().split()))
C.sort()
check = [0] * N
ans = 0
for i in range(N):
    check[i] = N - bisect.bisect_right(C,B[i])
for i in range(N):
    tmp = bisect.bisect_right(B,A[i])
    for k in range(tmp,N):
        ans += check[k]
print(ans)


### FIXED CODE ###

import bisect
N = int(input())
A_arr = list(map(int,input().split()))
A_arr.sort()
B_arr = list(map(int,input().split()))
B_arr.sort()
C_arr = list(map(int,input().split()))
ans = 0
check_array = [0] * N
for i in range(N):
    check_array[i] = check_array[i-1]+bisect.bisect_left(A_arr,B_arr[i])
for i in C_arr:
    B_index = bisect.bisect_left(B_arr,i)
    if B_index == 0:
        continue
    ans += check_array[B_index-1]
print(ans)
### BUGGY CODE ###

import sys
MX = 10**5
def main():
    input = sys.stdin.readline
    N = int(input())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    vL = [tuple(map(int, input().split())) for _ in range(Q)]

    H = min(N + 1, 1 << 9)
    Hb = (H - 1).bit_length()
    dp = [[0] * (MX + 1) for _ in range(H)]
    for i in range(1, H):
        v, w = items[i - 1]
        dpi = dp[i]
        dpip = dp[i >> 1]
        for j in range(w):
            dpi[j] = dpip[j]
        for j in range(w, MX + 1):
            dpi[j] = max(dpip[j], dpip[j - w] + v)
    for v, L in vL:
        if v < H:
            print(dp[v][L])
            continue
        ans = 0
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    iv, iw = items[node - 1]
                    value += iv
                    weight += iw
                    if weight > L:
                        break
                node >>= 1
                i >>= 1
            else:
                ans = max(ans, value + dp[node][L - weight])
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)

    H = min(N + 1, 1 << 10)
    dp = [None] * H
    dp[0] = [0] * (MX + 1)
    IV, IW = [], []
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i >> 1][:]
            dp[i] = dpi
            for j in range(MX, w - 1, -1):
                dpi[j] = max(dpi[j], dpi[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

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

N = int(input())
A = list(map(int,input().split()))
S = 0
for i in range(N):
    c = A.count(i)
    S += int(c*(c-1)/2)
for k in range(N):
    print(S - A.count(A[k]) + 1)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
CA = collections.Counter(A)
S = 0
for i in CA.values():
    S += i*(i-1)//2
for x in A:
    print(S - CA[x] + 1)
### BUGGY CODE ###

length, questions = [int(a) for a in input().split()]
strings = str(input())
for j in range(questions):
    start, end = [int(a) for a in input().split()]
    moji = strings[start - 1: end]
    counts = 0
    for k in range(len(moji) - 1):
        if moji[k] == 'A':
            if moji[k + 1] == 'C':
                counts += 1
    print(counts)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

N = int(input())
S = input()
res = 1000000
for i in range(N):
    Left = S[:i]
    Right = S[i+1:]
    res = min(res,Left.count('W')+Right.count('E'))
print(res)

### FIXED CODE ###

N = int(input())
S = input()
res = 1000000
prev_W = 0
prev_E = S.count('E')
for i in range(N):
    if i >= 1: prev_W += S[i-1].count('W')
    prev_E -= S[i].count('E')
    res = min(res,prev_W + prev_E)
print(res)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
ans = 0
minV = 10**15
cnt = 0

while True:
    if m <= 0:
        break
    a[-1] = a[-1] // 2
    a = sorted(a)
    m -= 1

ans = sum(a)
print(ans)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = []
#a = list(map(int, input().split()))
#a = list(reversed(sorted(a)))
#heapq.heapify(a)
for i in input().split():
    heapq.heappush(a, -int(i))

ans = 0

for i in range(len(a)):
    while True:
        if m <= 0:
            break

        maxV = heapq.heappop(a)
#        print('maxV: ' + str(maxV))
        heapq.heappush(a, -(-maxV // 2))
        m -= 1
        # print('m: ' + str(m))
        # print('a: ' + str(a))
ans = -sum(a)
print(ans)
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
m=0
for x in range(n+1):
    f=math.floor(a*x/b)-a*math.floor(x/b)
    if f>m:
        m=f
print(m)

### FIXED CODE ###

a,b,n=map(int,input().split())
import math
if n<b:
    m=math.floor(a*n/b)
else:
    e=b-1
    m=math.floor(a*e/b)
print(m)
### BUGGY CODE ###

import itertools
N, K = map(int, input().split())
seq = list(range(1,N + 1))
cand = list(itertools.product(seq, repeat=3))
ans = 0
for c in cand:
  ab = c[0] + c[1]
  bc = c[1] + c[2]
  ca = c[2] + c[0]
  if ab % K == 0 and bc % K == 0 and ca % K == 0:
    ans += 1
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
p1 = N // K
p2 = 0
if K % 2 == 0:
  p2 = (N + (K // 2)) // K
print(p1**3 + p2**3)
### BUGGY CODE ###

import bisect
N,M=map(int, input().split() )
A=list(map(int, input().split() ))
B=[0]*M
C=[0]*M
pos=A
for i in range(M):
  B[i],C[i]=map(int, input().split() )
  pos += B[i]*[C[i]]
  
pos.sort(reverse=True)
print(sum(pos[:N]))

### FIXED CODE ###

from collections import Counter

N,M = map(int, input().split() )
A   = list(map(int, input().split() ))
B   = [0]*M
C   = [0]*M
Cou = Counter(A)

for i in range(M):
  B[i],C[i]  = map(int, input().split() )
  Cou[C[i]] += B[i]
  
#print(Cou)  
ans=0
cnt=0
S=sorted(Cou,reverse=True)
#print(S)
for num in S:
  kosuu = min(Cou[num],N-cnt)
  cnt += kosuu
  ans += num*kosuu
  
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split(' ')))
B=[]
for i in range(N):
  if i%2==0:
    B.append(A[i])
  else:
    B = [A[i]] + B
#revert B when N%2==1
print(' '.join([str(b) for b in B])) if N%2==0 else print(' '.join([str(b) for b in B[::-1]]))

### FIXED CODE ###

N=int(input())
A=list(map(str, input().split(' ')))
even=A[0::2]
odd=A[1::2]
print(' '.join(even[::-1])+' '+' '.join(odd)) if N%2==1 else print(' '.join(odd[::-1])+' '+' '.join(even))
### BUGGY CODE ###

N,T  = map(int,input().split())
d = int(T / N)
if T % N == 0:
    print (d)


else:
    for i in range(d+1,0,-1):    
        if T % i ==0:
            print(i)
            break

### FIXED CODE ###

N,T  = list(map(int,input().split()))
d = int(T / N)
def ans():
    for i in range(d+1,0,-1):    
            if T % i ==0:
                print(i)
                break
if T % N == 0:
    print (d)
else:
    ans()
### BUGGY CODE ###

import heapq
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    heapq.heapify(A)
    C = set([i for i in range(N)])
    D = set([])
    if N == 10 ** 5 :
        parameter = 0.997
    else :
        parameter = 0.7
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = heapq.heappop(A)
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[1]+i] = a[0]
                D.add(a[1]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import collections

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

s.sort()

word = []
num = []
list = []
word.append(s[0])
num.append(1)

for i in range(1, len(s)):
    if s[i] != s[i-1]:
        word.append(s[i])
        num.append(1)
    else:
        num[len(word)-1] += 1

for i in range(len(word)):
    if num[i] == max(num):
        list.append(word[i])

list.sort()

for i in list:
    print(i)


### FIXED CODE ###

n = int(input())

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

list = []
maxnum = max(d.values())

for i in d:
    if d[i] == maxnum:
        list.append(i)
list.sort()
for i in list:
    print(i)
### BUGGY CODE ###

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

for i in range(1,n+1):
    print(li.count(i))

### FIXED CODE ###

import collections
n = int(input())
li = list(map(int, input().split()))
cnt = dict(collections.Counter(li))
for i in range(1,n+1):
    print(cnt.get(i, 0))
### BUGGY CODE ###

N = int(input())
li = []
for i in range(N):
    a = input()
    if a not in li:
        li.append(a)
print(len(li))

### FIXED CODE ###

N = int(input())
li = []
li = [input() for i in range(N)]
li2 = set(li)
print
print(len(li2))
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()
l = [list(map(int, input().split())) for _ in range(Q)]
for l,r in l:
  print(S[l-1:r].count("AC"))

### FIXED CODE ###

n,q= map(int,input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
import numpy as np
sn = list(np.cumsum([0] + [s[i:i++2]=="AC" for i in range(n-1)]))

for i,j in lr:
  i -= 1
  j -= 1
  print(sn[j] - sn[i])
### BUGGY CODE ###

import operator as op
from functools import reduce

m = 10**9 + 7

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom

x,y = map(int,input().split())

if max(x,y) > 2 *min(x,y):
    print(0)
elif (x+y) % 3 == 0:
    k = (x+y)//3
    n = (2*x-y)//3
    print(int(ncr(k,n)) % m)
else:
    print(0)

### FIXED CODE ###

def nCr(n, r, mod=10**9+7):
    n1, r = n+1, 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

x,y = map(int,input().split())

if max(x,y) > 2 *min(x,y):
    print(0)
elif (x+y) % 3 == 0:
    k = (x+y)//3
    n = (2*x-y)//3
    print(nCr(k,n))
else:
    print(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
s = input()
t = input()
ans = ''
slen = len(s)
tlen = len(t)

dp = [[0 for i in range(tlen+1)] for j in range(slen+1)]

for i in range(slen):
    for j in range(tlen):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
#ここまでで、DP配列が完成
#あとはDPの最後から遡る
i = slen
j = tlen
while (i>0 and j>0):
    if dp[i][j]==dp[i-1][j]:
        i -= 1
        continue
    elif dp[i][j]==dp[i][j-1]:
        j -= 1
        continue
    else:
        #print(i,j)
        ans = s[i-1] + ans
        i -= 1
        j -= 1
        
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input()
t = input()
ans = ''
slen = len(s)
tlen = len(t)

dp = [[0 for i in range(tlen+1)] for j in range(slen+1)]

for i in range(slen):
    for j in range(tlen):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
#ここまでで、DP配列が完成
#あとはDPの最後から遡る
i = slen
j = tlen
while (i>0 and j>0):
    if dp[i][j]==dp[i-1][j]:
        i -= 1
        continue
    elif dp[i][j]==dp[i][j-1]:
        j -= 1
        continue
    else:
        #print(i,j)
        ans = s[i-1] + ans
        i -= 1
        j -= 1
        
print(ans)
### BUGGY CODE ###

import itertools as itr
n, w = list(map(int, input().split()))
warr = [0]*(n+1)
varr = [0]*(n+1)
for i in range(n):
    wi, vi = list(map(int, input().split()))
    warr[i+1] = wi
    varr[i+1] = vi
    
dp = [[0]*(w+1) for _ in range(n+1)]

for i, j in itr.product(range(1,n+1), range(1,w+1)):
        jw = j-warr[i]
        if jw <0:
            dp[i][j] = dp[i-1][j]
            continue
        dp[i][j] = max(dp[i-1][jw] + varr[i], dp[i-1][j])
        
print(dp[n][w])

### FIXED CODE ###

import itertools as itr

n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)
for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
    
dp = [[0]*(wmax+1) for _ in range(n+1)]

for i, wi in itr.product(range(1, n+1), range(1, wmax+1)):
    if wi-w[i] >= 0:
        dp[i][wi] = max(dp[i-1][wi], dp[i-1][wi-w[i]]+v[i])
    else:
        dp[i][wi] = dp[i-1][wi]
            
print(dp[n][wmax])
### BUGGY CODE ###

MOD = 1000000007
# f(x) = f(x - 1) + f(x - 2)の場合のdp
def f_dp(x, a):
    dp = [0 for i in range(x + 1)]
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in range(2, x + 1):
        if i not in a:
            dp[i] = dp[i - 1] + dp[i -2]
    return dp[n] % MOD

if __name__ == "__main__":
    n, m = map(int, input().split())
    a = [int(input()) for i in range(m)]

    dp = f_dp(n, a)
    print(dp)

### FIXED CODE ###

MOD = 1000000007
# f(x) = f(x - 1) + f(x - 2)の場合のdp
def f_dp(x, a):
    dp = [0] * (x + 1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in range(2, x + 1):
        if i not in a:
            dp[i] = dp[i - 1] + dp[i -2]
    return dp[n] % MOD

if __name__ == "__main__":
    n, m = map(int, input().split())
    a = set([int(input()) for i in range(m)])

    dp = f_dp(n, a)
    print(dp)
### BUGGY CODE ###

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

ans = a_list[0]

for i in range(1, n):
    ans *= a_list[i]

if ans > 10**18:
    ans = -1


print(ans)

### FIXED CODE ###

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

ans = a_list[0]
count = a_list.count(0)

if count == 0:
    for i in range(1, n):
        ans *= a_list[i]
        if ans > 10**18:
            ans = -1
            break
else:
    ans = 0

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

import bisect
N, M = map(int, input().split())
Alist=list(map(int, input().split()))
Alist.sort()
for _ in range(M):
    b, c = map(int, input().split())
    index=bisect.bisect_left(Alist,c)
    if index < b:
        Alist=[c]*index+Alist[index:]
    else:
        Alist=Alist[b:index]+[c]*b+Alist[index:]
print(sum(Alist))

### FIXED CODE ###

N, M = map(int, input().split())
anlist=[]
for a in map(int, input().split()):
    anlist.append([1,a])
for _ in range(M):
    anlist.append(list(map(int, input().split())))
anlist=sorted(anlist, key=lambda x: x[1], reverse=True)
cnt = 0
ans = 0
for b, c in anlist:
    if cnt + b > N:
        ans += c*(N-cnt)
        break
    else:
        ans +=b*c
        cnt += b
print(ans)
### BUGGY CODE ###

from math import gcd

N = int(input())
A = list([int(x) for x in input().split()])

max_a = 10**6 + 1

before = 0
result = [0 for _ in range(max_a + 1)]

for i in A:
    before = gcd(before, i)
    result[i] += 1

is_pairwise = True
for i in range(2, max_a + 1):
    cnt = 0
    for j in range(i, max_a + 1, i):
        cnt += result[j]

    if cnt > 1:
        is_pairwise = False
        break

if is_pairwise:
    print('pairwise coprime')
    exit()

if before == 1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

from math import gcd


def main():
    N = int(input())
    A = list([int(x) for x in input().split()])

    max_a = max(A)

    before = 0
    result = [0 for _ in range(max_a + 1)]

    for i in A:
        before = gcd(before, i)
        result[i] += 1

    is_pairwise = True
    for i in range(2, max_a + 1):
        cnt = 0
        for j in range(i, max_a + 1, i):
            cnt += result[j]

        if cnt > 1:
            is_pairwise = False
            break

    if is_pairwise:
        print('pairwise coprime')
        exit()

    if before == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()