Harryxun/stf_run huggingface dataset:
# https://atcoder.jp/contests/abc107/tasks/arc101_a

import itertools
import collections
import bisect

def main():
    # big value
    INF = int(1e15)

    N, K = map(int, input().split())
    X = [-INF] + list(map(int, input().split())) + [INF]
    pos = bisect.bisect(X, 0) # 右にあって0に一番近い要素のインデックス
    # print(pos)

    ans = INF
    if N - pos + 1 >= K: # 右側からだけ取れるなら
        ans = min(ans, abs(X[pos + K - 1]))
    # print(ans)
    if pos - 1 >= K: # 左側からだけ取れるなら
        ans = min(ans, abs(X[pos - K]))
    # print(ans)

    for i in range(1, K):  # 左側からいくつ取るか
        if i > pos - 1:  # 左側に取れるだけ数がないなら continue
            continue
        # min(一番左までの距離 x 往復 + 一番右までの距離, 一番右までの距離 x 往復 + 一番左までの距離)
        ans = min(ans, abs(X[pos - i]) * 2 + abs(X[pos + K - i - 1]))
        ans = min(ans, abs(X[pos + K - i - 1]) * 2 + abs(X[pos - i]))

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/abc107/tasks/arc101_a

import itertools
import collections
import bisect

def main():
    # big value
    INF = int(1e15)

    N, K = map(int, input().split())
    X = [-INF] + list(map(int, input().split())) + [INF]
    pos = bisect.bisect(X, 0) # 0より大きい中で最小の要素のインデックス
    # print(pos)

    right_num = N - pos + 1
    left_num = pos - 1

    ans = INF
    if right_num >= K:  # 右側からだけ取れるなら
        ans = min(ans, abs(X[pos + K - 1]))
    # print(ans)

    for i in range(1, K):  # 左側からいくつ取るか
        if i > left_num:  # 左側に取れるだけ数がないなら continue
            continue
        if K - i > right_num:  # 右側に取れるだけ数がないなら continue
            continue

        left_distance = abs(X[pos - i])
        right_distance = abs(X[pos + K - i - 1])
        # min(一番左までの距離 x 往復 + 一番右までの距離, 一番右までの距離 x 往復 + 一番左までの距離)
        ans = min(ans, left_distance * 2 + right_distance, right_distance * 2 + left_distance)

    if left_num >= K:  # 左側からだけ取れるなら
        ans = min(ans, abs(X[pos - K]))
    # print(ans)

    print(ans)


if __name__ == '__main__':
    main()
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math

N,M=map(int,input().split())
xyz=[list(map(int,input().split())) for m in range(N)]
dp=[[0 for i in range(M)] for i in range(N)]
num=0
for a in [-1,1]:
    for b in [-1,1]:
        for c in [-1,1]:
            dp=[[0 for i in range(M)] for i in range(N)]
            for i in range(0,N):
                x,y,z=xyz[i]
                A=x*a+y*b+z*c
                for m in range(M):
                    if i==0:
                        dp[i][m]=max(A,dp[i][m])
                    else:
                        if m==0:
                            dp[i][m]=max(dp[i-1][m],A)
                        else:
                            dp[i][m]=max(dp[i-1][m-1]+A,dp[i-1][m])
            num=max(dp[-1][-1],num)
print(num)


### FIXED CODE ###

# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math

N,M=map(int,input().split())
xyz=[list(map(int,input().split())) for m in range(N)]
dp=[[[0,0] for i in range(M)] for i in range(N)]
if M==0:
    print(0)
    exit()
num=0
for a in [-1,1]:
    for b in [-1,1]:
        for c in [-1,1]:
            dp=[[None for m in range(M)] for i in range(N)]
            for i in range(0,N):
                x,y,z=xyz[i]
                A=x*a+y*b+z*c
                #print(dp)
                if i==0:
                    dp[i][0]=A
                else:
                    for m in range(0,M):
                        if m==0:
                            dp[i][m]=max(dp[i-1][m],A)
                        else:
                            if dp[i-1][m]:
                                dp[i][m]=max(dp[i-1][m-1]+A,dp[i-1][m])
                            elif dp[i-1][m-1]:
                                dp[i][m]=dp[i-1][m-1]+A
                            else:
                                break
            if dp[-1][-1]:
                num=max(dp[-1][-1],num)
print(num)
a, b = map(int, input().split())

if 1 <= a and a <= 9 and <= b and b <= 9:
  print(a*b)
else:
  print(-1

### FIXED CODE ###

a, b = map(int, input().split())

if 1 <= a and a <= 9 and 1<= b and b <= 9:
  print(a*b)
else:
  print(-1)
N=int(input())
A=list(map(int,input().split()))
print(*A[::-2],*A[N%2::2])

### FIXED CODE ###

from collections import deque
 
N = int(input())
A = [int(i) for i in input().split()]
 
B = deque(maxlen=2*10**5)
 
if N % 2 == 0:
    for i in range(N):
        if i % 2 == 0:
            B.append(A[i])
        else:
            B.appendleft(A[i])
else:
    for i in range(N):
        if i % 2 == 0:
            B.appendleft(A[i])
        else:
            B.append(A[i])
 
print(*B)
n, m = map(int, input().split())
a = list(input().split())

for i in range(len(a)):
    n = n - int(a[i])

if n >= 0:
    print(n)
else:
    print(-1)


### FIXED CODE ###

def isKaibun(str):
    for i in range(len(str)):
        if str[i] != str[len(str)-i-1]:
            return False
    return True

s = input()

if not isKaibun(s):
    print("No")
elif not isKaibun(s[0:int((len(s) - 1) / 2)]):
    print("No")
elif not isKaibun(s[int((len(s) + 3) / 2)-1:len(s)]):
    print("No")
else:
    print("Yes")
import numpy as np
n,l=int(input()),list(map(float,input().split()))
dp=np.full([n+1,n+1],0.0)
dp[0][0]=1.0
for i in range(1,n+1):
    for j in range(i+1):
        if j==0:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
a=0.0
for i in range((n+1)//2,n+1):
  	a+=dp[n][i]
print(a)

### FIXED CODE ###

n,l=int(input()),list(map(float,input().split()))
dp=[[0.0]*(n+1) for _ in range(n+1)]
dp[0][0]=1.0
for i in range(1,n+1):
    for j in range(i+1):
        if j==0:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
print(sum(dp[n][((n+1)//2):]))
A, B = map(int, input().split())

if (a * b) % 2 == 0 :
  print('yes')
else :
  print('no')

### FIXED CODE ###

A, B = map(int, input().split())
 
if (A * B) % 2 == 0 :
  print('No')
else :
  print('Yes')
N = int(input())


def kakuinowa(n):
    a = str(n)
    s = 0
    for i in range(len(a)):
        s = s + int(a[i])
    return s

import math
m = kakuinowa(N)
for i in range(int(math.log10(N)) + 1):
    n = kakuinowa((N // 10**i) * 10**i - 1)
    if n > m:
        m = n


print(m)


### FIXED CODE ###

a = input()
a = list(a)
l = len(a)
for i in range(l):
    a[i] = int(a[i])
m = sum(a)
for i in range(l):
    n = a[i]-1 + 9*(l-i-1)
    if n > m:
        m = n
print(m)
S = list(input())
T = list(input())

N = len(S)
M = len(T)

ans = 'UNRESTORABLE'

if N < M:
    print(ans)
    exit()

if N == M:
    ans = S
    for i in range(N):
        if S[i] == '?':
            S[i] = T[i]
        else:
            if S[i] != T[i]:
                ans = 'UNRESTORABLE'
    print(ans)
    exit()

for i in range(N-M,-1,-1):
    b = True
    for j in range(M):
        if S[i+j] == '?' or S[i+j] == T[j]:
            continue
        b = False
    if b:
        ans = S[:i] + T + S[i+j+1:]
for i in range(N):
    if ans[i] == '?':
        ans[i] = 'a'
print(''.join(ans))


### FIXED CODE ###

S = list(input())
T = list(input())
lenS = len(S)
lenT = len(T)
change = 0
for i in range(lenS-lenT,-1,-1):
    a = 1
    for j in range(lenT):
        if S[i+j] != T[j] and S[i+j] != '?':
            a = 0
    if a == 1:
        for j in range(lenT):
            S[i+j] = T[j]
        change = 1
        break

for i in range(lenS):
    if S[i] == '?':
        S[i] = 'a'

if change == 1:
    print(''.join(S))
else:
    print('UNRESTORABLE')
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
MOD = 10**9 + 7
def comb(n, k, p):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    k=k if k<=n-k else n-k
    for i in range(k):
        x=x*(n-i)%mod
        y=y*(i+1)%mod
    return (x*pow(y,mod-2,mod))%mod
n,a,b = map(int,input().split())
A = comb(n,a,MOD)
B = comb(n,b,MOD)
C = pow(2,n,MOD)
ans = C -A-B-1
print(ans%MOD)

### FIXED CODE ###

import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
MOD = 10**9 + 7
def comb(n, k, mod):
    if n<0 or k<0 or n<k:
        return 0
    if n==0 or k==0:
        return 1
    k=k if k<=n-k else n-k
    x = 1
    y = 1
    for i in range(k):
        x=x*(n-i)%mod
        y=y*(i+1)%mod
    return (x*pow(y,mod-2,mod))%mod
n,a,b = map(int,input().split())
A = comb(n,a,MOD)
B = comb(n,b,MOD)
C = pow(2,n,MOD)
ans = C -A-B-1
print(ans%MOD)
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
l.sort(key=lambda x:x[1])
lb=0
ans=0
for a,b in l:
    if a>=lb:
        lb=b
        ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
l.sort(key=lambda x:x[1])
lb=0
c=0
for a,b in l:
    if a>=lb:
        lb=b
        c+=1
print(c)
n=int(input())
l=list(map(int,input().split()))
b=[]
ans=0
for i in range(n)[::-1]:
  c=n//(i+1)
  s=0
  while (c+1)*(i+1)<=n:
    s+=l[(c+1)*(i+1)]
    c+=1
    s%=2
  if l[i]!=s:
    b.append(i+1)
    ans+=1
print(ans)
print(" ".join(b))

### FIXED CODE ###

n=int(input())
balls=list(map(int,input().split()))
ans=[0]*n;m=0;al=[]
for i in range(n)[::-1]:
  d=i+1
  c=n//d
  mal=2
  check=0
  while d*mal<=n:
    check+=ans[d*mal-1]
    mal+=1
  check%=2
  if check!=balls[i]:
    ans[i]=1
    al.append(str(d))
    m+=1
print(m)
print(" ".join(al))
n,m = map(int,input().split())
#L = [list(map(int,input().split())) for i in range(m)]


class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]
#a = [i+1 for i in range(n)]
d = Unionfind(n)

for i in range(m):
    a,b = map(int,input().split())
    d.union(a,b)
max1 = 0
for i in range(n):
    max1 = max(max1,d.size(i))
print(max1-1)


### FIXED CODE ###

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

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]
#a = [i+1 for i in range(n)]
d = Unionfind(n)

for i in range(m):
    a,b = map(int,input().split())
    d.union(a-1,b-1)
    
L = []
for i in range(n):
    c = d.find(i)
    L.append(c)
#print(L)
print(len(set(L))-1)
n = int(input())
a = list(map(int,input().split))
ans = [0] * n
for i in range(n):
    ac = a
    del ac[i]
    for j in range(0, n):
        if j == 0:
            ans[i] += abs(ac[0])
        else:
            ans[i] += abs(ac[j]-ac[j - 1])

for k in ans:
    print(str(k))

### FIXED CODE ###

n = int(input())
a = [0] + list(map(int,input().split())) + [0]
ans = 0
anslist = [0] * n
for j in range(1, n + 2):
    if j == 1:
        ans += abs(a[j])
    elif j == n + 1:
        ans += abs(a[n])
    else:
        ans += abs(a[j]-a[j - 1])

for i in range(1, n + 1):
    anslist[i - 1] = ans - abs(a[i - 1] - a[i]) - abs(a[i] - a[i + 1]) + abs(a[i - 1] - a[i + 1])
            
for k in anslist:
    print(k)
L, R = map(int, input().split())

mod = []
if 2019 <= R - L:
    print(0)
else:
    for i in range(L, R):
        j = i + 1
        mod.append((i * j % 2019))

print(min(mod))

### FIXED CODE ###

L, R = map(int, input().split())
 
if 2019 <= R - L:
    print(0)
else:
    a=min([(i*j)%2019 for i in range(L,R+1) for j in range(i+1,R+1)])
    print(a)
a,b=map(int,input().split())
if a>b:print(1)
  elif a==b:print(1)
    elif a<b and b%a==0:print(b//a)
      elif b==0:print(0)
        else:print(b//(a+1))

### FIXED CODE ###

a,b=map(int,input().split())
if b==1:print(0)
elif a==b:print(1)
else:
    if (b-1)%(a-1)>0:print((b-1)//(a-1)+1)
    else:print((b-1)//(a-1))
values = input()
values = [int(x) for x in values]
 
sum = 0
 
for val in values:
  sum += val
  
if sum >= 22:
  print("bust")
else:
  print("win")

### FIXED CODE ###

values = input().split()
values = [int(x) for x in values]

sum = 0

for val in values:
    sum += val

if sum >= 22:
    print("bust")
else:
    print("win")
import sys


def isprime(n):
    '''check if integer n is a prime'''

    # make sure n is a positive integer
    n = abs(int(n))

    # 0 and 1 are not primes
    if n < 2:
        return False

    # 2 is the only even prime number
    if n == 2: 
        return True    

    # all other even numbers are not primes
    if not n & 1: 
        return False

    # range starts with 3 and only needs to go up 
    # the square root of n for all odd numbers
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False

    return True


max = sys.stdin.readline()
answer = []

for x in range(max):
    n = sys.stdin.readline()
    if isprime(int(n)):
        answer.append(n)

print(' '.join(answer))

### FIXED CODE ###

import sys


def isprime(n):
    '''check if integer n is a prime'''

    # make sure n is a positive integer
    n = abs(int(n))

    # 0 and 1 are not primes
    if n < 2:
        return False

    # 2 is the only even prime number
    if n == 2: 
        return True    

    # all other even numbers are not primes
    if not n & 1: 
        return False

    # range starts with 3 and only needs to go up 
    # the square root of n for all odd numbers
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False

    return True


max = int(sys.stdin.readline())
answer = 0

for x in range(max):
    n = sys.stdin.readline()
    if isprime(int(n)):
        answer += 1

print(answer)
for a in range(-int(math.pow(x,1./3.)),int(math.pow(x,1./3.))+1):
    for b in range(-int(math.pow(x,1./3.))+1,int(math.pow(x,1./3.))+1):
        if a!=b:
            if x/(a-b) == a*a*a*a+a*a*a*b+a*a*b*b+a*b*b*b+b*b*b*b:
                print(a,b)
                break
    else:
        continue
    break

### FIXED CODE ###

x = int(input())

import math

for a in range(-int(math.pow(x,1./3.)),int(math.pow(x,1./3.))+1):
    for b in range(-int(math.pow(x,1./3.))+1,int(math.pow(x,1./3.))+1):
        if a!=b:
            if x/(a-b) == a*a*a*a+a*a*a*b+a*a*b*b+a*b*b*b+b*b*b*b:
                print(a,b)
                break
    else:
        continue
    break
S = input()
if 'hi' in S:
    print 'Yes'
elif:
    print 'No'

### FIXED CODE ###

S = raw_input()

length = len(S)
if length % 2 == 0:
  if S.count('hi')==length/2:
    print("Yes")
  else:
    print("No")
else:
  print("No")
t = int(input())
for i in range(t):
    able = "Yes"
    a,b,c,d = map(int, input().split())
    if a - b < 0:
        able = "No"
    else:
        x = c+(a-c)%b
        if x <= c:
            x+=d
        for i in range(1200):
            x-=b
            if x >= 0:
                if x <= c:
                    x+=d
            else:
                able = "No"
                break
    print(able)

### FIXED CODE ###

n = int(input())
a= list(input().split())
res = 0
for i in range(n-1):
    if a[i] == a[i+1]:
        a[i+1]=10001
        res +=1
print(res)
import numpy as np
import math
n = int(input())
l = np.empty(floor(n ** 0.5))
l = np.nan

k = 0
for i in range(1,floor(n ** 0.5)):
  if n % i == 0:
    l[k] = i + n // i - 2
    k += 1
print(int(np.nanmin(l)))

### FIXED CODE ###

n = int(input())

for i in range(int(n ** 0.5)):
  if n % (int(n ** 0.5) - i) == 0:
    j = n // (int(n ** 0.5) - i)
    break
    
print(int(n ** 0.5) - i + j - 2)
import collections
n=int(input())
a=sorted(list(collections.Counter(map(int,input().split())).items()), key=lambda x: x[0])
b=sorted(list(collections.Counter(map(int,input().split())).items()), key=lambda x: x[0])
c=sorted(list(collections.Counter(map(int,input().split())).items()), key=lambda x: x[0])

bc=[0]*len(b)
j=0
tmp=sum(i[1] for i in c)
for i,x in enumerate(b):
  while j<n and x[0]>=c[j][0]:
    tmp-=c[j][1]
    j+=1
  bc[i]=tmp

abc=[0]*len(a)
j=0
tmp=sum(i[1]*j for i,j in zip(b,bc))

for i,x in enumerate(a):
  while j<n and x[0]>=b[j][0]:
    tmp-=b[j][1]*bc[j]
    j+=1
  abc[i]=tmp
ans=sum(i[1]*j for i,j in zip(a,abc))
#print(a,b,c,bc,abc,sep="\n")
print(ans)


### FIXED CODE ###

import collections
n=int(input())
a=sorted(list(collections.Counter(map(int,input().split())).items()), key=lambda x: x[0])
b=sorted(list(collections.Counter(map(int,input().split())).items()), key=lambda x: x[0])
c=sorted(list(collections.Counter(map(int,input().split())).items()), key=lambda x: x[0])
la=len(a)
lb=len(b)
lc=len(c)
bc=[0]*lb
j=0
tmp=sum(i[1] for i in c)
for i,x in enumerate(b):
  while j<lc and x[0]>=c[j][0]:
    tmp-=c[j][1]
    j+=1
  bc[i]=tmp

abc=[0]*la
j=0
tmp=sum(i[1]*j for i,j in zip(b,bc))
for i,x in enumerate(a):
  while j<lb and x[0]>=b[j][0]:
    tmp-=b[j][1]*bc[j]
    j+=1
  abc[i]=tmp
ans=sum(i[1]*j for i,j in zip(a,abc))
#print(a,b,c,bc,abc,sep="\n")
print(ans)
n = int(input())
a = map(int,input().split())
res = 0
for i in range(n):
  for j in range(i+1,n):
    res += a[i]*a[j]
print(res)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
res = 0
for i in range(n):
  for j in range(i+1,n):
    res += a[i]*a[j]
print(res)
import itertools

import numpy as np

H, W, M = map(int, input().split())
HW = [list(map(int, input().split())) for _ in range(M)]
F = np.zeros([H, W], dtype=np.int64)

for h, w in HW:
    F[h - 1, w - 1] = 1

# 各方向の和を計算
A = np.sum(F, axis=0)
B = np.sum(F, axis=1)

maxA = np.max(A)
maxB = np.max(B)
print('h')

"""
# 最大値を取るindex
ind_A = np.arange(W)[A == maxA]
ind_B = np.arange(H)[B == maxB]

cnt = 0
ans = maxA + maxB
for h, w in itertools.product(ind_B, ind_A):
    if F[h, w] == 0:
        break

    cnt += 1
    if cnt == M:
        ans -= 1
        break
else:
    ans -= 1
print(ans)
"""


### FIXED CODE ###

import itertools

import numpy as np


def main():
    H, W, M = map(int, input().split())
    HW = [list(map(int, input().split())) for _ in range(M)]

    A = np.zeros(H, dtype=np.int64)
    B = np.zeros(W, dtype=np.int64)

    for h, w in HW:
        A[h - 1] += 1
        B[w - 1] += 1

    maxA = np.max(A)
    maxB = np.max(B)

    # 最大値を取るindex
    ind_A = np.arange(H)[A == maxA]
    ind_B = np.arange(W)[B == maxB]

    # 解の候補の数
    nn = len(ind_A) * len(ind_B)

    # Mより候補の数のほうが多いとok
    # 少ないときはM以下なので可算
    ans = maxA + maxB

    if nn <= M:
        for h, w in HW:
            if A[h - 1] == maxA and B[w - 1] == maxB:
                nn -= 1

    print(ans if nn else ans - 1)


main()
K = input()
D = int(input())
dp = [[0] * D for _ in range(len(K))]
mod = 10 ** 9 + 7
for i in range(int(K[0])):
  dp[0][i % D] = 1
tight = int(K[i]) % D
if len(K) > 1:
  for i in range(len(K)):
    for j in range(D):
      for k in range(10):
        dp[i + 1][(j + k) % D] += dp[i][j]
        dp[i + 1][(j + k) % D] %= mod
  for k in range(int(K[i])):
    dp[i][(tight + k) % D] += 1
  tight = (tight + int(K[i])) % D
print((dp[len(K) - 1][0] + (tight == 0) - 1) % mod)

### FIXED CODE ###

K = input()
D = int(input())
dp = [[0] * D for _ in range(len(K))]
mod = 10 ** 9 + 7
#桁DP
#0 ~ K[0] - 1までの数をトップとする場合
for i in range(int(K[0])):
  dp[0][i % D] += 1
#tightは上限付近の制御に使う
#K[0]をトップとする場合がtight
#tightは上限ギリギリを攻める
tight = int(K[0]) % D
if len(K) > 1:
  for i in range(len(K) - 1):
    for j in range(D):
      for k in range(10):
        dp[i + 1][(j + k) % D] += dp[i][j]
        dp[i + 1][(j + k) % D] %= mod
    #Kを超えないようにしている
    for k in range(int(K[i + 1])):
      dp[i + 1][(tight + k) % D] += 1
    #上から(i + 1)桁まで見たもので、上限ギリギリのものの剰余
    tight = (tight + int(K[i + 1])) % D
#tightは最終的に上限の剰余に一致するので、0でないならその分を除く
print((dp[len(K) - 1][0] + (tight == 0) - 1) % mod)
n = int(input())
lst1 = list(map(int,input().split()))
mod = 10**9+7

import math
#リスト l の最大公約数
def lcmlist(l):
    a = l[0]
    for i in range(len(l)):
        a = int(a)
        a = a*l[i]/math.gcd(a,l[i])
    return int(a)

g = lcmlist(lst1)
ans = 0
for i in range(n):
    ans += g//lst1[i]%mod

print(ans%mod)

### FIXED CODE ###

n = int(input())
lst1 = list(map(int,input().split()))
mod = 10**9+7
 
def GCD(a,b):
    if b == 0:
        return a
    else:
        return GCD(b,a%b)
def LCM(a,b):
    return (a//GCD(a,b)*b)

l = 1
for i in lst1:
    l = LCM(l,i)

ans = 0
for i in range(n):
    ans += l//lst1[i]
 
print(ans%mod)
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]
ans = [0] * N

for _ in range(M):
	a, b = map(int, input().split())
	friend[a - 1].append(b - 1)
	friend[b - 1].append(a - 1)
	
for _ in range(K):
	c, d = map(int, input().split())
	block[c - 1].append(d - 1)
	block[d - 1].append(c - 1)
	

def dfs(start, i):
	global visited
	global friend
	global block
	global ans
	visited[i] = 1
	for adj in friend[i]:
		if visited[adj]: continue
		if not adj in friend[start] and not adj in block[start]:
			ans[start] += 1
		dfs(start, adj)
		
	
for i in range(N):
	visited = [0] * N
	dfs(i, i)
	
print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]

for _ in range(M):
	a, b = map(int, input().split())
	friend[a - 1].append(b - 1)
	friend[b - 1].append(a - 1)
	
for _ in range(K):
	c, d = map(int, input().split())
	block[c - 1].append(d - 1)
	block[d - 1].append(c - 1)
	
# 同じ連結成分にラベルを振る（まだラベルを振っていない = -1 で初期化）
label = [-1] * N

cnt_label_num = 0

for i in range(N):
	if label[i] != -1: continue # もう振ってあったら飛ばす
	
	# 振ってなかったら幅優先でラベルを振る
	Q = [i]
	while Q:
		cur = Q.pop()
		if label[cur] != -1: continue
		label[cur] = cnt_label_num
		for adj in friend[cur]:
			if label[adj] != -1: continue
			Q.append(adj)
	
	cnt_label_num += 1
	
# お友達候補計算
cnt = Counter(label)
for i in range(N):
	friend_candidate = cnt[label[i]] - 1 # 同じグラフにいる人
	friend_candidate -= len(friend[i]) # 元から友達を引く
	# blockしている人が同じグラフにいるときはその分引く
	for block_man in block[i]:
		if label[i] == label[block_man]:
			friend_candidate -= 1
	print(friend_candidate, end = " ")