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

from bisect import bisect_right

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

def calc(x):
    tmp = 0
    for a in A:
        tmp += N - bisect_right(A, x - a - 0.5)
    return tmp

l = 0
r = 3 * 10 ** 5
while r - l > 1:
    mid = (l + r) // 2
    if calc(mid) >= M:
        l = mid
    else:
        r = mid

B = [0] * (N + 1)
for i in range(N):
    B[i + 1] = B[i] + A[i]

ans = 0
for a in A:
    tmp = bisect_right(A, r - a - 0.5)
    M -= (N - tmp)
    ans += a * (N - tmp) + (B[-1] - B[tmp])

ans += M * l
print (ans)

### FIXED CODE ###

from bisect import bisect_right

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

def calc(m): #m以下の組が何通りあるかを数える
    count = 0 #組数を数える
    for a in A:
        b = m - a #b以上のは含める
        count += N - bisect_right(A, b - 0.5)
    return count

l = 0 
r = 3 * 10 ** 5

while r - l > 1:
    mid = (l + r) // 2
    if calc(mid) >= M: #合計mid以上の組と手を繋ぐとしたとき、とM回以上握手できる
        l = mid
    else:
        r = mid

B = [0] * (N + 1)
for i in range(N):
    B[i + 1] = B[i] + A[i]

# print(B)
flag = False
for i in range(mid + 3, -1, -1):
    if calc(i) < M:
        flag = False
    else: #初めて手をにぎる回数がM回を下回ったとき
        break

i += 1 #合計この値までは全て使う、残り回数を調整
ans = 0
for a in A:
    b = i - a
    tmp = bisect_right(A, b - 0.5)
    M -= (N - tmp) #使った数
    ans += a * (N - tmp) + (B[-1] - B[tmp])

ans += M * (i - 1)
print (ans)
### BUGGY CODE ###


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

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

def calc(l):
    count = 0
    for i in range(len(l)-1):
        count += abs(l[i]-l[i+1])

    return count

# 0 3 5 -1 0 みたいに
L = [0] + A + [0]
for i in range(1, N+1):
    l = L[0:i] + L[i+1:]
    print(calc(l))


### FIXED CODE ###


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

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

def calc(l):
    count = 0
    for i in range(len(l)-1):
        count += abs(l[i]-l[i+1])

    return count

# 0 3 5 -1 0 みたいに
L = [0] + A + [0]
max_L = calc(L)
#print(max_L)

# 左右引いて、左右通しで計算すればいい
for i in range(1, N+1):
    diff_minus = abs(L[i-1]-L[i])+abs(L[i]-L[i+1])
    diff_plus = abs(L[i-1]-L[i+1])
    print(max_L-diff_minus+diff_plus)
### BUGGY CODE ###

#

import sys
input=sys.stdin.readline

kl=set()

            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    kl=set()
    p=[{} for i in range(N)]
    for j in range(N):
        n=A[j]
        ret={}
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                ret[i]=cnt
                kl.add(i)
        if n!=1:
            ret[int(n)]=1
            kl.add(int(n))
        p[j]=ret
    lcm=1
    for i in kl:
        maxipow=0
        for j in range(N):
            maxipow=max(maxipow,p[j].get(i,0))
        lcm*=i**maxipow
    MOD=10**9+7
    lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
from fractions import gcd
input=sys.stdin.readline

def main():
    MOD=10**9+7
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    l=(A[0]*A[1])//gcd(A[0],A[1])
    for i in range(2,N):
        l=(l*A[i])//gcd(A[i],l-A[i])
    l%=MOD
    ans=0
    for i in range(N):
        ans+=l*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

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

dp=[float('inf') for _ in range(n)]
dp[0]=0
for i in range(n):
  for j in range(1,k+1):
    if i+j<n:
      dp[i+j]=min(dp[i+j],dp[i]+abs(H[i+j]-H[i]))
print(dp[-1])

### FIXED CODE ###

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

dp=[float('inf') for _ in range(n)]
dp[0]=0
for i in range(n):
  for j in range(1,k+1):
    if i+j<len(dp):
      dp[i+j]=min(dp[i+j],dp[i]+abs(H[i]-H[i+j]))
print(dp[-1])
### BUGGY CODE ###

N = int(input())
num = list(map(int,input().split()))
count = 0
for _ in range(N):
  if min(num[:_+1]) == num[_]:
    count += 1

print(count)
  

### FIXED CODE ###

N = int(input())
num = list(map(int,input().split()))
count = 0
m = num[0]
for _ in range(N):
  if m >= num[_]:
    m = num[_]
    count += 1

print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
l = []
A_sl = list(set(A))
if len(A_sl) == 1:
    print(len(A))
elif len(A_sl) == 2:
    if A_sl[1] - A_sl[0] <= 2:
        print(len(A))
    else:
        count_l = A.count(A_sl[1])
        count_s = A.count(A_sl[0])
        print(max(count_l,count_s)) 
else:
    for i in range(min(A),max(A) + 1):
        count_i = A.count(i)
        l.append(count_i)
    l_num = [l[i-1] + l[i] + l[i+1] for i in range(1,max(A)-min(A))]
    print(max(l_num))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
l = [0]*(10**5)
for e in A:
    if e == 0:
        l[0] += 1
        l[1] += 1
    elif e == 99999:
        l[99999] += 1
        l[99998] += 1
    else:
        l[e-1] += 1
        l[e] += 1
        l[e+1] += 1
print(max(l))
### BUGGY CODE ###

# 出現した数のフラグを立てればよいだけでは
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
happend = set()
A.sort()
ans = 0

for val in A:
    if count[val] >= 2:
        ans += 1
        happend.add(val)
        continue
    for j in range(1, int(val**(1/2))+2):
        if val % j == 0:
            if j in happend or val//j in happend:
                ans += 1
                break
    happend.add(val)

print(N-ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
A.sort()
ans = 0
max_A = max(A)
dp = [True]*(max_A+1)  # 0~max(A)の数についてのリスト
happend = set()
for a in A:
    if C[a] >= 2:
        if a in happend:
            continue
        else:
            # aが存在したという証拠だけは残しておく
            x = a * 2
            while x <= max_A:
                dp[x] = False
                x += a
            happend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a * 2
        while x <= max_A:
            dp[x] = False
            x += a
print(ans)
### BUGGY CODE ###

n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
dp=[0]*(s+1)
for i in range(n):
	dp[0]+=1
	if a[i]>s:
		continue
	ans+=dp[s-a[i]]*(n-i)
	ans%=mod
	for j in range(s,a[i]-1,-1):
		dp[j]+=dp[j-a[i]]
		dp[j]%=mod
print(ans)

### FIXED CODE ###

n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
dp=[0]*(s+1)
for i in range(n):
	dp[0]+=1
	if a[i]>s:
		continue
	ans+=dp[s-a[i]]*(n-i)
	ans%=mod
	for j in range(s,a[i]-1,-1):
		dp[j]+=dp[j-a[i]]
		dp[j]%=mod
print(ans)
### BUGGY CODE ###

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

ans = "Yes"

for i in range(1, N-1):
    if max(H[0: i]) - 1 > min(H[i: N]):
        ans = "No"
        break
print(ans)

### FIXED CODE ###

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

flag = True

for i in range(N-1, 0, -1):
    if H[i-1] - 1 == H[i]:
        H[i-1] -= 1
    elif H[i-1] - 1 > H[i]:
        flag = False
        break

if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]
heapq.heapify(ls)
res = 0
r = min([r for _, r in ls])
while True:
    res += 1
    while ls:
        ll, rr = heapq.heappop(ls)
        if ll >= r:
            heapq.heappush(ls, [ll, rr])
            break
    if len(ls) > 0:
        r = min([r for _, r in ls])
    else:
        break
print(res)

### FIXED CODE ###

n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]
ls.sort()
res = 1
rmin = float('inf')
for l, r in ls:
    if l >= rmin:
        res += 1
        rmin = r
    else:
        rmin = min(rmin, r)

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

import math

K = int(input())
ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            ans += math.gcd(i, math.gcd(j, k))

print(ans)


### FIXED CODE ###

import math

K = int(input())
ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            ans += math.gcd(i, math.gcd(j, k))

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

N, K = map(int, input().rstrip().split())
Ps = [int(x) for x in input().rstrip().split()]
base_i = 0
max_val = 0
for i in range(len(Ps)-K+1):
    sum_val = sum(Ps[i:i+K])
    if max_val < sum_val:
        max_val = sum_val
        base_i = i
print((sum(Ps[base_i:base_i+K])+K)/2)


### FIXED CODE ###

N, K = map(int, input().rstrip().split())
Ps = [int(x) for x in input().rstrip().split()]

Ps_sum_list = []
Ps_sum = 0
for x in Ps:
    Ps_sum += x
    Ps_sum_list.append(Ps_sum)

max_val = 0
if K == 1:
    max_val = max(Ps)
    print((max_val + 1) / 2)
elif N == K:
    max_val = Ps_sum_list[-1]
    print((max_val + K) / 2)
else:
    for i in range(N - K):
        val = Ps_sum_list[i + K] - Ps_sum_list[i]
        if val > max_val:
            max_val = val
    print((max_val + K) / 2)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10 * 9 + 7

flag = True

if 0 in A:
    if A.count(0) != 1:
        flag = False
S = set(A)
if 0 in S:
    S.remove(0)
flag = all(A.count(x) == 2 for x in S)

if flag:
    print(2 ** (N//2) % MOD)
else:
    print(0)


### FIXED CODE ###

# 人数分布は一意
import numpy as np
MOD = 10**9 + 7
N = int(input())
A = np.array([int(x) for x in input().split()])

left = np.arange(N)
right = N-1-left
cnt_1 = np.bincount(np.abs(left-right))
cnt_2 = np.bincount(A)

if cnt_1.shape != cnt_2.shape or (cnt_1 != cnt_2).any():
    answer = 0
else:
    answer = pow(2, N//2, MOD)

print(answer)
### BUGGY CODE ###

x=int(input())
for a in range(-10**4,10**4):
    for b in range(-10**4,10**4):
        if a**5-b**5==x:
            print(a,b)
            exit()

### FIXED CODE ###

x=int(input())
for a in range(-10**3,10**3):
    for b in range(-10**3,10**3):
        if a**5-b**5==x:
            print(a,b)
            exit()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(1,n+1):
  for j in range(1,i+1):
    if a[j-1]<a[i-1]:
      break
    if j==i:
      ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
m=a[0]
ans=1
for i,z in enumerate(a):
  if i==0:continue
  if z<=m:
    ans+=1
  m=min(m,z)
print(ans)
### BUGGY CODE ###

import itertools
N, M, R = map(int, input().split())
INF = 2 ** 63 - 1
d = [[INF for i in range(N+1)] for j in range(N+1)]
r = list(map(int, input().split()))
r = list(itertools.permutations(r))
for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c
for i in range(N+1):
    d[i][i] = 0


for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = INF
for path in r:
    anstemp = 0
    for i in range(R-1):
        anstemp += d[path[i]][path[i+1]]
    ans = min(anstemp, ans)
print(ans)


### FIXED CODE ###

import itertools
N, M, R = map(int, input().split())
INF = 2 ** 63 - 1
d = [[INF for i in range(N+1)] for j in range(N+1)]
r = list(map(int, input().split()))
r = list(itertools.permutations(r))
for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c
for i in range(N+1):
    d[i][i] = 0


for k in range(N+1):
    for i in range(N+1):
        for j in range(N+1):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = INF
for path in r:
    anstemp = 0
    for i in range(R-1):
        anstemp += d[path[i]][path[i+1]]
    ans = min(anstemp, ans)
print(ans)
### BUGGY CODE ###

N,K,Q=map(int,input().split())
A=[int(input()) for _ in range(Q)]

score=[]
answer=[]

for i in range(N):
    score.append(K)

for l in range(N):
    answer.append("Yes")

for j in range(Q):
    for k in range(N):
        if k+1==A[j]:
            pass
        else:
            score[k]-=1
            if score[k]==0:
                answer[k]="No"

for m in range(N):
    print(answer[m])

### FIXED CODE ###

N,K,Q=map(int,input().split())
A=[int(input()) for _ in range(Q)]

a=[K-Q]*N

for i in A:
    a[i-1]+=1


for j in a:
    if j>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    en.append([y1-1,x1-1,z1])
    su.append([x1-1,y1-1,a1])
    su.append([y1-1,x1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    while True:
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
    return d
from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
for i in range(n):
  kae = shortest_path(su,n,i)[t-1]
  ans.append(kae+tori[i])
moti = 10**15
for i in range(n):
  c = min(ans)
  print(moti-c)
  ans.popleft()

### FIXED CODE ###

import heapq
n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    su.append([x1-1,y1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[] for i in range(n+1)]
    for path in edge:
      cost[path[0]].append((path[1],path[2]))
      cost[path[1]].append((path[0],path[2]))
    d = [inf for j in range(num_v)]
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if d[src] < prov_cost:
                continue
      for dest,weight in cost[src]:
        if weight != float('inf') and d[dest] > d[src] + weight:
          d[dest] = d[src] + weight
          heapq.heappush(q, (d[dest], dest))
    return d
 
 
from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])
### BUGGY CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    x.append(0)
    x.sort()
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j-1]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

# coding: utf-8
import sys
import copy

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,k = na()
    a = na()
    anss = [0]*n
    while k != 0:
        flag = 0
        anss = [0]*n
        for i in range(n):
            ai = a[i]
            if ai >= n-1:
                flag += 1
            for j in range(max(0,i-ai), min(n,i+ai+1)):
                anss[j] += 1
        if flag == n:
            for i in range(n):
                anss[i] = n
            break
        a = copy.copy(anss)
        k -= 1
    print(' '.join(list(map(str,anss))))
    return


if __name__ == '__main__':
    main()

### FIXED CODE ###

# coding: utf-8
import sys
import copy

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,k = na()
    a = na()
    memo = [0]*(n+1)
    for i in range(n):
        ai = a[i]
        memo[max(0, i-ai)] += 1
        memo[min(n, i+ai+1)] -= 1
    k -= 1
    if k == 0:
        tmp = 0
        for i in range(n):
            tmp += memo[i]
            print(tmp, end=' ')
        return
    while k != 0:
        flag = 0
        memo2 = [0]*(n+1)
        tmp = 0
        for i in range(n+1):
            tmp += memo[i]
            if tmp >= max(i, n-i-1):
                flag += 1
            memo2[max(0, i-tmp)] += 1
            memo2[min(n, i+tmp+1)] -= 1
        if flag == n:
            memo2[0] = n
            memo2[-1] = -1*n
            break
        memo = copy.copy(memo2)
        k -= 1
    tmp = 0
    for i in range(n):
        tmp += memo2[i]
        print(tmp, end=' ')
    return


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

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)

col = [0 for _ in range(n)]
def bfs(bs, d, c):
  if d < 0:
    return
  nset = set()
  for b in bs:
    nset = nset.union(g[b])
    col[b] = c
  return bfs(nset, d-1, c)
  
q = int(input())
for _ in range(q):
  v, d, c = map(int, input().split())
  col[v-1] = c
  bfs(set(g[v-1]), d-1, c)
for c in col:
  print(c)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(m)]
    edges = [[] for _ in range(n)]
    for a, b in ab:
        edges[a - 1].append(b - 1)
        edges[b - 1].append(a - 1)
    
    q = int(input())
    ans = [0 for _ in range(n)]
    dd = [-1 for _ in range(n)]
    vdc = [tuple(map(int, input().split())) for _ in range(q)]
    for v, d, c in vdc[::-1]:
        if dd[v - 1] >= d:
            #  v - 1 から距離 d の部分は塗りつぶされているため無視
            continue
        
        node = []
        node.append(v - 1)
        while d >= 0 and len(node) > 0:
            next_node = []
            while len(node) > 0:
                u = node.pop()
                if dd[u] >= d:
                    continue
                dd[u] = d
                if ans[u] == 0:
                    ans[u] = c
                for v in edges[u]:
                    if dd[v] < d - 1:
                        next_node.append(v)
            node = next_node
            d -= 1
    
    print(*ans, sep='\n')


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

from collections import defaultdict


class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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


uf = UnionFind(n)

friends = defaultdict(int)
chain = defaultdict(int)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a] += 1
    friends[b] += 1
    uf.union(a, b)

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if uf.find(i) == uf.find(j):
            chain[i] += 1

for _ in range(k):
    c, d = map(int, input().split())
    if uf.find(c) == uf.find(d):
        friends[c] += 1
        friends[d] += 1

ans = []
for i in range(1, n + 1):
    ans.append(chain[i] - friends[i] - 1)

print(*ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.ps = [-1] * (n + 1)

    def find(self, x):
        if self.ps[x] < 0:
            return x
        else:
            self.ps[x] = self.find(self.ps[x])
            return self.ps[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.ps[x] > self.ps[y]:
            x, y = y, x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        x = self.find(x)
        return -self.ps[x]


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


uf = UnionFind(n)

friends = [0] * (n + 1)
chain = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a] += 1
    friends[b] += 1
    uf.union(a, b)

for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c, d):
        friends[c] += 1
        friends[d] += 1

ans = []
for i in range(1, n + 1):
    ans.append(uf.size(i) - friends[i] - 1)

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

N=int(input())
A=list(map(int,input().split()))
from functools import reduce
from math import gcd
g=reduce(lambda x,y:gcd(x,y),A,0)
if g>1:
    print('not coprime')
    exit()
def prime(N):
    p=set(range(2,N+1))
    for i in range(int(N**.5)+1):
        if i in p:
            p-=set(range(i*2,N+1,i))
    return p
p=prime(1000)
r=1
s=set()
for a in A:
    p2=p.copy()
    for x in p:
        if a%x==0:
            p2.remove(x)
        while a%x==0:
            a//=x
        if a==1:
            break
    if a>1:
        if 1000<a and a not in s:
            s.add(a)
        else:
            r=0
            break
    p=p2
print(['setwise coprime','pairwise coprime'][r])

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
from functools import reduce
from math import gcd
g=reduce(lambda x,y:gcd(x,y),A,0)
if g>1:
    print('not coprime')
    exit()
def prime(N):
    p=set(range(2,N+1))
    for i in range(int(N**.5)+1):
        if i in p:
            p-=set(range(i*2,N+1,i))
    return p
p=prime(1000)
r=1
s=set()
for a in A:
    f=0
    for x in p:
        if a%x==0:
            if f==0:
                p2=p.copy()
                f=1
            p2.remove(x)
        while a%x==0:
            a//=x
        if a==1:
            break
    if a>1:
        if 1000<a and a not in s:
            s.add(a)
        else:
            r=0
            break
    if f:
        p=p2
print(['setwise coprime','pairwise coprime'][r])