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

N,M,K=map(int,input().split())
fdic={}
for i in range(1,N+1):
  fdic[i]=set()  
for i in range(M):
  a,b=map(int,input().split())
  fdic[a].add(b)
  fdic[b].add(a)

bdic={}
for i in range(1,N+1):
  bdic[i]=set()
for i in range(K):
  c,d=map(int,input().split())
  bdic[c].add(d)
  bdic[d].add(c)
  
#print(fdic)
#print(bdic)

dic_cluster={}
cluster_num=0
cluster_list=[0]*(N+1)

for i in range(1,N+1):
  if cluster_list[i]>0:
    continue
  else:
    cluster_num+=1
    dic_cluster[cluster_num]=set()
    visited=set()
    queue=[i]
    while(len(queue)>0):
      new_queue=set()
      for q in queue:
        cluster_list[q]=cluster_num
        dic_cluster[cluster_num].add(q)
        visited.add(q)
        nx=fdic[q]
        for n in nx:
          if not n in visited:
            new_queue.add(n)

      queue=new_queue
      #print(new_queue)
      
#print(cluster_list)
#print(dic_cluster)

candlist=[]
for i in range(1,N+1):
  cluster_i=set(dic_cluster[cluster_list[i]])  
  cluster_i.remove(i)
  #print(cluster_i.difference(fdic[i]).difference(bdic[i]))  
  candlist.append(str(len(cluster_i.difference(fdic[i]).difference(bdic[i]))))
  
print(" ".join(candlist))
  
  

### FIXED CODE ###

N,M,K=map(int,input().split())
fdic={}
for i in range(1,N+1):
  fdic[i]=set()  
for i in range(M):
  a,b=map(int,input().split())
  fdic[a].add(b)
  fdic[b].add(a)

blist=[]
for i in range(K):
  c,d=map(int,input().split())
  blist.append((c,d))
  
#print(fdic)
#print(blist)

dic_cluster={}
cluster_num=0
cluster_list=[0]*(N+1)

for i in range(1,N+1):
  if cluster_list[i]>0:
    continue
  else:
    cluster_num+=1
    dic_cluster[cluster_num]=set()
    visited=set()
    queue=[i]
    while(len(queue)>0):
      new_queue=set()
      for q in queue:
        cluster_list[q]=cluster_num
        dic_cluster[cluster_num].add(q)
        visited.add(q)
        nx=fdic[q]
        for n in nx:
          if not n in visited:
            new_queue.add(n)

      queue=new_queue
      #print(new_queue)
      
#print(cluster_list)
#print(dic_cluster)

candlist=[0]*(N+1)
for i in range(1,N+1):
  candlist[i]=len(dic_cluster[cluster_list[i]])-len(fdic[i])-1
for c,d in blist:
  if d in dic_cluster[cluster_list[c]]:
    candlist[c]-=1
    candlist[d]-=1
  
print(" ".join(map(str,candlist[1:])))
### BUGGY CODE ###

from collections import defaultdict
N = input()
a_raw = list(map(int, input().split()))
a_plus = [num + 1 for num in a_raw]
a_minus = [num - 1 for num in a_raw]
numbers = set(a_raw) | set(a_minus) | set(a_plus)
num_count = list()
for number in numbers:
    num_count.append(a_raw.count(number) + a_plus.count(number) + a_minus.count(number))

print(max(num_count))

### FIXED CODE ###

from collections import defaultdict as dd
N = input()
a_raw = list(map(int, input().split()))
num_count = dd(int)
for item in a_raw:
    num_count[item] += 1
    num_count[item-1] += 1
    num_count[item+1] += 1
print(max(num_count.values()))
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

MOD = 10**9 + 7

N = int(input())
A = [int(x) for x in input().split()]
C = np.zeros(N,dtype = np.int64) # cumsum

cum = 0
for i,a in enumerate(A):
  cum ^= a
  C[i] = cum

X = list(set(C)) # 候補
if 0 in X:
  X.remove(0)

X_to_idx = {x:i for i,x in enumerate(X)}

L = len(X)

arr = np.zeros((L,2),dtype=np.int64)
arr[:,0] = 1
# a,0,...でいまのところ矛盾なくできている列
# 0,a,...

zero_update = np.zeros(L,dtype=np.int64) #0が出てきて更新した回数
zero_cnt = 0

for i in range(N):
  c = C[i]
  if c == 0:
    zero_cnt += 1
    continue
  idx = X_to_idx[c]
  # 蓄積された0の回数分アップデート
  n = zero_cnt - zero_update[idx]
  zero_update[idx] = zero_cnt
  a = arr[idx,0]
  b = arr[idx,1]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr[idx,0] = a
  arr[idx,1] = b

answer = 0
final = C[-1]
if final != 0:
  idx = X_to_idx[final]
  answer = arr[idx,0]
else:
  answer = arr[:,1].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr_0 = [1] * U
arr_1 = [0] * U
 
zero_update = [0] * U #0が出てきて更新した回数
zero_cnt = 0
 
c = 0
for a in A:
  c ^= a
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr_0[c]
  b = arr_1[c]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr_0[c] = a
  arr_1[c] = b
 
answer = 0
if c != 0:
  answer = arr_0[c]
else:
  answer = sum(arr_1[1:])
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)
### BUGGY CODE ###

n,p=map(int,input().split())
if n==1:
    print(p)
else:
    d=int(p**(1/n))
    k=1
    for i in range(1,d+2):
        if p%(i**n)==0:
            k=i
    else:
        print(k)

### FIXED CODE ###

n,p=map(int,input().split())
if n==1:
    print(p)
else:
    def r(n,p):
        d=int(p**(1/n))
        k=1
        for i in range(1,d+1):
            if p%(i**n)==0:
                k=i
        return k
    c=1
    while r(n,p)!=1:
        s=r(n,p)
        c*=s
        p=p/(s**n)
    print(c)
### BUGGY CODE ###

import itertools

N, M= (int(i) for i in input().split())
X = list(int(i) for i in input().split())
X.sort()

if(N >= M):
    print(0)
else:
    X_index = range(M) # 0~N-1の連続リスト
    combination = list(itertools.combinations(X_index,N-1))
    min = 2 * 100000
    for tmp_taple in combination:
        tmp_sum = 0
        from_index = 0
        for to_index in tmp_taple:
            tmp_sum += X[to_index] - X[from_index]
            from_index = to_index + 1
        if(from_index < M-1):
            tmp_sum += X[M-1] - X[from_index]
        if(min > tmp_sum):
            min = tmp_sum
    print(min)

### FIXED CODE ###

N, M= (int(i) for i in input().split())
if (N<M):
    X = list(int(i) for i in input().split())
    X.sort()
    Y = [X[i] - X[i-1] for i in range(1, len(X))]
    Y.sort()
    print(sum(Y[0:M-N]))
else:
    print(0)


"""
N個のコマ：N-1個の閉経路が存在する
各座標の距離を求める(M-1個)
M：座標の数　N:駒の数
移動しなくても通っている座標の数: N
M - N
"""
### BUGGY CODE ###

from operator import mul
from functools import reduce
from collections import Counter

def cmb(n, r):
    if n < 2:
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

N = int(input())
A = [int(x) for x in input().split()]
C = Counter(A)
ans = {}

cal = {}
for a, b in C.items():
    cal[a] = cmb(b, 2)
for i in C.keys():
    ans[i] = sum(cal.values()) - (C[i] - 1)
for a in A:
    print(ans[a])

### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]
C = Counter(A)
ans = {}
cal = sum([b*(b-1)//2 for b in C.values()])
for a, b in C.items():
    ans[a] = cal - (b-1)
for a in A:
    print(ans[a])
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
for i in range(len(s)):
    for j in range(i,len(s)):
        for k in range(j,len(s)):
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k] and j-i!=k-j:
                ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())

num_r = s.count('R')
num_g = s.count('G')
num_b = s.count('B')

ans = num_r*num_g*num_b

for i in range(n):
    for j in range(i, n):
        k = j+(j-i)
        if (k < n) and (s[i] != s[j]) and (s[j] != s[k]) and (s[k] != s[i]):
            ans -= 1
print(ans)
### BUGGY CODE ###

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

BC.sort(key=lambda x: x[1], reverse=True)
for B, C in BC:
    A.sort()
    mn = A[0]
    if mn >= C:
        break
    if A[B - 1] <= C:
        A[:B] = [C] * B
    else:
        a, b = 0, B
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        A[:b] = [C] * b

print(sum(A))

### FIXED CODE ###

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

BC.sort(key=lambda x: x[1], reverse=True)
A.sort()
l, r = 0, N
for B, C in BC:
    if A[l] >= C:
        break
    a, b = l, r
    if A[r - 1] >= C:
        while a + 1 < b:
            i = a + (b - a) // 2
            if A[i] >= C:
                b = i
            else:
                a = i
        r = b
    n = B + l
    if n > r:
        n = r
        B = n - l
    if n <= b:
        A[l:n] = [C] * B
        l = n
    else:
        A[l:b] = [C] * B
        l = b
    if l == r:
        break

print(sum(A))
### BUGGY CODE ###

H, W, K = map(int, input().split())
items = []

start = []
diff = float("inf")
p = []
prev = [[False] * W for _ in range(H)]
for i in range(H):
    items.append(list(input()))
    for j in range(W):
        s = items[i][j]
        if s == "S":
            start = [i, j]
            diff = min(diff, min(i, H - 1 - i, min(j, W - 1 - j)))
            p = [i, j]
            prev[i][j] = True

from collections import deque

que = deque([])

dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]

for i in range(4):
    x = dx[i]
    y = dy[i]
    if 0 <= start[0] + y <= H - 1 and 0 <= start[1] + x <= W - 1:
        tmp = items[start[0] + y][start[1] + x]
        if tmp == ".":
            que.append((start[0] + y, start[1] + x))
k = K
while len(que) != 0 and k != 0:
    que2 = deque([])
    while len(que) != 0:
        q = que.popleft()
        a = q[0]
        b = q[1]
        prev[a][b] = True
        c = min(min(a, H - 1 - a), min(b, W - 1 - b))
        if c < diff:
            diff = c
            p = (a, b)

        for i in range(4):
            x = dx[i]
            y = dy[i]
            if 0 <= a + y <= H - 1 and 0 <= b + x <= W - 1:
                if prev[a + y][b + x]:
                    continue
                tmp = items[a + y][b + x]
                if tmp == ".":
                    que2.append((a + y, b + x))
    k -= 1
    que = que2

ans = 1
if diff == 0:
    print(ans)
else:
    print(ans + (K - 1 + diff) // K)


### FIXED CODE ###

H, W, K = map(int, input().split())
items = []

start = []
diff = float("inf")
p = []
prev = [[False] * W for _ in range(H)]
for i in range(H):
    items.append(list(input()))
    for j in range(W):
        s = items[i][j]
        if s == "S":
            start = [i, j]
            diff = min(diff, min(i, H - 1 - i, min(j, W - 1 - j)))
            p = [i, j]
            prev[i][j] = True

from collections import deque

que = deque([])

dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]

for i in range(4):
    x = dx[i]
    y = dy[i]
    if 0 <= start[0] + y <= H - 1 and 0 <= start[1] + x <= W - 1:
        tmp = items[start[0] + y][start[1] + x]
        if tmp == ".":
            que.append((start[0] + y, start[1] + x))
            prev[start[0] + y][start[1] + x] = True
k = K
while len(que) != 0:
    q = que.popleft()
    a = q[0]
    b = q[1]
    if abs(start[0] - a) + abs(start[1] - b) > K:
        continue
    c = min(min(a, H - 1 - a), min(b, W - 1 - b))
    if c < diff:
        diff = c
        p = (a, b)

    for i in range(4):
        x = dx[i]
        y = dy[i]
        if 0 <= a + y <= H - 1 and 0 <= b + x <= W - 1:
            if prev[a + y][b + x]:
                continue
            tmp = items[a + y][b + x]
            if tmp == ".":
                que.append((a + y, b + x))
                prev[a + y][b + x] = True

ans = 1
if diff == 0:
    print(ans)
else:
    print(ans + (K - 1 + diff) // K)
### BUGGY CODE ###

n = int(input())
s = list(input())
cnt = 0

l_R = [i for i , x in enumerate(s) if x == "R"]
l_G = [i for i , x in enumerate(s) if x == "G"]
l_B = [i for i , x in enumerate(s) if x == "B"]

RGB = [[l_R, l_B, l_G], [l_R, l_G, l_B], [l_B, l_G, l_R], 
        [l_B, l_R, l_G], [l_G, l_R, l_B], [l_G, l_B, l_R]]

for A, B, C in RGB:
    for i in A:
        for j in B:
            for k in C:
                if (j - i != k - j) & (i < j < k):
                    cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = list(input())
cnt = 0

cnt = s.count("R") * s.count("B") * s.count("G")
# j - i = k -j を求める。
sub = 0 
for i in range(n):
    for j in range(i, n):
        k = 2 * j - i
        if k <= n - 1:
            if (s[i] != s[j]) and (s[j] != s[k]) and (s[i] != s[k]):
                sub += 1

print(cnt-sub)
### BUGGY CODE ###

from bisect import bisect_left
from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)

A.sort()
result = 0
for i in range(N):
    if A[i] < 1:
        t = bisect_left(A, 1 // A[i])
    else:
        t = i + 1
    for j in range(t, N):
        t = A[i] * A[j]
        if t == int(t):
            result += 1
print(result)


### FIXED CODE ###

def conv(s):
    if s.find('.') == -1:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


N, *A = open(0).read().split()
N = int(N)

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
L = list(map(int, input().split()))

L.sort()
#print(L)

from bisect import bisect_right,bisect_left

ans = 0
for i, a in enumerate(L[:-2]):
    for j, b in enumerate(L[i+1:-1]):
        j=i+1+j
        #print(a+b, abs(a-b), i, j)
        #for k, c in enumerate(L[j+1:]):
        #    if abs(a-b) < c and c < a+b:
        #        ans += 1
        #    if c >= a+b:
        #        break
        l = bisect_right(L[j+1:], abs(a-b))
        r = bisect_left(L[j+1:], a+b)
        #print(r-l)
        ans += r-l
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
L = list(map(int, input().split()))

L.sort()
#print(L)

from bisect import bisect_right,bisect_left

ans = 0
for i, a in enumerate(L[:-2]):
    for j, b in enumerate(L[i+1:-1]):
        j=i+1+j
        #print(a+b, abs(a-b), i, j)
        #for k, c in enumerate(L[j+1:]):
        #    if abs(a-b) < c and c < a+b:
        #        ans += 1
        #    if c >= a+b:
        #        break
        l = bisect_left(L, abs(a-b),j+1)
        r = bisect_left(L, a+b,j+1)
        #print(r-l)
        ans += r-l
print(ans)
### BUGGY CODE ###

def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    check = [[1]*n for i in range(n)]
    d = [[float("INF")]*n for i in range(n)]

    for i in range((n+1)//2):
        for j in range(i,n-i):
            d[i][j] = i
            d[-1-i][j] = i
        for j in range(i,n-i):
            d[j][i] = i
            d[j][-1-i] = i

    ans = 0
    for t in l:
        t -=1
        x = t//n
        y = t%n
        check[x][y] = 0
        ans += d[x][y]
        q = deque([])
        q.append((x,y,d[x][y]))
        while q:
            bx,by,z = q.popleft()

            if bx != 0:
                if d[bx-1][by] > z:
                    d[bx-1][by] = z
                    q.append((bx-1,by,z+check[bx-1][by]))
            if bx != n-1:
                if d[bx+1][by] > z:
                    d[bx+1][by] = z
                    q.append((bx+1,by,z+check[bx+1][by]))
            if by != 0:
                if d[bx][by-1] > z:
                    d[bx][by-1] = z
                    q.append((bx,by-1,z+check[bx][by-1]))
            if by != n-1:
                if d[bx][by+1] > z:
                    d[bx][by+1] = z
                    q.append((bx,by+1,z+check[bx][by+1]))  
    print(ans)
if __name__ =="__main__":
    main()

### FIXED CODE ###

def main():
    from collections import deque
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    check = [[1]*n for i in range(n)]
    d = [[float("INF")]*n for i in range(n)]

    for i in range((n+1)//2):
        for j in range(i,n-i):
            d[i][j] = i
            d[-1-i][j] = i
        for j in range(i,n-i):
            d[j][i] = i
            d[j][-1-i] = i
    def solve(l):
        ans = 0
        for t in l:
            t -=1
            x = t//n
            y = t%n
            check[x][y] = 0
            ans += d[x][y]
            q = deque([])
            q.append((x,y,d[x][y]))
            while q:
                bx,by,z = q.popleft()

                if bx != 0:
                    if d[bx-1][by] > z:
                        d[bx-1][by] = z
                        q.append((bx-1,by,z+check[bx-1][by]))
                if bx != n-1:
                    if d[bx+1][by] > z:
                        d[bx+1][by] = z
                        q.append((bx+1,by,z+check[bx+1][by]))
                if by != 0:
                    if d[bx][by-1] > z:
                        d[bx][by-1] = z
                        q.append((bx,by-1,z+check[bx][by-1]))
                if by != n-1:
                    if d[bx][by+1] > z:
                        d[bx][by+1] = z
                        q.append((bx,by+1,z+check[bx][by+1]))  
        return ans

    
    print(solve(l))

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

import heapq

N, M = map(int, input().split())
income = [[] for _ in range(M+1)]  # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        income[a].append(-b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
tmp = []
for rest_days in range(1, M+1):
    tmp = list(heapq.merge(tmp, income[rest_days]))
    heapq.heapify(tmp)
    if tmp:
        ans += heapq.heappop(tmp)

print(-ans)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
income = [[] for _ in range(M+1)]  # income[i]はi日後に報酬が得られる全ての仕事についての報酬のリスト
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        income[a].append(-b)

# 後ろから考える。残りi日のときに終了までに報酬が得られる仕事のうち報酬最大のものを選ぶ
ans = 0
tmp = []
heapq.heapify(tmp)

for rest_days in range(1, M+1):
    for x in income[rest_days]:
        heapq.heappush(tmp, x)
    if tmp:
        ans += heapq.heappop(tmp)

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

import sys

sys.setrecursionlimit(10 ** 9)

def main():
  input = sys.stdin.buffer.readline
  read = sys.stdin.buffer.read
  # Nがノードの数, Qが操作回数
  N, Q = map(int, input().split())
  ABPX = list(map(int, read().split()))
  AB = iter(ABPX[:N+N-2])
  PX = iter(ABPX[N+N-2:])

  parents = [None] * N
  childrens = [set() for _ in range(N)]
  relations = {}
  shown = set()

  for a, b in zip(AB, AB):
    a -= 1
    b -= 1
    # parents[b] = a
    # childrens[a].add(b)
    relations.setdefault(a, [])
    relations.setdefault(b, [])
    relations[a].append(b)
    relations[b].append(a)

  def f(parent, relations, parents, childrens):
    shown.add(parent)
    for c in relations[parent]:
      if c not in shown:
        parents[c] = parent
        childrens[parent].add(c)
        f(c, relations, parents, childrens)

  f(0, relations, parents, childrens)
  points = {}
  result = [0] * N

  for p, x in zip(PX, PX):
    p -= 1
    points.setdefault(p, 0)
    points[p] += x

  def solve(idx, parents, childrens, points, result):
    # print(idx)
    if idx in points:
      result[idx] += points[idx]
    if parents[idx] is not None:
      result[idx] += result[parents[idx]]
    for child in childrens[idx]:
      solve(child, parents, childrens, points, result)
      
  solve(0, parents, childrens, points, result)
  print(*result)

if __name__ == "__main__":
  main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 9)

def main():
  input = sys.stdin.buffer.readline
  read = sys.stdin.buffer.read
  # Nがノードの数, Qが操作回数
  N, Q = map(int, input().split())
  ABPX = list(map(int, read().split()))
  AB = iter(ABPX[:N+N-2])
  PX = iter(ABPX[N+N-2:])

  parents = [None] * N
  childrens = [set() for _ in range(N)]
  relations = [[] for _ in range(N)]
  shown = set()

  for a, b in zip(AB, AB):
    a -= 1
    b -= 1
    relations[a].append(b)
    relations[b].append(a)

  points = [0] * N
  result = [0] * N

  for p, x in zip(PX, PX):
    p -= 1
    points[p] += x

  def solve(parent, relations, points, result):
    result[parent] += points[parent]
    shown.add(parent)
    for child in relations[parent]:
      if child not in shown:
        result[child] += result[parent]
        solve(child, relations, points, result)
      
  solve(0, relations, points, result)
  print(*result)

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

from fractions import gcd


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

lcm = A[0]

for a in A:
    lcm = (lcm * a) // gcd(lcm, a)

ans = 0
for a in A:
    ans += lcm // a
    ans %= MOD

print(ans)


### FIXED CODE ###

from fractions import gcd


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

lcm = A[0]

for a in A:
    lcm = (lcm * a) // gcd(lcm, a)

ans = 0
for a in A:
    ans += (lcm % MOD) * pow(a, MOD - 2, MOD)
    ans %= MOD

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

import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def make_modinv_list(n, mod=10**9+7):
    inv_list = [0]*(n+1)
    inv_list[1] = 1
    for i in range(2, n+1):
        inv_list[i] = (mod - mod//i * inv_list[mod%i] % mod)
    return inv_list

def solve():
  mod = 998244353
  n = ni()
  a = nl()
  m = max(a)
  s = -sum(a) % mod
  l = [0]*(m+1)
  for x in a:
    l[x] += x
  a = make_modinv_list(m, mod)
  sieve = [1]*(m+1)
  sieve[0] = sieve[1] = 0
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(m//i, 0, -1):
        sieve[j*i] = 0
        l[j] += l[j*i]
      sieve[i] = 1
  for i in range(m+1):
    l[i] = l[i] * l[i] % mod
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(1, m//i + 1):
        l[j] = (l[j] - l[j*i]) % mod
  for i in range(1, m+1):
    if l[i]:
      s = (s + l[i] * a[i]) % mod
  print(s * a[2] % mod)
  return

solve()

### FIXED CODE ###

import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def solve():
  n = ni()
  a = nl()
  m = max(a)
  mod = 998244353
  l = [0]*(m+1)
  for x in a:
    l[x] += x
  sieve = [1]*(m+1)
  sieve[0] = sieve[1] = 0
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(m//i, 0, -1):
        sieve[j*i] = 0
        l[j] += l[j*i]
      sieve[i] = 1
  for i in range(m+1):
    l[i] = l[i] * l[i] % mod
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(1, m//i + 1):
        l[j] -= l[j*i]
  s = -sum(a)
  for i in range(1, m+1):
    if l[i]:
      s = (s + l[i] * modinv(i, mod)) % mod
  print(s * modinv(2, mod) % mod)
  return

solve()
### BUGGY CODE ###

import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
#print(l)
ans=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=l[b+1:]
        min_c= l[b]-l[a]+1
        max_c= l[a]+l[b]-1
#        print(str(l[a])+","+str(l[b])+" "+str(min_c) + ":" + str(max_c))
        if(min_c <= max_c):
            ans+=bisect.bisect_right(c, max_c) - bisect.bisect_left(c, min_c)
print(ans)


### FIXED CODE ###

import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        min_c=j+1
        max_c=bisect.bisect_left(l, l[j]+l[i])-1
        num=max_c-min_c+1
#        print(str(l[i])+" "+str(l[j])+":"+str(min_c)+" "+str(max_c)+":"+str(num))
        ans += num if num > 0 else 0
print(ans)