Harryxun/stf_run huggingface dataset:
N=int(input())

X_t=[]
L_t=[]
ans=0

for _ in range(N):
    x,l=map(int,input().split())
    X_t.append(x)
    L_t.append(l)

tmp=zip(X_t,L_t)
XL=sorted(tmp)

X=[]
L=[]

for x,l in XL:
    X.append(x)
    L.append(l)
    

nls=[0]
for i in range(1,N-1):
    if (X[i]+L[i]>X[i+1]-L[i+1]) and (X[i]-L[i]<X[i-1]+L[i-1]):
        ans+=1
    else:
        nls.append(i)
nls.append(N-1)
        
for i in range(len(nls)-1):
    if nls==[]:
        break
    if len(nls)==1:
        break
    if (i-2)>len(nls):
        break
    
    if X[nls[i]]+L[nls[i]]>X[nls[i+1]]-L[nls[i+1]]:
        ans+=1

if X[-1]-L[-1]<X[-2]+L[-2]:
    ans+=1
print(N-ans)

### FIXED CODE ###

N=int(input())
A=[]
ans=1
for i in range(N):
    Xi,Li=map(int,input().split())
    A.append([Xi-Li,Xi+Li])
A.sort(key=lambda x:x[1])

def interf(A1,A2):
    if A1[1]>A2[0]:
        return 1
    else:
        return 0
    
pre=A[0]
for i in range(1,N):
    if interf(pre,A[i])==0:
        ans+=1
        pre=A[i]
print(ans)
from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(set)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = {connect_to for connect_to in connect_dic[room_i] if connect_to not in next_connect.keys()}
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])

### FIXED CODE ###

from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(set)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = {connect_to for connect_to in connect_dic[room_i] if connect_to not in next_connect_dic.keys()}
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])
n, k = map(int, input().split())
sushi = []
for i in range(n):
    tmp = list(map(int, input().split()))
    sushi.append(tmp)
eaten = set() # 食べた種類を記憶(集合型)
chohuku = [] # 同じ種類で二回以上食べた寿司のスコアを記録
scores = [] # Sのスコアのリスト

sushi.sort(key=lambda x:x[1])
sushi.reverse() # sushiをおいしさの降順にソート

tmp = 0 # Sのおいしさの合計を保持
for i in range(k): # sushiを美味しい順にk個食べる
    if sushi[i][0] in eaten: # 同じ種類の寿司を食べていた場合
        chohuku.append(sushi[i][1])
    else:
        eaten.add(sushi[i][0]) # 食べた寿司の種類を記憶
    tmp += sushi[i][1] # 食べた寿司のおいしさをtmpに追加
chohuku.sort()
scores.append(tmp+len(eaten)**2) # 今のSのスコアを記憶

for i in range(k,n):
    if not sushi[i][0] in eaten:
        tmp -= chohuku.pop()
        eaten.add(sushi[i][0])
        tmp += sushi[i][1]
        scores.append(tmp+len(eaten)**2)
        
print(max(scores))
    

### FIXED CODE ###

n, k = map(int, input().split())
sushi = []
for i in range(n):
    tmp = list(map(int, input().split()))
    sushi.append(tmp)
eaten = set() # 食べた種類を記憶(集合型)
chohuku = [] # 同じ種類で二回以上食べた寿司のスコアを記録
scores = [] # Sのスコアのリスト

sushi.sort(key=lambda x:x[1])
sushi.reverse() # sushiをおいしさの降順にソート

tmp = 0 # Sのおいしさの合計を保持
for i in range(k): # sushiを美味しい順にk個食べる
    if sushi[i][0] in eaten: # 同じ種類の寿司を食べていた場合
        chohuku.append(sushi[i][1])
    else:
        eaten.add(sushi[i][0]) # 食べた寿司の種類を記憶
    tmp += sushi[i][1] # 食べた寿司のおいしさをtmpに追加
chohuku.sort()
scores.append(tmp+len(eaten)**2) # 今のSのスコアを記憶

for i in range(k,n):
    if not sushi[i][0] in eaten and chohuku != []:
        tmp -= chohuku.pop(0)
        eaten.add(sushi[i][0])
        tmp += sushi[i][1]
        scores.append(tmp+len(eaten)**2)
        
print(max(scores))
import math
        
def koch(n, p.x, p.y, q.x, q.y):
 if n == 0:
  return
         
 s.x = (p.x*2+q.x)/3
 s.y = (p.y*2+q.y)/3
 t.x = (p.x+q.x*2)/3
 t.y = (p.y+q.y*2)/3
 u.x = (t.x-s.x)*math.cos(math.pi/3) - (t.y-s.y)*math.sin(math.pi/3) + s.x
 u.y = (t.x-s.x)*math.sin(math.pi/3) + (t.y-s.y)*math.cos(math.pi/3) + s.y
        
 koch(n-1, p.x, p.y, s.x, s.y)
 print s.x, s.y
 koch(n-1, s.x, s.y, u.x, u.y)
 print u.x, u.y
 koch(n-1, u.x, u.y, t.x, t.y)
 print t.x, t.y
 koch(n-1, t.x, t.y, q.x, q.y)
 
n = input()
        
p.x = 0.0
p.y = 0.0
q.x = 100.0
q.y = 0.0
        
print p.x, p.y
koch(n, p.x, p.y, q.x, q.y)
print q.x, q.y

### FIXED CODE ###

import math
          
def koch(n, h, i, j, k):
 if n == 0:
  return
           
 sx = (h*2+j)/3
 sy = (i*2+k)/3
 tx = (h+j*2)/3
 ty = (i+k*2)/3
 ux = (tx-sx)*math.cos(math.pi/3) - (ty-sy)*math.sin(math.pi/3) + sx
 uy = (tx-sx)*math.sin(math.pi/3) + (ty-sy)*math.cos(math.pi/3) + sy
          
 koch(n-1, h, i, sx, sy)
 print sx, sy
 koch(n-1, sx, sy, ux, uy)
 print ux, uy
 koch(n-1, ux, uy, tx, ty)
 print tx, ty
 koch(n-1, tx, ty, j, k)
   
n = input()
          
px = float(0)
py = float(0)
qx = float(100)
qy = float(0)
          
print px, py
koch(n, px, py, qx, qy)
print qx, qy
N = int(input())
S = input()
sum_s = [0] * N
# [0, i) のWの数
for i in range(1, N + 1):
    if S[i - 1] == 'W':
        sum_s[i] = sum_s[i - 1] + 1
    else:
        sum_s[i] = sum_s[i - 1]
        
ans = sum_s[N + 1]
for i in range(0, N):
    lc = sum_s[i]
    rc = sum_s[N + 1] - sum_s[i + 1] 
    min(ans, lc + rc)

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
sum_s = [0] * N
sum_s[0] = 1 if S[0] == 'W' else 0
for i in range(1, N):
    if S[i] == 'W':
        sum_s[i] = sum_s[i - 1] + 1
    else:
        sum_s[i] = sum_s[i - 1]

lc = 0
rc = (N - 1) - (sum_s[N - 1] - sum_s[0])
ans = lc + rc

for i in range(1, N):
    lc = sum_s[i - 1]
    rc = (N - (i + 1)) - (sum_s[N - 1] - sum_s[i])

    ans = min(ans, lc + rc)

print(ans)
n = int(input())
s = list(map(int, input().split()))
s.sort(reverse=True)
print(s[::2] - s[1::2])


### FIXED CODE ###

n = int(input())
s = list(map(int, input().split()))
s.sort(reverse=True)
print(sum(s[::2]) - sum(s[1::2]))
import sys
import math
n = int(sys.stdin.readline())
l = list(map(int, input().split()))
dp = [math.inf] *n
dp[0] = 0
for i in range(n):
    for j in range(i+1,i+3):
        if(j<n):
            dp[j]=min(dp[j],dp[i]+abs(l[i]-l[j]))
print(dp[n-1])

### FIXED CODE ###

import sys
n = int(input())
l = list(map(int, input().split()))
dp = [sys.maxsize] *n
dp[0] = 0
for i in range(n):
    for j in range(i+1,i+3):
        if(j<n):
            dp[j]=min(dp[j],dp[i]+abs(l[i]-l[j]))
print(dp[n-1])
N, A, B = map(int, input().split())
X = list(map(int, input().split()))

ans = 0
for i in range(1, N):
    d = X[i] - X[i - 1]
    if d * A > B:
        ans += B
    else:
        ans += d * A
print(ans

### FIXED CODE ###

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

ans = 0
for i in range(1, N):
    d = X[i] - X[i - 1]
    if d * A > B:
        ans += B
    else:
        ans += d * A
print(ans)
a = int(input())
b = int(input())

answer_list = [1,2,3]
pop_list = []

for i in answer_list:
    if i == a:
        answer_list.pop(i)


for i in answer_list:
    if i == b:
        answer_list.pop(i)


print(answer_list[0])

### FIXED CODE ###

a = int(input())
b = int(input())

answer_list = [1,2,3]

answer_list.remove(a)
answer_list.remove(b)

print(answer_list[0])
N,K = map(int,input().split())
x_list = list(map(int,input().split()))

split_idx = None
for i,x in enumerate(x_list):
    if x >= 0:
        split_idx = i
        break
if split_idx == None:
    lefts = x_list
    rights = []
else:
    lefts = x_list[:split_idx]
    rights = x_list[split_idx:]

if rights[0]==0:
    K -= 1
    rights = rights[1:]

if K == 0:
    print(0)
else:
    min_time = 10**9
    for left_cnt in range(K+1):
        right_cnt = K-left_cnt
        if left_cnt > len(lefts) or right_cnt > len(rights):
            continue
        if left_cnt ==0 and right_cnt == 0:
            tmp_time = 0
        elif left_cnt == 0:
            tmp_time = rights[right_cnt-1]
        elif right_cnt == 0:
            tmp_time = -lefts[-left_cnt]
        elif -lefts[-left_cnt] >= rights[right_cnt-1]:
            tmp_time = rights[right_cnt-1]*2 + (-lefts[-left_cnt])
        else:
            tmp_time = rights[right_cnt-1] + (-lefts[-left_cnt]) * 2
        if tmp_time < min_time:
            min_time = tmp_time
    print(min_time)

### FIXED CODE ###

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

split_idx = None
for i,x in enumerate(x_list):
    if x >= 0:
        split_idx = i
        break
if split_idx == None:
    lefts = x_list
    rights = []
else:
    lefts = x_list[:split_idx]
    rights = x_list[split_idx:]

if len(rights)>0:
    if rights[0]==0:
        K -= 1
        rights = rights[1:]

if K == 0:
    print(0)
else:
    min_time = 10**9
    for left_cnt in range(K+1):
        right_cnt = K-left_cnt
        if left_cnt > len(lefts) or right_cnt > len(rights):
            continue
        if left_cnt ==0 and right_cnt == 0:
            tmp_time = 0
        elif left_cnt == 0:
            tmp_time = rights[right_cnt-1]
        elif right_cnt == 0:
            tmp_time = -lefts[-left_cnt]
        elif -lefts[-left_cnt] >= rights[right_cnt-1]:
            tmp_time = rights[right_cnt-1]*2 + (-lefts[-left_cnt])
        else:
            tmp_time = rights[right_cnt-1] + (-lefts[-left_cnt]) * 2
        if tmp_time < min_time:
            min_time = tmp_time
    print(min_time)
n,m=map(int,input().split())
l=list(map(int,input().split()))
if m==1:
  print(0)
  exit()
l.sort()
l2=[]
for i in range(len(l)-1):
  l2.append(l[i+1]-l[i])
for i in range(n-1):
  l2.remove(max(l2))
print(sum(l2))

### FIXED CODE ###

n,m=map(int,input().split())
l=list(map(int,input().split()))
if m==1:
  print(0)
  exit()
l.sort()
l2=[]
x0=l[0]
l.remove(x0)
for x in l:
  l2.append(x-x0)
  x0=x
l2.sort()
if n==1:
  print(sum(l2))
else:
  print(sum(l2[:-(n-1)]))
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

def f(A, N, K):
    A.sort()
    I = (np.abs(A)).argsort()
    A = A[I][::-1]
    if N == K:
        return A
    # 全部負
    if np.all(A < 0):
        if K % 2 == 0:
            return A[:K]
        else:
            return A[-K:]
    # これ以外の場合は、必ず正を実現できる
    pos = A[A >= 0]
    neg = A[A < 0]
    nums = [1]
    if K & 1:
        nums = [pos[0]]
        pos = pos[1:]
        K -= 1
    # K は偶数
    # pos, neg から偶数個ずつセットにする
    pos = pos[::2] * pos[1::2]
    neg = neg[::2] * neg[1::2]
    A = np.concatenate([pos, neg])
    A.sort()
    A = A[::-1]
    return np.concatenate([nums, A[:K // 2]])

MOD = 10**9 + 7
B = f(A, N, K).tolist()
ans = 1
for x in B:
    ans = ans * x % MOD
print(ans)

### FIXED CODE ###

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

def f(A, N, K):
    A.sort()
    I = (np.abs(A)).argsort()
    A = A[I][::-1]
    if N == K:
        return A
    # 全部負
    if np.all(A < 0):
        if K % 2 == 0:
            return A[:K]
        else:
            return A[-K:]
    # これ以外の場合は、必ず正を実現できる
    pos = A[A >= 0]
    neg = A[A < 0]
    nums = [1]
    if K & 1:
        nums = [pos[0]]
        pos = pos[1:]
        K -= 1
    # K は偶数
    # pos, neg から偶数個ずつセットにする
    if len(pos) & 1:
        pos = pos[:-1]
    if len(neg) & 1:
        neg = neg[:-1]
    pos = pos[::2] * pos[1::2]
    neg = neg[::2] * neg[1::2]
    A = np.concatenate([pos, neg])
    A.sort()
    A = A[::-1]
    return np.concatenate([nums, A[:K // 2]])

MOD = 10**9 + 7
B = f(A, N, K).tolist()
ans = 1
for x in B:
    ans = ans * x % MOD
print(ans)
N,M = map(int,input().split())
requests = []
for _ in range(M):
        a,b = map(int,input().split())
        requests.append([a,b])

ans = 1
requests = sorted(requests, key=lambda x:(x[1],x[0]))
b = min(requests, key=lambda x:x[1])[1]
for i in range(M):
        if requests[i][0] < b:
                continue
        else:
                ans += 1
                b = min(requests[i:], key=lambda x:x[1])[1]

print(ans)

### FIXED CODE ###

A = list(map(int,input().split()))
B = [abs(A[0]-A[1]),abs(A[0]-A[2]),abs(A[1]-A[2])]
B.sort()
print(B[0]+B[1])
s=input()
t=input()
dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
def func(i,j):
    if i>=(len(s)) or j>=(len(t)):
        dp[i][j]=0
        return dp[i][j]
    if dp[i][j]!=-1:
        return dp[i][j]
    if s[i]==t[j]:
        dp[i][j] = func(i+1,j+1)+1
        return dp[i][j]
    if s[i]!=t[j]:
        dp[i][j] = max(func(i+1,j),func(i,j+1))
        return dp[i][j]
l=func(0,0)

i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1
print(arr)


# for i in range(len(s)-1,-1,-1):
#     for j in range(len(t)-1,-1,-1):
#         if s[i] == t[j]:
#             dp[i][j] = dp[i+1][j+1] + 1
#         else:
#             dp[i][j] = max(dp[i+1][j],dp[i][j+1])
# l=dp[0][0]

### FIXED CODE ###

s=input()
t=input()

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
for i in range(len(s),-1,-1):
    for j in range(len(t),-1,-1):
        if i>=(len(s)) or j>=(len(t)):
            dp[i][j] = 0
        else:
            if s[i] == t[j]:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = max(dp[i+1][j],dp[i][j+1])

l=dp[0][0]
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)
h, w, n = [int(i) for i in input().split()]
if n == 0:
  for i in range(10):
    print(0)
    exit(0)
a, b = zip(*
  [[int(i) for i in input().split()] for j in range(n)])

board = [[0]*(w+1) for i in range(h+1)]

ans = [0] * 10
ans[0] = min(0, (h-2)) * min(0, (w-2))

for a, b in zip(a, b):
  for i in range(max(2, a-1), min(h, a+2)):
    for j in range(max(2, b-1), min(w, b+2)):
      try:
        ans[board[i][j]] -= 1
        board[i][j] += 1
        ans[board[i][j]] += 1
      except:
        pass

for i in range(10):
  print(ans[i])

### FIXED CODE ###

h, w, n = [int(i) for i in input().split()]
if n == 0:
  a = b = [0] 
else:
  a, b = zip(*
  [[int(i) for i in input().split()] for j in range(n)])

board = { }

ans = [0] * 10
ans[0] = max(0, (h-2)) * max(0, (w-2))

for a, b in zip(a, b):
  for i in range(max(2, a-1), min(h, a+2)):
    for j in range(max(2, b-1), min(w, b+2)):
      try:
        ans[board.get((i, j), 0)] -= 1
        board[(i, j)] = board.get((i, j), 0) + 1
        ans[board[(i, j)]] += 1
      except:
        pass

for i in range(10):
  print(ans[i])
cnt = 0
zorome = 0
num = input()

while cnt < num:
  mass = input().split()
  
  if(mass[0] == mass[1]):
    zorome += 1
    
    if(zorome >= 3):
      break
  else:
    zorome = 0
  
  cnt += 1

print("Yes" if zorome >= 3 else "No")


### FIXED CODE ###

cnt = 0
zorome = 0
num = int(input())

while cnt < num:
  mass = input().split()
  
  if(mass[0] == mass[1]):
    zorome += 1
    
    if(zorome >= 3):
      break
  else:
    zorome = 0
  
  cnt += 1

print("Yes" if zorome >= 3 else "No")
r = input()
s = 3 * (r ** 2)
print("s")

### FIXED CODE ###

r = int(input())
s = 3 * r * r
print(s)
# C
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]

da, db, dc = 0, 0, 0

for a, b, c in abc:
    na = max(db, dc) + a
    na = max(da, dc) + a
    na = max(da, db) + a
    
print(max([na, nb, nc]))

### FIXED CODE ###

# C
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]

da, db, dc = 0, 0, 0

for a, b, c in abc:
    na = max(db, dc) + a
    nb = max(da, dc) + b
    nc = max(da, db) + c
    da = na
    db = nb
    dc = nc
    
print(max([na, nb, nc]))
n,m = map(int,input().split())
lis = [0]*n+1
a = []
for i in range(m):
    a.append(int(input()))
    
mod = 10**9+7
ans = 0
if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    else:
        print(2)
else:
    if 1 in a and 2 in a:
        print(0)
    elif 1 in a:
        lis[1] = 1
    elif 2 in a:
        lis[0] = 1
    else:
        lis[0] = 1
        lis[1] = 2
    
    for j in range(3,n+1):
        if j in a:
            lis[0] = lis[1]
            lis[1] = 0
        else:
            ans = lis[0]%mod + lis[1]%mod
            lis[0] = lis[1]
            lis[1] = ans
        
        if lis[0] == 0 and lis[1] == 0:
            ans = 0
            break
        

    print(ans%mod)

### FIXED CODE ###

n,m = map(int,input().split())
lis = [False]*(n+1)
a = []
for i in range(m):
    a = int(input())
    lis[a] = True

mod = 10**9+7
dp =[0]*(n+1)
dp[0] =1
for i in range(n):
    dp[i] %= mod
    if (lis[i]):dp[i] = 0
    if i+1 <=n:
        dp[i+1] += dp[i]
    if i+2 <=n:
        dp[i+2] += dp[i]

print(dp[n]%mod)
a = int(input())
s = input()

if a >= 3200:
  print('red')
elsd:
  print(s)

### FIXED CODE ###

a = int(input())
s = input()

if a < 3200:
  print('red')
else:
  print(s)
import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]

import math
dp = [math.inf] * (h + 10 ** 4)
dp[0] = 0

for j in range(h):
  for a, b in ab:
    dp[j + a] = min(dp[j + a], dp[j] + b)

dprint(dp[:10])
print(min(dp[h:]))


### FIXED CODE ###

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]

INF = 2 ** 64
dprint(INF)
dp = [INF] * (h + 10 ** 4)
dp[0] = 0

for j in range(h):
  for a, b in ab:
    dp[j + a] = min(dp[j + a], dp[j] + b)

dprint(dp[:10])
print(min(dp[h:]))
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
from scipy.special import comb
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()

a.sort(reverse = True)
res = 0
for i in range(n-k+1):
    res += a[i] * comb(n-i-1, k-1, exact=True)

a.reverse()
for i in range(n-k+1):
    res -= a[i] * comb(n-i-1, k-1, exact=True)

print(res%MOD)


### FIXED CODE ###

import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()

def mpow(a, n):
    if n == 0:return 1
    if n == 1:return a%MOD
    if n%2 == 1:return (a%MOD * mpow(a, n-1)%MOD)%MOD
    t = mpow(a, n//2)
    return (t*t)%MOD

fac = [1]*(n+1)
inv_fac = [1]*(n+1)
for i in range(n):
    fac[i+1] = (fac[i]*(i+1))%MOD
inv_fac[n] = mpow(fac[n], MOD-2)
for i in range(n, 0, -1):
    inv_fac[i-1] = (inv_fac[i]*i)%MOD

def cmb(n, r):
    if n == 0 and r == 0:return 1
    if n<r or n<0:return 0
    return (fac[n]*(inv_fac[r]*inv_fac[n-r])%MOD)%MOD
 
a.sort(reverse = True)
res = 0
for i in range(n-k+1):
    res += (a[i]*cmb(n-i-1, k-1))%MOD
    res = res%MOD
 
a.reverse()
for i in range(n-k+1):
    res -= (a[i]*cmb(n-i-1, k-1))%MOD
    res = res%MOD
 
print(res)
n,k=map(int,input().split())
lists=list(map(int,input().split()))
a=format(k,"b")
length=max(len(a),len(format(max(lists),"b")))
uselists=[0]*length
for some in lists:
    check=format(some,"0%ib"%length)
    for i in range(length):
        if check[i]=="1":
            uselists[length-1-i]+=1         
if k>=1:
    order=0
    for i in range(length):
        if  2**i<=k<2**(i+1):
            order=i
            break            
    ans1=0
    ans2=0
    for j in range(order):
        ans1+=(2**j)*max(uselists[j],n-uselists[j])
        
    for j in range(order+1,length):
        ans2+=(2**j)*uselists[j]
    ans2+=(2**order)*(n-uselists[order])
    bigger=0
    newlist=[0]*(k-2**order+1)
    for g in range(0,k-2**order+1):
        some=format(g,"0%ib"%order)
        newlist[g]=some
    for some in newlist:
        checker=0
        for i in range(order):
            if some[i]=="1":
                checker+=(2**(order-1-i))*(n-uselists[i])
            else:
                checker+=(2**(order-1-i))*uselists[i]
        bigger=max(bigger,checker)  
    ans2=ans2+bigger
    print(max(ans1,ans2))
    
elif k==0:
    ans=0
    for i in range(length):
        if uselists[i]=="1":
            ans+=(2**i)*(n-uselists[i])
        else:
            ans+=(2**i)*uselists[i]     
    print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
k2=format(k+1,"0%ib"%40)
lists=list(map(int,input().split()))
countlist=[0]*40
for j in lists:
    c=format(j,"0%ib"%40)
    for i in range(40):
        if c[i]=="1":
            countlist[i]+=1

emptylist=[]
for i in range(40):
    if k2[i]=="1":
        emptylist.append(i)
if k>=1:
    ans=0
    for i in emptylist:
        subing=0
        for j in range(40):
            if j<i:
                if k2[j]=="1":
                    subing+=(2**(39-j))*(n-countlist[j])
                elif k2[j]=="0":
                    subing+=(2**(39-j))*countlist[j]
            if j==i:
                subing+=(2**(39-i))*countlist[i]
            
            if j>i:
                subing+=(2**(39-j))*max(countlist[j],n-countlist[j])
        ans=max(ans,subing)
    print(ans)
elif k==0:
    ans=0
    for i in range(40):
        ans+=(2**(39-i))*countlist[i]
    print(ans)
n, k = map(int,input().split())
print(n,k)

l = list(map(int,input().split()))

dp = [[0] * 2 for i in range(n)]

ans = l[:]

if k > 10**:
    k = 100
    
for i in range(k):
    for j in range(n):
        dp[j][0] = (j+1 - ans[j] - 0.5)
        dp[j][1] = (j+1 + ans[j] + 0.5)

    ans = [0] * n

    for x in range(n):
        for y in range(n):
            if dp[y][0] <= x+1 <= dp[y][1]:
                ans[x] += 1

else:
    print(*ans)


### FIXED CODE ###

import numpy as np
from numba import njit

@njit #処理の並列化

def imos(n, a):
    
    l=np.zeros((n+1), dtype = np.int64)

    for i in range(n):
        ai = a[i] # 光の強さ_これにより照らせる範囲が決まる
        start = max(0, i - ai) #StartIndex_照らせる範囲
        end = min(n, i + ai + 1) #EndIndex + 1_照らせる範囲
        l[start] += 1 # 各々を'+1'と'-1'で表し...
        l[end] -= 1
    return np.cumsum(l)[:n] # 累積和をとる_cumulative sum

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

for _ in range(k):
    a = imos(n, a)
    if a.min() == n: # すべての要素が最大値'n'になるとbreak
        break

print(*a)