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

import heapq
N,M=map(int,input().split())
R=[]
G=[[] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    G[a].append((b,c))
    G[b].append((a,c))
    R.append((a,b,c))
Q=[[0]*N for i in range(N)]
INF=10**9
for i in range(N):
    stack=[]
    g=[INF for i in range(N)]
    g[i]=0
    for b,c in G[i]:
        heapq.heappush(stack,(g[i]+c,i,b))
    used=[[0]*N for i in range(N)]
    while(stack):
        c,a,b=heapq.heappop(stack)
        g[b]=min(g[b],c)
        used[a][b]=1
        used[b][a]=1
        for j in G[b]:
            if used[b][j[0]]:
                continue
            heapq.heappush(stack,(g[b]+j[1],b,j[0]))
    for j in range(i+1,N):
        Q[i][j]=g[j]
ans=0
for a,b,c in R:
    if b<a:
        a,b=b,a
    if Q[a][b]<c:
        ans+=1
print(ans)


### FIXED CODE ###

import heapq
N,M=map(int,input().split())
R=[]
G=[[] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    G[a].append((b,c))
    G[b].append((a,c))
    R.append((a,b,c))
Q=[[0]*N for i in range(N)]
INF=10**9
for i in range(N):
    stack=[]
    g=[INF for i in range(N)]
    g[i]=0
    n=1
    for b,c in G[i]:
        heapq.heappush(stack,(g[i]+c,i,b))
    used=[[0]*N for i in range(N)]
    while(stack):
        if n==N:
            break
        c,a,b=heapq.heappop(stack)
        g[b]=min(g[b],c)
        used[a][b]=1
        used[b][a]=1
        for j in G[b]:
            if used[b][j[0]] or g[j[0]]!=INF:
                continue
            heapq.heappush(stack,(g[b]+j[1],b,j[0]))
    for j in range(i+1,N):
        Q[i][j]=g[j]
ans=0
for a,b,c in R:
    if b<a:
        a,b=b,a
    if Q[a][b]<c:
        ans+=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    s = set()

    for i in range(n):
        s = s ^ {input()}

    print(len(s))


main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

import bisect

def main():
    n = int(input())
    s = []

    for i in range(n):
        a = int(input())
        i = bisect.bisect_left(s, a)
        if len(s) > i and s[i] == a:
            s.remove(a)
        else:
            s.insert(i, a)


    print(len(s))


main()
### BUGGY CODE ###

n, k = map(int, input().split())
while n > abs(n - k):
    n = abs(n - k)
print(n)

### FIXED CODE ###

n, k = map(int, input().split())
print(min(n%k, k-n%k))
### BUGGY CODE ###

a,b,c=[int(i) for i in input().split()]
count=0
while c > 0:
    c -= 1
    count += 1
    if b > 0:
        b -= 1
        count += 1
    elif a>0:
        a -= 1
    else:
        break
if b>0:
    count+=b
print(count)

### FIXED CODE ###

a,b,c=[int(i) for i in input().split()]
if c<b or c<=a+b:
    print(b+c)
else:
    print(a+b*2+1)
### BUGGY CODE ###

a = input()
sum = 0
for i in a:
  sum += int(a)
if sum % 9 == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a = int(input())
if a % 9 == 0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

N=int(input())

for i in range(1, N+1, 1):
    print(len([[x,y,z] for x in range(1,i+1,1) for y in range(1,i-x*x,1) for z in range(1,i-x*x-y*y-x*y,1) if x*x+y*y+z*z+x*y+y*z+z*x == i]))
 

### FIXED CODE ###

n = int(input())
 
ans = [0] * (n+1)
for x in range(1,110):
    for y in range(1,110):
        for z in range(1,110):
            tmp = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if tmp <= n:
                ans[tmp] += 1
 
for i in ans[1:]:
    print(i)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    # import numpy as np

    # def seachPrimeNum(N):
    #     max = int(np.sqrt(N))
    #     seachList = [i for i in range(2, N+1)]
    #     primeNum = []
    #     while seachList[0] <= max:
    #         primeNum.append(seachList[0])
    #         tmp = seachList[0]
    #         seachList = [i for i in seachList if i % tmp != 0]
    #     primeNum.extend(seachList)
    #     return primeNum

    def factorization(n):
        ret = set()
        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
                ret.add(i)
        if temp != 1:
            ret.add(temp)

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    # primes = set(seachPrimeNum(max(A)))

    s = factorization(A[0])

    ls = len(s)
    flag = True
    for x in A[1:]:
        g = gcd(g, x)
        if flag:
            for y in s:
                if x % y == 0:
                    flag = False
            s |= factorization(x)

    if flag:
        print("pairwise coprime")
    elif g == 1:
        print("setwise coprime")

    else:
        print("not coprime")


main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    M = max(A)
    X = [i for i in range(M+1)]
    S = [True for i in range(M+1)]
    S[0] = False
    S[1] = False

    for i in range(1, M+1):
        if S[i]:
            for j in range(i, M+1, i):
                if S[j]:
                    S[j] = False
                    X[j] = i
    flag = True
    s = set()
    ls = 0
    for x in A:
        tmp = set()
        while(X[x] != 1):
            tmp.add(X[x])
            x //= X[x]
        l = len(tmp)
        s |= tmp
        if len(s) == ls + l:
            ls += l
            continue
        else:
            flag = False
            break

    if flag:
        print("pairwise coprime")
    else:
        for x in A[1:]:
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()
### BUGGY CODE ###

import math

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
valid = [True] * len(A)
sqrt = A[len(A)-1] // 2
stop = -1
for i in range(len(A)):
    if A[i] > sqrt:
        stop = i
        break
    if valid[i] == False:
        continue
    for j in range(i+1, len(A)):
        if A[j] % A[i] == 0:
            valid[j] = False
        if A[j] == A[i]:
            valid[i] = False
if stop != -1:
    cur = A[stop]
    for i in range(stop+1, len(A)):
        if cur == A[i]:
            valid[i-1] = valid[i] = False
        else:
            cur = A[i]
print(valid.count(True))


### FIXED CODE ###

import math

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
maxA = A[len(A)-1]
valid = [True] * maxA

for i in range(len(A)):
    if valid[A[i]-1] == False:
        continue
    if i != 0 and A[i-1] == A[i]:
        valid[A[i]-1] = False
    else:
        for j in range(A[i]*2, maxA+1, A[i]):
            valid[j-1] = False

count = 0
for i in range(len(A)):
    if valid[A[i]-1] == True:
        count += 1
print(count)
### BUGGY CODE ###

def BFS(x):
  cnt=1
  v=deque([x])
  k=0
  zu[x]=k
  lis=[x]
  
  while len(v)>0:
    a=v.popleft()
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        cnt += 1
        lis.append(i)
          
  return lis

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]
zu=[ -1 for _ in range(N)] #訪問済みリスト

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)
    
size=[0]*N
pena=[0]*N
for i in range(N):
  if zu[i]==-1:
    kumi=BFS(i) #リスト
    for k in range(len(kumi)):
      size[kumi[k]]=len(kumi)
      for l in range(len(kumi)):
        if l==k:
          pass
        else:
          if (kumi[l] in bl[kumi[k]]) or (kumi[l] in fr[kumi[k]]):
            #print(kumi[k],kumi[l],bl[kumi[k]],fr[kumi[k]])
            pena[kumi[k]] += 1
#print(size)
#print(pena)
ans=[]
for i in range(N):
  ans.append(size[i]-pena[i]-1)
print(*ans)

### FIXED CODE ###

def BFS(x):
  cnt=1
  v=deque([x])
  k=0
  zu[x]=k
  lis=[x]
  roots[x]=x
  
  while len(v)>0:
    a=v.popleft()
    roots[a]=x
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        cnt += 1
        lis.append(i)

          
  return lis

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]
zu=[ -1 for _ in range(N)] #訪問済みリスト
roots= [ -1 for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)
fr_set= [set(fr[i]) for i in range(N)]
    
size=[0]*N
pena=[0]*N
for i in range(N):
  if zu[i]==-1:
    kumi=BFS(i) #リスト
    for k in range(len(kumi)):
      size[kumi[k]]=len(kumi)
      
      
ans=[0 for _ in range(N)]      
for i in range(N):
  ans[i]= size[i]-1 - len(fr[i])
  for j in bl[i]:
    if roots[j]==roots[i]:
      ans[i] -= 1      
      
print(*ans)
### BUGGY CODE ###


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

best=0
bestP=[0]*K
for i in range(N):
  if sum(P[i:i+K])>best:
    best=sum(P[i:i+K])
    bestP=P[i:i+K]
    

ans=0
for p in bestP:
  ans+=(p+1)/2
print(ans)

### FIXED CODE ###

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

#n面サイコロの出る目の期待値
def n_mean(n):
  return 0.5*(n+1)

Pmean=list(map(lambda x: n_mean(x), P))
Psum=[0]*N
Psum[0]=Pmean[0]
for i in range(1,N):
  Psum[i]=Psum[i-1]+Pmean[i]
#print(Psum)
ans=0
for i in range(N-K+1):
  if i==0:
    ans=Psum[K-1]
  else:
    #1~6 
    ans=max(ans, (Psum[i+K-1]-Psum[i-1]))
  
print(ans)
### BUGGY CODE ###

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*(N+1)
        self.b=1<<N.bit_length()-1
    def add(self,a,w):
        x=a
        while(x<=self.N):
            self.bit[x]+=w
            x+=x&-x
    def get(self,a):
        ret,x=0,a-1
        while(x>0):
            ret+=self.bit[x]
            x-=x&-x
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l) 
    def lowerbound(self,w):
        if w<=0:
            return 0
        x=0
        k=self.b
        while k>0:
            if x+k<=self.N and self.bit[x+k]<w:
                w-=self.bit[x+k]
                x+=k
            k//=2
        return x+1

N=int(input())
A=list(map(int,input().split()))
dic={}
for i in range(N):
    dic[A[i]]=i+1
bit=BIT(N)
ans=0
for i in range(1,N+1):
    d=dic[i]
    bit.add(d,1)
    c=bit.get(d+1)
    L=bit.lowerbound(c-1)
    R=bit.lowerbound(c+1)
    ans+=(R-d)*(d-L)*i
print(ans)


### FIXED CODE ###

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*(N+1)
        self.b=1<<N.bit_length()-1
    def add(self,a,w):
        x=a
        while(x<=self.N):
            self.bit[x]+=w
            x+=x&-x
    def get(self,a):
        ret,x=0,a-1
        while(x>0):
            ret+=self.bit[x]
            x-=x&-x
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l) 
    def lowerbound(self,w):
        if w<=0:
            return 0
        x=0
        k=self.b
        while k>0:
            if x+k<=self.N and self.bit[x+k]<w:
                w-=self.bit[x+k]
                x+=k
            k//=2
        return x+1

N=int(input())
A=list(map(int,input().split()))
dic={}
for i in range(N):
    dic[A[i]]=i+1
bit=BIT(N)
ans=0
for i in range(1,N+1):
    d=dic[i]
    bit.add(d,1)
    c=bit.get(d+1)
    L=bit.lowerbound(c-1)
    R=bit.lowerbound(c+1)
    ans+=(R-d)*(d-L)*i
print(ans)
### BUGGY CODE ###

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

b=[]
for i in range(n):
    b.append(a[i])
    b.reverse()
print(' '.join(map(str,b)))


### FIXED CODE ###

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

odd = []
even = []
for i in range(n):
    if i%2==0:
        even.append(a[i])
    else:
        odd.append(a[i])
if n%2!=0:
    b=even[::-1]+odd
else:
    b=odd[::-1]+even

print(' '.join(map(str,b)))
### BUGGY CODE ###

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

from collections import Counter
C = Counter(A)
#print(C)

X = [0]*(max(A)+1)
for i in A:
    j = i*2
    while j <= max(A):
        X[j] = 1
        j += i
#print(X)

ans = 0
for a in A:
    if C[a] == 1 and X[a] != 1:
        ans += 1
print(ans)


### FIXED CODE ###

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

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

def main():
    A.sort()
    S = set(A)
    m = max(A)
    X = [0]*(m+1)
    for i in range(1, m+1):
        j = i
        if j not in S:
            continue
        while j <= m:
            X[j] += 1
            j += i
    #print(X)

    D = {}
    for i in range(n):
        if A[i] not in D:
            D[A[i]] = 1
        else:
            D[A[i]] += 1

    ans = 0
    for a in A:
        if X[a] == 1 and D[a] == 1:
            ans += 1
    print(ans)

    #for i in range(m+1):
    #    if X[i] == 1:
            #print(i)

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

n=int(input())
a=[int(i) for i in input().split()]
mod=10**9+7
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    ans+=a[i]^a[j]
    ans%=mod
print(ans)

### FIXED CODE ###

mod=10**9+7
n=int(input())
a=[format(int(i),'b') for i in input().split()]
d0=[0]*60
d1=[0]*60
ans=0
for i in a:
  d=i[::-1]
  l=len(i)
  for j in range(60):
    if j<l and d[j]=='1':
      d1[j]+=1
    else:
      d0[j]+=1
for j in range(60):
  ans+=d0[j]*d1[j]*(2**j)
  ans%=mod
print(ans)
### BUGGY CODE ###

N = int(input())
S = []
num = []
num_list = []
count_list = []
num_list_counter = 0
count = 0

for i in range(N):
    S.append(input())
    num = 1
    num *= 2 ** S[i].count('a')
    num *= 3 ** S[i].count('b')
    num *= 5 ** S[i].count('c')
    num *= 7 ** S[i].count('d')
    num *= 11 ** S[i].count('e')
    num *= 13 ** S[i].count('f')
    num *= 17 ** S[i].count('g')
    num *= 19 ** S[i].count('h')
    num *= 23 ** S[i].count('i')
    num *= 29 ** S[i].count('j')
    num *= 31 ** S[i].count('k')
    num *= 37 ** S[i].count('l')
    num *= 41 ** S[i].count('m')
    num *= 43 ** S[i].count('n')
    num *= 47 ** S[i].count('o')
    num *= 73 ** S[i].count('p')
    num *= 79 ** S[i].count('q')
    num *= 83 ** S[i].count('r')
    num *= 89 ** S[i].count('s')
    num *= 97 ** S[i].count('t')
    num *= 101 ** S[i].count('u')
    num *= 103 ** S[i].count('v')
    num *= 107 ** S[i].count('w')
    num *= 109 ** S[i].count('x')
    num *= 113 ** S[i].count('y')
    num *= 127 ** S[i].count('z')

    if num_list_counter == 0:
        num_list.append(num)
        count_list.append(1)
        num_list_counter += 1
    else:
        judge = 0
        for j in range(num_list_counter):
            if num_list[j] == num:
                judge = 1
                count += count_list[j]
                count_list[j] += 1
        if judge == 0:
            num_list_counter += 1
            num_list.append(num)
            count_list.append(1)

print(count)


### FIXED CODE ###

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

dic = {}
for i in range(N):
    S.append(input())
    S[i] = sorted(S[i])
    S[i] = ''.join(S[i])
    if dic.setdefault(S[i], 0) > 0:
        count += dic[S[i]]
        dic[S[i]] += 1
    else:
        dic[S[i]] = 1
print(count)
### BUGGY CODE ###

def D():
    
    k=int(input())
    runrun=[i for i in range(1,10)]
    count=10
    runrun_count=9
            
    
    while runrun_count<k:
        
        len_count=0
        strcount=str(count)
        
        for i in range(1,len(strcount)):
            if abs(int(strcount[i])-int(strcount[i-1])) < 2 :
                len_count+=1
                continue
            else :
                break
        
        
        if len_count==len(strcount)-1:
            runrun.append(count)
            runrun_count+=1
            
        count+=1    
        
        
    print(runrun[k-1])
    
if __name__=='__main__':
    D()



### FIXED CODE ###

import queue


def D():
    
    k=int(input())
    q = queue.Queue()
    for i in range(1,10): q.put(i)
    
    for i in range(k):
        valu=q.get()
        if i==k-1: print(valu)
        
        if valu%10 != 0: q.put((10*valu)+(valu%10)-1)
        q.put((10*valu)+(valu%10))
        if valu%10 !=9: q.put((10*valu)+(valu%10)+1)
        
        
        
if __name__=='__main__':
    D()
### BUGGY CODE ###

N = int(input())
a = [''.join(sorted(list(input()))) for i in range(N)]
a_unique = set(a)
b = 0
for i in a_unique:
    c = a.count(i)
    b = b + c * (c - 1) / 2 
print(int(b))

### FIXED CODE ###

from collections import Counter

N = int(input())
a = [''.join(sorted(input())) for i in range(N)]
count = Counter(a).values()
b = 0
for i in count:
    b = b + i * (i-1)
b=int(b/2)
print(b)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

#input
N, M = map(int, input().split())
s = [0] * M
t = [0] * M
for i in range(M):
    s[i], t[i] = map(int, input().split())

#output
#（便宜的に地点から-1としておく）
u = [[]] * N
for v in s:
    u[v-1] = [t-1 for i, t in enumerate(t) if s[i] == v]

#地点vにたどり着く確率をp[v]とする。
p = [0] * N
p[0] = 1
for v in range(N):
    for i in range(v):
        if v in u[i]:
            p[v] += p[i]/len(u[i])

#期待値をゴールから逆順に求めていく。点vからゴールまでの移動距離の期待値をq[v]とする。
q = [0] * N
q[N-1] = 0
for v in reversed(range(N)):
    for i in u[v]:
        q[v] += (1 + q[i])/len(u[v])

v = [0] * M
for i in range(M):
    if len(u[(s[i]-1)]) > 1:
        v[i] = p[(s[i]-1)]*(q[(s[i]-1)]/(len(u[(s[i]-1)])-1) - (1 + q[(t[i]-1)])/(len(u[(s[i]-1)])-1))

print(q[0]+min(v))


### FIXED CODE ###

import sys
input = sys.stdin.readline

#input
N, M = map(int, input().split())
u = [[] for i in range(N-1)]
#（便宜的に地点から-1としておく）
for i in range(M):
    s, t = map(int, input().split())
    u[s-1].append(t-1)

#output
#地点vにたどり着く確率をp[v]とする。
p = [0] * N
p[0] = 1
for x, y in enumerate(u):
    for z in y:
        p[z] += p[x]/len(y)

#期待値をゴールから逆順に求めていく。点vからゴールまでの移動距離の期待値をq[v]とする。
q = [0] * N
q[N-1] = 0
for x, y in list(enumerate(u))[::-1]:
    q[x] = sum(q[z] for z in y)/len(y) + 1

v = [0] * N
for i in range(N-1):
    a = len(u[i])
    if a > 1:
        b = max(q[c] for c in u[i])
        v[i] = p[i]*(q[i] - (1+b))/(a-1)

print(q[0]+min(v))
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))
a = 1
if 0 in li:
    print(0)
    quit()
else:
    for x in li:
        a *= x
    if a > 10**18:
        print(-1)
        quit()
    print(a)

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque
from pprint import pprint
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

graph = [[0 for _ in range(N)] for _ in range(N)]
visited = [0 for _ in range(N)]

for x,y in xy:
    graph[x-1][y-1] = 1
    graph[y-1][x-1] = 1

def dfs(v):
    que = deque()
    vis_list = []
    visited[v] = 1
    vis_list.append(v)
    que.append(v)
    while len(que) > 0:
        i = que.pop()   #深さ優先探索
        # i = que.popleft() #幅優先探索
        for n in range(N):
            if graph[i][n] == 1 and visited[n] == 0:
                visited[n] = 1
                vis_list.append(n)
                que.append(n)

    return vis_list

grps = []
for i in range(N):
    if visited[i] == 0:
        grps.append(dfs(i))

ans = 0
for g_list in grps:

    if len(g_list) == 1:
        if g_list[0] == p[g_list[0]]-1:
            ans += 1
    else:
        tmp = set([])
        for i in g_list:
            tmp.add(p[i]-1)
        ans += len( set(g_list) & tmp)

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque, defaultdict
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

graph = defaultdict(set)
visited = [False for _ in range(N)]

for x,y in xy:
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

def dfs(v):
    que = deque()
    vis_list = []
    visited[v] = True
    vis_list.append(v)
    que.append(v)
    while len(que) > 0:
        i = que.pop()   #深さ優先探索
        # i = que.popleft() #幅優先探索
        for n in list(graph[i]):
            if visited[n] == False:
                visited[n] = True
                vis_list.append(n)
                que.append(n)

    return vis_list

grps = []
for i in range(N):
    if visited[i] == False:
        grps.append(dfs(i))

ans = 0
for g_list in grps:
    if len(g_list) == 1:
        if g_list[0] == p[g_list[0]]-1:
            ans += 1
    else:
        tmp = set([])
        for i in g_list:
            tmp.add(p[i]-1)
        ans += len( set(g_list) & tmp)

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

#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

from math import gcd
import math
acc = a[0]
LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
for i in range(2,LIMIT+1):
    if minPrime[i] == 0:
        for j in range(i,LIMIT+1,i):
            if minPrime[j] == 0:
                minPrime[j] = i

# def factrial(N):
#     ret = []
#     while minPrime[N] != N:
#         ret.append(minPrime[N])
#         N = N//minPrime[N]
#     if N != 1:
#         ret.append(N)
#     return ret

def factrial(N):
    ret = set()
    while minPrime[N] != N:
        ret.add(minPrime[N])
        N = N//minPrime[N]
    if N != 1:
        ret.add(N)
    return ret

for i in range(N):
    acc = gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

pairwise = True
p = set() #all prime
for e in a:
    if not pairwise:
        break
    #f = set(factrial(e))
    f = factrial(e)
    if p & f != set():
        pairwise = False
    p = p | f

if pairwise:
    print("pairwise coprime")
else:
    print("setwise coprime")
# for s:
#     acc = math.gcd(acc,a[i])
# if acc != 1:
#     print("not coprime")
#     exit()
# print("pairwise coprime")
# for i in range(N):
#     for j in range(i+1,N):
#         b = gcd(a[i],a[j])
#         if b != 1:
#             print("setwise coprime")
#             exit()
# if pairwise == True:
#     print("pairwise coprime")
# else:
#     print("not coprime")


### FIXED CODE ###

import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)
 
        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i
 
    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num
 
    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret
 
sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])
 
for i in a:
    if not pc:
        break
    asf = sofe.factorization(i)
    
    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")