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

import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
for _ in range(m):
    b,c = map(int,input().split())
    if min(A) >= c:
        pass
    else:
        A.sort()
        index = bisect.bisect_left(A,c)
        if b <= index:
            for i in range(b):
                A[i] = c
        else:
            for i in range(index):
                A[i] = c
print(sum(A))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

minA = A[0]
Query = []
for _ in range(m):
    b,c = map(int,input().split())
    if c > minA:
        Query.append([b,c])
Query = sorted(Query, key=lambda x:(x[1], x[0]), reverse=True)

ans = 0
index = 0
for b,c in Query:
    if index >= n:
        break
    #print("----")
    cnt = 0
    Flag = True
    while Flag:
        #print(A,b,c,index)
        if A[index] < c:
            A[index] = c
            cnt += 1
            index += 1
            if (cnt >= b) or (index >= n):
                Flag = False
        else:
            Flag = False
    '''
    #A.sort()
    if A[0] >= c:
        break
    else:
        index = min(bisect.bisect_left(A,c),b)
        if index > len(A):
            ans += c * len(A)
            break
        else:
            ans += c * index
            A = A[index:]
    print(A)
    '''
print(sum(A))
### BUGGY CODE ###

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)
for _ in range(m):
    _max = max(arr)
    i = arr.index(_max)
    arr[i] = _max // 2
print(sum(arr))

### FIXED CODE ###

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)

b = arr[0] // 2
i = 0
while True:
    if m == 0:
        break
    if b <= arr[i]:
        arr[i] = arr[i] // 2
        m -= 1
    else:
        arr = sorted(arr, reverse=True)
        i = 0
        b = arr[0] // 2
        continue
    if i < n-1:
        i += 1
    else:
        i = 0

print(sum(arr))
### BUGGY CODE ###

def solve(string):
    n, m, *ab = map(int, string.split())
    base = n * (n - 1) // 2
    ans = [base]
    cluster = []
    ab = ab[::-1]
    for _b, _a in zip(ab[:2 * m - 2:2], ab[1:2 * m - 2:2]):
        ins = [_a in _c or _b in _c for _c in cluster]
        if not any(ins):
            cluster.append([_a, _b])
        else:
            tmp = [_a, _b]
            for f, _c in zip(ins, cluster):
                tmp += _c if f else []
            cluster = [_c for f, _c in zip(ins, cluster) if not f]
            cluster.append(list(set(tmp)))
        ans.append(base - sum([len(_c) * (len(_c) - 1) // 2 for _c in cluster]))
    return "\n".join([str(_ans) for _ans in ans[::-1]])


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))


### FIXED CODE ###

class uf:

    def __init__(self, n):
        self.table = [-1] * (n + 1)
        self.size = [1] * (n + 1)

    def merge(self, r1, r2):
        self.table[r1] = r2
        self.size[r2] += self.size[r1]
        self.size[r1] = 0

    def find_root(self, k):
        path = []
        curr = k
        while self.table[curr] != -1:
            path.append(curr)
            curr = self.table[curr]
        return curr, path

    def defrag(self, r, p):
        for i in p:
            self.table[i] = r

    def defrag_all(self):
        for i in range(len(self.table)):
            if self.table[i] == -1:
                continue
            self.defrag(*self.find_root(i))

    def in_same_group(self, k1, k2):
        r1, p1 = self.find_root(k1)
        r2, p2 = self.find_root(k2)
        if r1 == r2:
            self.defrag(r1, p1 + p2)
        else:
            self.defrag(r1, p1)
            self.defrag(r2, p2)
        return r1 == r2


def cul_comb(n):
    return n * (n - 1) // 2


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = ab[::-1]
    ans = [cul_comb(n)]
    table = uf(n)
    for _b, _a in zip(ab[:2 * m - 2:2], ab[1:2 * m - 2:2]):
        if table.in_same_group(_b, _a):
            ans.append(ans[-1])
        else:
            r_a, p_a = table.find_root(_a)
            r_b, p_b = table.find_root(_b)
            ans.append(ans[-1] - table.size[r_a] * table.size[r_b])
            table.merge(r_a, r_b)
            table.defrag(r_b, p_a)
            table.defrag(r_b, p_b)
    return "\n".join([str(a) for a in ans[::-1]])


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for i in range(M)]

minA = min(A)
C = [[j]*i for i,j in BC if j > minA]
for i in range(len(C)):
    A = A[:N]
    if C[i][0] > min(A):
        A.extend(C[i])
        A.sort(reverse=True)


print(sum(A[:N]))


### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for i in range(M)]

A.sort()
BC.sort(key=lambda x: x[1], reverse=True)

idx = 0
for b, c in BC:
  for j in range(idx, min(N, idx + b)):
    if A[j] < c:
      A[j] = c
  idx += b
print(sum(A))
### BUGGY CODE ###

#####segfunc######
def segfunc(x,y):
    return x|y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = set()

#num:n以上の最小の2のべき乗
n=int(input())
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
s=input()
init([{i}for i in s])
q=int(input())
for _ in range(q):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,{c})
  else:
    _,l,r=quer
    print(len(query(int(l)-1,int(r))))


### FIXED CODE ###

import sys;input=sys.stdin.readline
n=int(input())
s=input()
num=2**(n-1).bit_length()
def segfunc(x,y):return x|y
seg=[0]*(2*num-1)
for i in range(n):seg[i+num-1]=2**(ord(s[i])-97)
for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
def update(i,x):
  i+=num-1;seg[i]=x
  while i:i=(i-1)//2;seg[i]=segfunc(seg[i*2+1],seg[i*2+2])
def query(l,r):
  l+=num-1;r+=num-1
  if l==r:return seg[l]
  s=seg[l];l+=1
  while r-l>1:
    if ~l%2:s=segfunc(seg[l],s)
    if r%2:s=segfunc(seg[r],s);r-=1
    l//=2;r=(r-1)//2
  if l==r:return segfunc(s,seg[l])
  return segfunc(s,segfunc(seg[l],seg[r]))
for _ in range(int(input())):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,2**(ord(c)-97))
  else:
    _,l,r=quer
    print(sum(map(int,bin(query(int(l)-1,int(r)-1))[2:])))
### BUGGY CODE ###

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


MOD = 10 ** 9 + 7


def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


def nCr(n, r, p=MOD):
    # Modulo binomial coefficients
    num = 1
    den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return num * modInverse(den, p) % p


if N - 1 < K:
    # Any combo is achievable so this is stars and bars
    # N people into N rooms, which means N - 1 dividers
    stars = N
    bars = N - 1
    print(nCr(stars + bars, bars))
else:
    tot = 0
    # Group by number of empty rooms
    # With K moves there can only be at most K empty rooms
    # Max of N - 1 empty rooms in general
    assert K + 1 <= N
    for numEmpty in range(K + 1):
        numNonEmpty = N - numEmpty
        stars = numEmpty  # Everyone moving into an occupied room
        bars = numNonEmpty - 1
        tot += nCr(stars + bars, bars) * nCr(N, numEmpty)
    print(tot % MOD)


### FIXED CODE ###

from functools import lru_cache


CHECK = False

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

MOD = 10 ** 9 + 7


@lru_cache(maxsize=None)
def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


if N - 1 <= K or CHECK:
    fact = [1]
    for i in range(1, 2 * N + 1):
        fact.append((fact[-1] * i) % MOD)

    def nCr(n, r, p=MOD):
        # Modulo binomial coefficients
        return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], p)) % p


if N - 1 <= K:
    # Any combo is achievable so this is stars and bars
    # N people into N rooms, which means N - 1 dividers
    stars = N
    bars = N - 1
    print(nCr(stars + bars, bars))
else:
    # Group by number of empty rooms
    # With K moves there can only be at most K empty rooms
    # Max of N - 1 empty rooms in general
    assert K + 1 < N
    tot = 0
    comb1 = 1
    comb2 = 1
    for numEmpty in range(K + 1):
        way3 = comb1 * comb2
        if CHECK:
            numNonEmpty = N - numEmpty
            stars = numEmpty  # Everyone moving into an occupied room
            bars = numNonEmpty - 1  # Number of dividers
            way1 = nCr(stars + bars, bars) * nCr(N, numEmpty)

            way2 = nCr(N, numEmpty) * nCr(N - 1, numEmpty)

            assert way1 % MOD == way2 % MOD == way3 % MOD
        tot += way3

        j = numEmpty + 1
        invJ = modInverse(j, MOD)
        comb1 = (N + 1 - j) * comb1 * invJ % MOD
        comb2 = (N - j) * comb2 * invJ % MOD
    print(tot % MOD)
### BUGGY CODE ###

from networkx import*
def main():
    g=Graph()
    for a in[*open(0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,b+.5)
    x=0
    for c in connected_components(g):
        s=g.subgraph(c)
        a,b=map(len,bipartite.sets(s))
        x+=a*b-s.size()
    print(x)
main()

### FIXED CODE ###

class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
n,*z=map(int,open(0).read().split())
u=UnionFind(10**5*2+1)
for x,y in zip(*[iter(z)]*2):
    u.unite(x,10**5+y)
d=[[0,set(),set()]for _ in range(10**5*2+1)]
for x,y in zip(*[iter(z)]*2):
    t=d[u.root(x)]
    t[0]+=1
    t[1].add(x)
    t[2].add(y)
print(sum(len(x)*len(y)-a for a,x,y in d))
### BUGGY CODE ###

import math
N,M = list(map(int,input().split()))
a = [-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
b = []
c = []
fac_N =[1]
for i in range(M+1):
    b.append(a[i+1]-a[i]-2)
for i in range(1,max(b)+1):
    fac_N.append(fac_N[-1]*i)
 
 
for i in range(len(b)):
    counter= 0
    for num2 in range(b[i]//2+1):
        bi = b[i]-2*num2
        counter += fac_N[num2+bi]//fac_N[num2]//fac_N[bi]%1000000007
    c.append(counter)
ans = 1
for i in range(len(c)):
    ans *= c[i]%1000000007
print(ans%1000000007)


### FIXED CODE ###

n,m = map(int,input().split())
a = [ int(input()) for _ in range(m)]
M=10**9+7
lis = [1] + [0]*n

for i in a:
  lis[i]=-1
lis[1] += 1
for i in range(n-1):
  if lis[i+2]<0:
    lis[i+2]= 0
  else:
    lis[i+2] = (lis[i+1] + lis[i])%M
print(lis[n])
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

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

pows = [1] * N
for i in range(1, N):
    pows[i] = (pows[i - 1] * 2) % MOD

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    # add sub-tree on the parent side
    if p != -1:
        subs.append(N - res)
    now = pows[N - 1] - 1 # N - 1 means that it chooses freelye other than v
    for sub in subs:
        now -= pows[sub] - 1
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

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

pows = [1] * N
for i in range(1, N):
    pows[i] = (pows[i - 1] * 2) % MOD

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    # add sub-tree on the parent side
    if p != -1:
        subs.append(N - res)
    now = pows[N - 1] - 1 # N - 1 means that it chooses freelye other than v
    for sub in subs:
        now -= pows[sub] - 1
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)
### BUGGY CODE ###

import math
n, m = [int(i) for i in input().split()]
p = [int(input()) for i in range(m)]

a = []
a.append(1)
if 1 in p:
    a.append(0)
else:
    a.append(1)
for i in range(2, n + 1):
    if i in p:
        a.append(0)
    else:
        a.append(a[i - 2] + a[i - 1])
    
print(a[n] % 1000000007)

### FIXED CODE ###

import math
n, m = [int(i) for i in input().split()]
p = [0 for i in range(n + 1)]
for _ in range(m):
    p[int(input())] = 1
    
a = []
a.append(1)
if p[1] == 1:
    a.append(0)
else:
    a.append(1)
for i in range(2, n + 1):
    if p[i] == 1:
        a.append(0)
    else:
        a.append((a[i - 2] + a[i - 1]) % 1000000007)
    
print(a[n])
### BUGGY CODE ###

#array内で積がx未満になるペアの数
def syakutori_pos(x,array):
    n=len(array)
    res=0
    j=n-1
    for i in range(n):
        tmp=0
#         j=n-1
        y=-(-x//array[i])
        while j!=-1:
            
            if array[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if array[i]**2<x:
            tmp-=1
        res+=tmp
    res=res//2
    return res



#array内で積がx未満になるペアの数
def syakutori_neg(x,array_pos,array_neg):
    n_pos=len(array_pos)
    n_neg=len(array_neg)
    y=x//array_neg
#     print(A_pos,y)
    res=0
    i=0
    j=n_pos-1
    for z in reversed(y):
        while(j!=-1):
            if z<array_pos[j]:
                j-=1
            else:
                break
#         print(z,j+1)
        res+=j+1
    return n_pos*n_neg-res


import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg.copy())
n_post=(len(A_pos)*(len(A_pos)-1)//2)+(len(A_neg)*(len(A_neg)-1))//2
n_zero=len(A[A==0])*(len(A_pos)+len(A_neg))+len(A[A==0])*(len(A[A==0])-1)//2
n_neg=len(A_pos)*len(A_neg)

def syakutori(x):
    if x>0:
        return syakutori_pos(x,A_pos)+syakutori_pos(x,A_neg2)+n_neg+n_zero
    elif x==0:
        return n_neg
    else:
        return syakutori_neg(x,A_pos,A_neg)




r=10**18
l=-10**18
while(r-l>1):
    mid=(l+r)//2
    z=syakutori(mid)
#     z= count_pair(mid)
#     print(l,r)
    if z < K:
        l=mid
    else:
        r=mid
print(l)

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=-A_neg[::-1]
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)
### BUGGY CODE ###

'''
Created on 2020/08/29

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  A,B,N=map(int,pin().split())
  t=int(B/A)
  ans=0
  for x in range(t,N+1):
    ans=max(ans,int(A*x/B)-A*int(x/B))
  print(ans)
  return 
main()

### FIXED CODE ###

'''
Created on 2020/08/29

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  A,B,N=map(int,pin().split())
  x=min(B-1,N)
  ans=int(A*x/B)-A*int(x/B)
  print(ans)
  return
main()
#解説AC
### BUGGY CODE ###

def main():
    MOD = 10**9 + 7
    A_UB = 2**60  # upper bound
    MAX_BIN_LENGTH = len('{:b}'.format(A_UB))
    BIN_FORMAT = '{{:0{}b}}'.format(MAX_BIN_LENGTH)

    N = int(input())
    A = list(map(int, input().split(' ')))
    rev_bin_A = [BIN_FORMAT.format(a)[::-1] for a in A]

    bit_coef = [0 for _ in range(MAX_BIN_LENGTH)]
    for b in range(MAX_BIN_LENGTH):
        bit_list = [int(rev_bin_a[b]) for rev_bin_a in rev_bin_A]
        one_num = sum(bit_list)
        zero_num = N - one_num
        bit_coef[b] = one_num * zero_num

    answer = 0
    for b in range(MAX_BIN_LENGTH):
        pow_2 = (2**b) % MOD
        answer += (pow_2 * bit_coef[b]) % MOD
    answer %= MOD
    print(answer)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np


def main():
    MOD = 10**9 + 7
    A_UB = 2**60  # upper bound
    MAX_BIN_LENGTH = len('{:b}'.format(A_UB))

    N = int(input())
    A = list(map(int, input().split(' ')))
    A = np.array(A)

    bit = 1
    answer = 0
    for b in range(MAX_BIN_LENGTH):
        a_bits = A & 1
        one_num = np.count_nonzero(a_bits)
        answer += (one_num * (N - one_num) * bit) % MOD
        answer %= MOD
        bit *= 2
        bit %= MOD
        A >>= 1
    print(answer)


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

def solve(n, k, al):
    m = -1
    for x in range(k+1):
        s = 0
        for e in al:
            s += x ^ e
        if m < s:
            m = s
    print(m)

def main():
    n, k = map(int, input().split())
    al = list(map(int, input().split()))
    solve(n, k, al)

main()    

### FIXED CODE ###

def solve(n, k, al):
    bin_k = format(k,"b")
    len_k = len(bin_k)
    
    # search
    answer = 0
    enable_one = False
    zero_limit = n // 2
    for i in range(len_k,-1,-1):
        bit = 1 << i
        answer = answer << 1
        if enable_one or ((k & bit) != 0):
            # 0 or 1 case
            zero_count = 0
            for e in al:
                if (e & bit) == 0:
                    zero_count += 1
            if zero_count > zero_limit:
                answer += 1
            else:
                enable_one = True
    # print(answer)

    s = 0
    for e in al:
        s = s + (answer ^ e)
    print(s)

def main():
    n, k = map(int, input().split())
    al = list(map(int, input().split()))
    solve(n, k, al)

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

def LCS(S, T):
    lenS, lenT = len(S), len(T)
    lcs_set = [[[] for j in range(lenT + 1)] for i in range(lenS + 1)]
    for i in range(0, lenS + 1):
        lcs_set[i][0].append("")
    for j in range(1, lenT + 1):
        lcs_set[0][j].append("")
    for i in range(1, lenS + 1):
        for j in range(1, lenT + 1):
            if S[i-1] == T[j-1]:
                for x in lcs_set[i-1][j-1]:
                    lcs_set[i][j].append(x + S[i-1])
            else:
                if len(lcs_set[i-1][j][0]) < len(lcs_set[i][j-1][0]):
                    lcs_set[i][j] = lcs_set[i][j-1]
                elif len(lcs_set[i-1][j][0]) > len(lcs_set[i][j-1][0]):
                    lcs_set[i][j] = lcs_set[i-1][j]
                else:
                    lcs_set[i][j] = lcs_set[i-1][j] + lcs_set[i][j-1]
            lcs_set[i][j] = list(set(lcs_set[i][j]))
    return lcs_set[lenS][lenT]

print(LCS(input(), input())[0])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

s, t = input(), input()
ls, lt = len(s), len(t)
dp = [[0] * (lt+1) for i in range(ls+1)]
for i, x in enumerate(s, 1):
    for j, y in enumerate(t, 1):
        if x == y:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
ans = ''
while 0 < dp[i][j]:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        i -= 1
        j -= 1
        ans += s[i]
print(ans[::-1])
### BUGGY CODE ###

from functools import reduce
from math import gcd

N=int(input())
A=list(map(int, input().split()))
c=10**6+1
C=[0]*c
f=1
for i in A:
    C[i]+=1

for i in range(2,c):
    cnt=0
    for j in range(i,c,i):
        cnt+=C[j]
    if cnt>1:
        f=0


if f==1:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')

### FIXED CODE ###

from functools import reduce
from math import gcd

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

c=max(A)+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>=c  or j>D[i] :
           break
        D[i*j]=j
f=0
for i in A:
    if i==1:
        continue
    temp=i
    while temp!=1:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp2=D[temp]
        while temp%temp2==0 and temp>=temp2:
            temp=temp//temp2
    if f==1:
        break
        


if max(div)<=1 and f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')