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

from collections import deque


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        g[a].append(b)
        g[b].append(a)
    max_val = 10 ** 9 + 7
    dist = [max_val for _ in range(n)]
    prev = [-1 for _ in range(n)]
    dist[0] = 0
    
    q = deque([0])
    while q:
        now = q.pop()
        for next in g[now]:
            if prev[next] < 0 or dist[now] + 1 < dist[next]:
                prev[next] = now + 1
                dist[next] = dist[now] + 1
                q.append(next)
    if all(prev[i] > 0 for i in range(1, n)):
        print("Yes")
        for i in range(1, n):
            print(prev[i])
    else:
        print("No")


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import deque


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        g[a].append(b)
        g[b].append(a)
    max_val = 10 ** 9 + 7
    dist = [max_val for _ in range(n)]
    prev = [-1 for _ in range(n)]
    dist[0] = 0
    q = deque([0])
    cnt = 0
    while q:
        now = q.popleft()
        for next in g[now]:
            if prev[next] < 0:
                if prev[next] < 0:
                    q.append(next)
                    cnt += 1
                prev[next] = now + 1
                dist[next] = dist[now] + 1
    if cnt == n:
        print("Yes")
        for i in range(1, n):
            print(prev[i])
    else:
        print("No")


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

from operator import mul
from functools import reduce

def cmb(n,r):
    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())
L=input()
L=L.split()
L=[int(item) for item in L]
L.sort()
ans=cmb(N,3)
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in reversed(range(j+1,N)):
            if (L[i]+L[j])>L[k]:
                break
            else:
                ans-=1


print(int(ans))

### FIXED CODE ###

from operator import mul
from functools import reduce
import bisect

def cmb(n,r):
    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())
L=input()
L=L.split()
L=[int(item) for item in L]
L.sort()
ans=cmb(N,3)
ans2=0
for i in reversed(range(2,N)):
    for j in reversed(range(1,i)):
        a=bisect.bisect_right(L,L[i]-L[j])
#        print('{0}:{1}'.format(a,j))
#        print(a)
        if(a<j):
            ans2+=(j-a)
    

print(ans2)
### BUGGY CODE ###

x = int(input())
m = 100

import math
count = 0
while True:
    if m >= x:
        print(count)
        break
    x = math.floor(100 * 1.01)
    count += 1
    

### FIXED CODE ###

x = int(input())
m = 100

count = 0
while m < x:
    m += m // 100
    count += 1

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

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

div = 2
res = 1
while P != 1 and div <= P:
    cnt = 0
    while P % div == 0:
        P /= div
        cnt += 1

        if cnt == N:
            res *= div
            cnt = 0
    div += 1

print(res)


### FIXED CODE ###

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

if N == 1:
    print(P)
    exit()

div = 2
res = 1
R = P

while div * div <= R and div <= P:
    cnt = 0
    while P % div == 0:
        P /= div
        cnt += 1

        if cnt == N:
            res *= div
            cnt = 0
    div += 1

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

n,d = map(int,input().split())
num = [[0]*d for i in range(d)]
a = 0
for i in range(n):
  x,y = map(int,input().split())
  x %=d
  y%=d
  num[x][y] += 1
  a = max(a,num[x][y])
x=1
while x*x<a:
  x += 1
r = (x-1)*d
a = x-1
dai = d-1
syo = 0
anum = [[[0]*d for i in range(d)]for i in range(2)]
rui = [[[0]*(2*d+1) for i in range(2*d+1)]for i in range(2)]
for i in range(d):
  for j in range(d):
    z = num[i][j]
    if z> a*(a+1):
      anum[0][i][j]=1
      anum[1][i][j]=1
    elif z > a*a:
      anum[1][i][j]=1
for x in range(2):
  for i in range(1,2*d+1):
    for j in range(1,2*d+1):
      rui[x][i][j]+=rui[x][i-1][j]+rui[x][i][j-1]-rui[x][i-1][j-1]+anum[x][(i-1)%d][(j-1)%d]
def cheak(kon):
  for i in range(1,d+1):
    for j in range(1,d+1):
      if rui[1][i+d-1][j+d-1] - rui[1][i+kon+1 - 1][j+d-1] - rui[1][i+d-1][j+kon+1 - 1] + rui[1][i+kon+1 - 1][j+kon+1 - 1]:
        continue
      if rui[0][i+d-1][j+kon] - rui[0][i+kon+1 - 1][j+kon] - rui[0][i+d-1][j - 1] + rui[0][i+kon+1 - 1][j - 1]:
        continue
      if rui[0][i+kon][j+d-1] - rui[0][i - 1][j+d-1] - rui[0][i+kon][j+kon+1 - 1] + rui[0][i - 1][j+kon+1 - 1]:
        continue
      return 1
  return 0 
kon = (dai+syo)//2
while True:
  if dai-syo <= 1:
    if cheak(syo) == 1:
       dai = syo
    break
  kon = (dai+syo)//2
  c = cheak(kon)
  if c == 1:
    dai = kon
  else:
    syo = kon
print(dai+r)

### FIXED CODE ###

n,d = map(int,input().split())
num = [[0]*d for i in range(d)]
a = 0
for i in range(n):
  x,y = map(int,input().split())
  x %=d
  y%=d
  num[x][y] += 1
  a = max(a,num[x][y])
x=1
while x*x<a:
  x += 1
r = (x-1)*d
a = x-1
dai = d-1
syo = 0
anum = [[[0]*d for i in range(d)]for i in range(3)]
rui = [[[0]*(2*d+1) for i in range(2*d+1)]for i in range(3)]
for i in range(d):
  for j in range(d):
    z = num[i][j]
    if z > (a+1)**2:
      anum[0][i][j]=1
      anum[1][i][j]=1
      anum[2][i][j]=1
    elif z> a*(a+1):
      anum[1][i][j]=1
      anum[2][i][j]=1
    elif z > a*a:
      anum[1][i][j]=1
for x in range(3):
  for i in range(1,2*d+1):
    for j in range(1,2*d+1):
      rui[x][i][j]+=rui[x][i-1][j]+rui[x][i][j-1]-rui[x][i-1][j-1]+anum[x][(i-1)%d][(j-1)%d]
def cheak(kon):
  for i in range(1,d+1):
    for j in range(1,d+1):
      if rui[0][i+kon][j+kon] - rui[0][i - 1][j+kon] - rui[0][i+kon][j - 1] + rui[0][i - 1][j - 1]:
        continue
      if rui[1][i+d-1][j+d-1] - rui[1][i+kon+1 - 1][j+d-1] - rui[1][i+d-1][j+kon+1 - 1] + rui[1][i+kon+1 - 1][j+kon+1 - 1]:
        continue
      if rui[2][i+d-1][j+kon] - rui[2][i+kon+1 - 1][j+kon] - rui[2][i+d-1][j - 1] + rui[2][i+kon+1 - 1][j - 1]:
        continue
      if rui[2][i+kon][j+d-1] - rui[2][i - 1][j+d-1] - rui[2][i+kon][j+kon+1 - 1] + rui[2][i - 1][j+kon+1 - 1]:
        continue
      return 1
  return 0 
kon = (dai+syo)//2
while True:
  if dai-syo <= 1:
    if cheak(syo) == 1:
       dai = syo
    break
  kon = (dai+syo)//2
  c = cheak(kon)
  if c == 1:
    dai = kon
  else:
    syo = kon
print(dai+r)
### BUGGY CODE ###

n, m = map(int, input().split())
query = []
for i in range(m):
    qList = list(map(int, input().split()))
    query.append(qList)
result = [[] for i in range(n)]

for city in query:
    result[city[0]-1].append(city[1])

for i in result:
    i.sort()

for city in query:
    rank = result[city[0]-1].index(city[1])+1
    resultStr = "{}{}".format(str(city[0]).zfill(6), str(rank).zfill(6))
    print(resultStr)

### FIXED CODE ###

def main():
    from sys import stdin
    from bisect import bisect_left

    readline = stdin.readline
    n, m = map(int, readline().split())
    data = [list(map(int, readline().split())) for _ in range(m)]
    t = [[] for _ in range(n)]

    for p, y in data:
        t[p - 1].append(y)

    for i in range(n):
        t[i].sort()

    for p, y in data:
        nth = bisect_left(t[p - 1], y) + 1
        print("%06d%06d" % (p, nth))

main()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

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

    visited = [0]
    now = 0
    ind = 0
    for _ in range(K):
        if A[now]-1 in visited:
            ind = visited.index(A[now]-1)
            break
        else:
            visited.append(A[now]-1)
            now = A[now]-1

    loop_visited = visited[ind:]
    ans_ind = (K-ind) % len(loop_visited)

    print(loop_visited[ans_ind]+1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

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

    # N = 2*(10**4)
    # K = 10**18
    # A = [i+2 for i in range(N)]
    # A[-1] = 1
    # print(A)

    visited = [0]
    visited_set = set([0])
    now = 0
    ind = 0
    my_append = visited.append
    my_add = visited_set.add
    for i in range(K):
        a = A[now]-1
        if a in visited_set:
            ind = visited.index(a)
            break
        else:
            my_add(a)
            my_append(a)
            now = a
            # ind = i

    loop_visited = visited[ind:]
    ans_ind = (K-ind) % len(loop_visited)

    print(loop_visited[ans_ind]+1)


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

n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")

nxt = [i for i in range(n+1)]
for i in range(1, n):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	ans = 0
	tmp = x ^ (1 << (n-1-i))
	if tmp == 0:
		print(0)
		continue
	if tmp > x:
		ans = 1
		tmp %= p+1
	else:
		ans = 1
		tmp %= p-1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")
if p > 1:
	pre0 = x%(p-1)
pre1 = x%(p+1)

nxt = [i for i in range(n+10)]
for i in range(1, n+10):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (pre1 + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (pre0 - pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)
### BUGGY CODE ###

from scipy.misc import comb


def solve(string):
    n, m, k = map(int, string.split())
    base = n * m * ((n + 1) * (m + 1) * (n + m - 2) - n**2 - m**2 + 2) // 6 % (10**9 + 7)
    return str(base * comb(n * m - 2, k - 2, exact=True) % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))


### FIXED CODE ###

mod = 10**9 + 7


def comb(n, k):
    x, y = 1, 1
    k = min(k, n - k)
    for i in range(k):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod


def solve(string):
    n, m, k = map(int, string.split())
    base = n * m * ((n + 1) * (m + 1) * (n + m - 2) - n**2 - m**2 + 2) // 6 % mod
    return str(base * comb(n * m - 2, k - 2) % mod)


if __name__ == '__main__':
    print(solve(input()))
### BUGGY CODE ###

p=1
s=[0]*2
n=int(input())
q=sorted([[int(input()),0]for i in range(n)]+[[int(input()),1]for i in range(n)])
for i in q:
    if s[(i[1]+1)%2]==0:
        s[i[1]]+=1
    else:
        p*=s[(i[1]+1)%2]
        s[(i[1]+1)%2]-=1
print(p%(10**9+7))

### FIXED CODE ###

p=1
m=10**9+7
s=[0]*2
n=int(input())
q=sorted([[int(input()),i//n]for i in range(2*n)])
for i in q:
    if s[1-i[1]]==0:
        s[i[1]]+=1
    else:
        p=(p*s[1-i[1]])%m
        s[1-i[1]]-=1
print(p)
### BUGGY CODE ###

n = int(input())
a = input().split()

ans = 1
for i in a:
    i = int(i)
    ans = ans * i
    if ans > 10 ** 18:
        ans = -1
print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)
# lS = list(map(int, list(S)))
# print(lS)

nums = [0]*(N+1)
for i in range(N):
    m = 10**(N-i-1)
    val = int(S[i]) * m
    val %= MOD
    nums[i+1] = val
# nums.append(0)
# nums.reverse()
# print(nums)

d = defaultdict(int)
d[0] += 1
cnt = 0
for i in range(N):
    nums[i+1] += nums[i]
    nums[i+1] %= MOD
    # print(nums[i+1])
    cnt += d[nums[i+1]]
    # print(d[nums[i+1]])
    d[nums[i+1]] += 1
# print(nums)
print(cnt)

### FIXED CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 2019
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

S = input()
N = len(S)

d = defaultdict(int)
d[0] += 1
# nums = [0]*(N+1)
m = 0
last = 0
dd = 1
for i in range(N):
    m += int(S[N-i-1])*dd
    m %= MOD
    # val = (int(S[i])*m + nums[i])%MOD
    # cnt += d[val]
    dd = (dd*10)%MOD
    d[m] += 1

cnt = 0
for i, v in d.items():
    cnt += v*(v-1)//2
print(cnt)
### BUGGY CODE ###

from re import sub

dest = input().rstrip("\n")

suffixes = ["dream$", "dreamer$", "erase$", "eraser$"]

while True:
    len_before = len(dest)
    for suffix in suffixes:
        dest = sub(suffix, "", dest)
    if len(dest) == len_before:
        break

print("YES" if not dest else "NO")


### FIXED CODE ###

dest = input().rstrip("\n")

suffixes = ["dream", "dreamer", "erase", "eraser"]
cut_lens = [-5, -7, -5, -6]

while True:
    for suffix, cut_len in zip(suffixes, cut_lens):
        if dest.endswith(suffix):
            dest = dest[:cut_len]
            break
    else:
        break

print("YES" if not dest else "NO")
### BUGGY CODE ###

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

at = [0]
for i in range(len(A)):
    at.append(A[i])
    if i > 0:
        at[-1] += at[i]

bt = [0]
for i in range(len(B)):
    bt.append(B[i])
    if i > 0:
        bt[-1] += bt[i]


n = 0
time = 0

for i, a in enumerate(at):
    if a > K:
        break
    for j, b in enumerate(bt):
        if a+b > K:
            break
        if a+b <= K and a+b >= time:
            time = a+b
            n = i + j

print(n)


### FIXED CODE ###

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

at = [0]
for i in range(len(A)):
    at.append(A[i])
    if i > 0:
        at[-1] += at[i]

bt = [0]
for i in range(len(B)):
    bt.append(B[i])
    if i > 0:
        bt[-1] += bt[i]


n = 0
time = 0


for i, a in enumerate(at):
    if a > K:
        break
    l = 0
    r = len(bt)-1
    while r - l > 1:
        m = (l+r)//2
        if bt[m] < K-a:
            l = m
        else:
            r = m
    if bt[r] <= K -a:
        b = bt[r]
    else:
        r -= 1
        b = bt[r]
    if i + r >= n:
        n = i + r

print(n)
### BUGGY CODE ###

from collections import deque, defaultdict
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
events = []
for _ in range(N):
    S, T, X = map(int, input().split())
    events.append((S-X, X))
    events.append((T-X, -X))
events.sort()
events = deque(events)
ans = [0] * Q
cur = []
remove = defaultdict(int)
for i in range(Q):
    D = int(input())
    while events and events[0][0] <= D:
        t, x = events.popleft()
        if x > 0:
            heappush(cur, x)
        else:
            remove[-x] += 1
    while cur and remove[cur[0]]:
        remove[cur[0]] -= 1
        heappop(cur)
    ans[i] = cur[0] if cur else -1
print(*ans, sep='\n')


### FIXED CODE ###

from collections import deque, defaultdict
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
events = [None] * (2*N)
for i in range(N):
    S, T, X = map(int, input().split())
    events[2*i] = (S-X, X)
    events[2*i+1] = (T-X, -X)
events.sort(key=lambda x: x[0])
events = deque(events)
ans = [0] * Q
cur = []
remove = defaultdict(int)
for i in range(Q):
    D = int(input())
    while events and events[0][0] <= D:
        t, x = events.popleft()
        if x > 0:
            heappush(cur, x)
        else:
            remove[-x] += 1
    while cur and remove[cur[0]]:
        remove[cur[0]] -= 1
        heappop(cur)
    ans[i] = cur[0] if cur else -1
print(*ans, sep='\n')
### BUGGY CODE ###

import itertools

N = int(input())
S = [int(c) for c in input()]
table = list(range(10))

count = 0
for p in itertools.product(table, repeat=3): # 重複を許して1~9の数値を３つならべる
    target = list(p)

    flag = False
    for i_1 in range(N-2):
        if S[i_1] == target[0]: # 1つ目の数字があったら次へ
            for i_2 in range(i_1+1, N-1):
                if S[i_2] == target[1]:
                    for i_3 in range(i_2+1, N):
                        if S[i_3] == target[2]:
                            count += 1
                            flag = True
                            break
                    
                    if flag:
                        break
            if flag:
                break

print(count)

### FIXED CODE ###

def I(): return int(input())
N = I()
S = input()
ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    if S.find(num[0])==-1:
        continue
    S1 = S[S.find(num[0])+1:]
    if S1.find(num[1])==-1:
        continue
    S2 = S1[S1.find(num[1])+1:]
    if S2.find(num[2])==-1:
        continue
    ans += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

x = input()

for i in range(0, 100000):
    x = x.replace("ST", "")
    if len(x) == 0:
        break

print(len(x))


### FIXED CODE ###

# -*- coding: utf-8 -*-

x = input()

# ペアになっていないSの数（ペアができたら-1）
sc = 0
# ペアにならなかったTの数
tc = 0

for c in x:
    if c == 'S':
        sc += 1
    elif sc >= 1:
        sc -= 1
    else:
        tc += 1

print(sc + tc)
### BUGGY CODE ###

a,b=map(int,input().split())
L=list(map(int,input().split()))
maxa=10**10*(-1)
for i in range(a-b+1):
  if sum(L[i:i+b])>maxa:
    maxa=sum(L[i:i+b])
print((maxa+b)/2)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
N,M=MAP()
L=LIST()
maxa=-(10**10)
sums=sum(L[:M])
maxa=max(maxa,sums)
for i in range(N-M):
  sums=sums-L[i]+L[i+M]
  maxa=max(maxa,sums)
print((maxa+M)/2)
### BUGGY CODE ###

import sys

def isEmpty(S):
  if len(S) == 0:
    return True

def isFull(S):
  if len(S) >= 100000:
    return True

def enqueue(x):
  if isFull(x_list_list):
    print 'Error'
  x_list_list.append(x)

def dequeue(x_list_list):
  if isEmpty(x_list_list):
    print 'Error'
  del_list = x_list_list[0]
  x_list_list.pop(0)
  return(del_list)

y = sys.stdin.readline()
a, b = y.split(" ")
a = int(a)
b = int(b)

S = []
x_list_list = []

for i in range(a):
  text = raw_input()
  x_list = text.split()
  x_list[1] = int(x_list[1])
  x_list.append(0)
  x_list_list.append(x_list)

flag = a
while flag != 0:
  if x_list_list[0][1] > b:
    x_list_list[0][1] -= int(b)
    for j in range(flag):
      x_list_list[j][2] += b
    del_list = dequeue(x_list_list)
    enqueue(del_list)
  else:
    for j in range(flag):
      x_list_list[j][2] += x_list_list[0][1]
    x_list_list[0][1] = 0
    flag -= 1
    print x_list_list[0][0],x_list_list[0][2]
    dequeue(x_list_list)
    

### FIXED CODE ###

import sys

def isEmpty(S):
  if len(S) == 0:
    return True

def isFull(S):
  if len(S) >= 100000:
    return True

def enqueue(x):
  if isFull(x_list_list):
    print 'Error'
  x_list_list.append(x)

def dequeue(x_list_list):
  if isEmpty(x_list_list):
    print 'Error'
  del_list = x_list_list[0]
  x_list_list.pop(0)
  return(del_list)

y = sys.stdin.readline()
a, b = y.split(" ")
a = int(a)
b = int(b)

S = []
x_list_list = []
run_time = 0

for i in range(a):
  text = raw_input()
  x_list = text.split()
  x_list[1] = int(x_list[1])
  x_list.append(0)
  x_list_list.append(x_list)

flag = a
while flag != 0:
  if x_list_list[0][1] > b:
    x_list_list[0][1] -= int(b)
    run_time += b
    del_list = dequeue(x_list_list)
    enqueue(del_list)
  else:
    run_time += x_list_list[0][1]
    x_list_list[0][2] = run_time
    x_list_list[0][1] = 0
    flag -= 1
    print x_list_list[0][0],x_list_list[0][2]
    dequeue(x_list_list)
### BUGGY CODE ###

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

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

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

### FIXED CODE ###

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

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

ans = 0
for a in A:
    ans += lcm // a
ans %= MOD
print(ans)
### BUGGY CODE ###

n = int(input())
a = 1
for i in range(1, n + 1):
  a *= i
  
print(a % (10 ** 9 + 7))
  

### FIXED CODE ###

n = int(input())
a = 1
for i in range(1, n+1):
  a = a * i % (10 ** 9 + 7)
print(a)
### BUGGY CODE ###

N,S=map(int,input().split())
As=list(map(int,input().split()))

MOD=998244353

d = [[0]*3001 for _ in range(3001)]
d[0][0]=1

for i in range(1,N+1):
    Ai=As[i-1]
    for j in range(S+1):
        d[i][j] += 2*d[i-1][j]
        if Ai <= j:
            d[i][j] += d[i-1][j-Ai]
        d[i][j] %= MOD
print(d[N][S])

### FIXED CODE ###

import numpy as np
N,S=map(int,input().split())
As=list(map(int,input().split()))

MOD=998244353

#d = [[0]*3001 for _ in range(3001)]
d=np.zeros((3001,3001))
d[0,0]=1

for i in range(1,N+1):
    Ai=As[i-1]
    d[i] += 2*d[i-1]
    d[i,Ai:] += d[i-1][:-Ai]
    d[i] %= MOD
print(int(d[N][S]))
### BUGGY CODE ###

h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

# print(h,w,m)
HW.sort()
# print(*HW,sep='\n')
# print('---')

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]


for i in range(m):
    # print(h,w)
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

# # print('---')
# # print(sum_h)
# # print(sum_w)
# # print('---')
sum_h.sort(reverse=True)
sum_w.sort(reverse=True)
# print(sum_h)
# print(sum_w)

max_bombs = 0
if sum_h[0][0] > sum_w[0][0]:
    for w_bombs, w_index in sum_w:
        bombs = sum_h[0][0] + w_bombs
        if [sum_h[0][1], w_index] in HW:
            bombs -= 1
        if max_bombs < bombs:
            max_bombs = bombs

else:
    for h_bombs, h_index in sum_h:
        bombs = sum_w[0][0] + h_bombs
        if [h_index, sum_w[0][1]] in HW:
            bombs -= 1
        if max_bombs < bombs:
            max_bombs = bombs

# for h_bombs, h_index in sum_h:
#     for w_bombs, w_index in sum_w:
#         bombs = h_bombs + w_bombs
#         if [h_index, w_index] in HW:
#             bombs -= 1
#         if max_bombs < bombs:
#             max_bombs = bombs
print(max_bombs)


### FIXED CODE ###

h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]
for i in range(m):
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

h_num_ix = {}
for num,ix in sum_h:
    if not num in h_num_ix:
        h_num_ix[num] = set()
    h_num_ix[num].add(ix)

w_num_ix = {}
for num,ix in sum_w:
    if not num in w_num_ix:
        w_num_ix[num] = set()
    w_num_ix[num].add(ix)

max_h_num = max(h_num_ix)
max_w_num = max(w_num_ix)

# print(sorted(HW))
# print('---')
# print(h_num_ix)
# print(w_num_ix)
# print(max_h_num)
# print(max_w_num)
# print('====')

SHW = set()
for h,w in HW:
    SHW.add((h,w))
# print(SHW)

max_num = max_h_num + max_w_num - 1
for h_ix in h_num_ix[max_h_num]:
    for w_ix in w_num_ix[max_w_num]:
        num = max_h_num + max_w_num
        # if [h_ix, w_ix] in HW: continue
        if (h_ix, w_ix) in SHW: continue
        max_num += 1
        print(max_num)
        exit()
print(max_num)