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

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	#b , c = IN()
	s = input()
	
	ll=len(s)
	ret_count=0
	for i in range(ll-2):
		v = int(s[i:i+3])
		for c in s[i+3:]:
			v = (v * 10 + int(c))% 2019
			if v == 0:
				#print(i,j,s[i:j])
				#print(s[i:i+3],'aaa')
				ret_count += 1
	print(ret_count)
				
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main2():
	#a = int(input())
	#b , c = IN()
	s =  input()
	#s='1'*3000
	s=[int(c) for c in s]
	ll=len(s)
	ret_count=0
	for i in range(1):#ll-2):
		v = s[i]
		vs=[v]
		for c in s[i+1:]:
			v = (v * 10 + c) % 2019
			vs.append(v)
			if v == 0:
				ret_count += 1
		else:
			pa(vs)	
	print(ret_count)
				
def main():
	#a = int(input())
	#b , c = IN()
	s =  input()
	#s='1'*3000
	s=[int(c) for c in s]
	s=s[::-1]
	ll=len(s)
	cc=[0]*2019
	p=0
	tt=1
	cc[0]=1
	for i, v in enumerate(s):
		tt *= 10
		tt %= 2019
		p += tt*v
		p %= 2019
		cc[p] += 1
	
	ret = 0
	for v in cc:
		ret += v *(v-1)//2
	print(ret)	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
B=[]
for a in A:
    B.append(a)
    B=B[::-1]
print(*B)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
if N%2==0:
    B=A[::-2]+A[::2]
else:
    B=A[::-2]+A[1::2]
print(*B)
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
n = int(input())
a_b = sorted(make_divisors(n))
flag = False
for i in a_b:
  if i ** 5 == n:
    print(i, 0)
    break
  else:
    for b in range(-1*i-1, i + 1):
      if (i+b)**5-b**5 == n:
        print(i + b, b)
        flag = True
        break
  if flag:
    break

### FIXED CODE ###

import numpy as np
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            #if i != n // i:
                #divisors.append(n//i)
    return divisors
n = int(input())
a_b = sorted(make_divisors(n))
flag = False
for i in a_b:
  if i ** 5 == n:
    print(i, 0)
    break
  else:
    for b in range(-int(np.sqrt(n)), int(np.sqrt(n + 1))):
      if (i+b)**5-b**5 == n:
        print(i + b, b)
        flag = True
        break
  if flag:
    break
### BUGGY CODE ###

N=input()
S=input()
N=int(N)
ans=0
ind=[]
tmp={"R":0,"G":0,"B":0}
for i in S:
    tmp[i]+=1
    ind.append(tmp.copy())
#print(ind)
for i in range(0,N-2):
    for j in range(i+1,N-1):
        if S[i]==S[j]:
            continue
        for k in tmp.keys():
            if k!=S[i] and k!=S[j]:
                col=k
                break
        #print(i,j,col)
        if 2*j-i <N and S[j+j-i]==col:
            ans-=1
        ans+=(ind[-1][col]-ind[j][col])
print(ans)


### FIXED CODE ###

N=input()
S=input()
N=int(N)
ans=0
ind=[]
tmp={"R":0,"G":0,"B":0}
for i in S:
    tmp[i]+=1
    ind.append(tmp.copy())
#print(ind)
for i in range(0,N-2):
    for j in range(i+1,N-1):
        if S[i]==S[j]:
            continue
        for k in tmp.keys():
            if k!=S[i] and k!=S[j]:
                col=k
                break
        #print(i,j,col)
        if 2*j-i <N and S[j+j-i]==col:
            ans-=1
        ans+=(ind[-1][col]-ind[j][col])
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict, deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N = int(input())
es = defaultdict(list)
se = defaultdict(list)
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins, start):
  q = deque(start)
  res = []
  while q:
    p = q.popleft()
    res += [p]
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
start = [v1 for v1 in range(len(ins)) if ins[v1]==0]
ls = TP_sort(es, ins, start)
if ls==-1:
  print(-1)
else:
  for i in start:
    dp[i] = 0
  print(dfs(ls[-1])+1)

### FIXED CODE ###

N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

for i in range(1,n+1):
	print(a.count(i))

### FIXED CODE ###

import collections
n = int(input())
a = [int(i) for i in input().split()]
mylist = collections.Counter(a)
for i in range(1,n+1):
	print(mylist[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
#A=[1,1,1,1,1,1,1]
#N=7
A.sort(reverse=True)
L=[]
dis=[A[0]]
L.append(A[0])
L.append(A[0])
#print(L)
num=0
for i in range(1,len(A)):
    ind=dis.index(max(dis))
    num+=dis.pop(ind)
    #L.insert(ind+1,A[i])
   
    dis[ind:ind]=[A[i],A[i]]
print(num)
#print(L)
#print(dis)

### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))
#A=[1,1,1,1,1,1,1]
#N=7
A.sort(reverse=True)
dis=deque([A[0]])
num=0
for i in range(1,len(A)):
    num+=dis.popleft()
    #L.insert(ind+1,A[i])
    dis.append(A[i])
    dis.append(A[i])
print(num)
#print(L)
#print(dis)
### BUGGY CODE ###

s = input().split()
N = int(s[0])
K = int(s[1])
A = input().split()

for i in range(K, N):
    m1 = 1
    m2 = 1
    for j in range(K):
        m1 *= int(A[i - j - 1])
        m2 *= int(A[i - j - 0])
    print('Yes' if m1 < m2 else 'No')


### FIXED CODE ###

s = input().split()
N = int(s[0])
K = int(s[1])
A = input().split()

for i in range(K, N):
    m1 = int(A[i - K])
    m2 = int(A[i])
    print('Yes' if m1 < m2 else 'No')
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect
from heapq import heappush, heappop
from scipy.sparse.csgraph import floyd_warshall

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, T = MAP()
wv = [LIST() for _ in range(N)]
dp1 = [[0]*T for _ in range(N+1)]
dp2 = [[0]*T for _ in range(N+1)]


for i in range(N):
	for j in range(T):
		if j < wv[i][0]:
			dp1[i+1][j] = dp1[i][j]
		else:
			dp1[i+1][j] = max(dp1[i][j], dp1[i][j-wv[i][0]]+wv[i][1])

wv = wv[::-1]

for i in range(N):
	for j in range(T):
		if j < wv[i][0]:
			dp2[i+1][j] = dp2[i][j]
		else:
			dp2[i+1][j] = max(dp2[i][j], dp2[i][j-wv[i][0]]+wv[i][1])

wv = wv[::-1]
ans = 0
for i in range(1, N+1):
	tmp = 0
	for j in range(T):
		tmp = max(tmp, dp1[i-1][j] + dp2[N-i][T-1-j])
	ans = max(ans, tmp+wv[i-1][1])

print(ans)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect
from heapq import heappush, heappop

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, T = MAP()
wv = [LIST() for _ in range(N)]
dp1 = [[0]*T for _ in range(N+1)]
dp2 = [[0]*T for _ in range(N+1)]


for i in range(N):
	for j in range(T):
		if j < wv[i][0]:
			dp1[i+1][j] = dp1[i][j]
		else:
			dp1[i+1][j] = max(dp1[i][j], dp1[i][j-wv[i][0]]+wv[i][1])

wv = wv[::-1]

for i in range(N):
	for j in range(T):
		if j < wv[i][0]:
			dp2[i+1][j] = dp2[i][j]
		else:
			dp2[i+1][j] = max(dp2[i][j], dp2[i][j-wv[i][0]]+wv[i][1])

wv = wv[::-1]
ans = 0
for i in range(1, N+1):
	tmp = 0
	for j in range(T):
		tmp = max(tmp, dp1[i-1][j] + dp2[N-i][T-1-j])
	ans = max(ans, tmp+wv[i-1][1])

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

from collections import Counter
n,*a=map(int,open(0).read().split())
l=[0]*n
r=[0]*n
for i,c in enumerate(a):
  l[i]+=c+i+1
  r[i]+=i+1-c
L=Counter(l)
R=Counter(r)
ans=0
for i in range(1,n+max(a)):
  ans+=L[i]*R[i]
print(ans)

### FIXED CODE ###

from collections import Counter
n,*a=map(int,open(0).read().split())
l=[0]*n
r=[0]*n
for i,c in enumerate(a):
  l[i]+=c+i+1
  r[i]+=i+1-c
L=Counter(l)
R=Counter(r)
def count(A):
  ret=0
  for i in A.values():
    ret+=i*(i-1)//2
  return ret
print(count(L+R)-count(L)-count(R))
### BUGGY CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))
 
def E(n):
  return sum(range(1,n+1)) / n
 
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
elif N == K:
  l2 = list(map(E, l))  
  print(sum(l2))
elif K == 1:
  print(E(max(l)))
else:
  j = sum(l[0:0+K])
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if m < j:
          m = j
          t = l[i:i+K]

  l2 = list(map(E, t))
 
  print(sum(l2))

### FIXED CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))
 
def E(n):
  return (1 + n) / 2
 
j = sum(l[0:0+K])
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
elif N == K:
  l2 = list(map(E, l))  
  print(sum(l2))
else:
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if l[i] < l[i-1]:
          continue
      elif m < j:
          m = j
          t = l[i:i+K]

  l2 = list(map(E, t))
 
  print(sum(l2))
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
a.sort(reverse=True)
maxi = a[0]
j = 1
k = 1
while k <= len(a)-1:
  if (j*maxi)%a[k] == 0:
    k += 1
  else:
    k = 1
    j += 1
print(j*maxi)

### FIXED CODE ###

N=int(input())#入力回数を決める
import fractions
from functools import reduce
li=[]
for i in range(N):
  li.append(int(input()))
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
print(lcm_list(li))
### BUGGY CODE ###

n = int(input())
alist = list(map(int,input().split()))
aset = set(alist)
blist = list(aset)
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
ans1 = sum([cmb(alist.count(i),2) for i in blist if alist.count(i) >= 2])
for i in range(n):
  if alist.count(alist[i]) >= 2:
    print(ans1-alist.count(alist[i])+1)
  else:
    print(ans1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
alist = list(map(int,input().split()))
aalist = [0]*n
aset = set(alist)
adic = {}
for a in alist:
    if a not in adic:
        adic[a] = 0
    adic[a] += 1
a_counter = list(adic.items())

sigma = 0
for counter in a_counter:
    sigma += counter[1] * (counter[1] - 1) // 2

for i in range(n):
    aalist[i] = adic[alist[i]]-1

anslist = []
for a in aalist:
    anslist.append(sigma - a)

for ans in anslist:
    print(ans)
### BUGGY CODE ###

from collections import deque

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

t = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, (input().split()))
    t[a].append(b)
    t[b].append(a)

cnt = [0 for i in range(n + 1)]
for i in range(q):
    p, x = map(int, (input().split()))
    cnt[p] += x

d = deque()
d.append(1)
chked = []
while d:
    stat = d.pop()
    chked.append(stat)
    for v in t[stat]:
        if v not in chked:
            d.append(v)
            cnt[v] += cnt[stat]

print(*cnt[1:])


### FIXED CODE ###

from collections import deque

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

t = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, (input().split()))
    t[a].append(b)
    t[b].append(a)

cnt = [0 for i in range(n + 1)]
for i in range(q):
    p, x = map(int, (input().split()))
    cnt[p] += x

d = deque()
d.append(1)
chked = set()
while d:
    stat = d.pop()
    chked.add(stat)
    for v in t[stat]:
        if v not in chked:
            d.append(v)
            cnt[v] += cnt[stat]

print(*cnt[1:])
### BUGGY CODE ###

import copy
from functools import lru_cache
import math
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for k in range(K):
        B = [0] * N
        for i in range(N):
            l = max(0, i - A[i])
            r = min(i + A[i], N-1)
            B[l] += 1
            if r+1 < N:
                B[r+1] -= 1

        for i in range(1, N):
            B[i] += B[i - 1] 

        A = B[:]

        if k >= 41:
            break

    print(" ".join(map(str, B)))

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import copy
from functools import lru_cache
import numpy as np
from numba import njit

#@njit
# @njit('(i8[::1],)', cache=True)
# def func(A):
#     N = len(A)
#     B = np.zeros_like(A)
#     for i in range(N):
#         l = max(0, i - A[i])
#         r = min(i + A[i], N-1)
#         B[l] += 1
#         if r+1 < N:
#             B[r+1] -= 1

#     B = np.cumsum(B)
#     return B

def resolve():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())))

    # N = 2 * 10**5
    # K = 2 * 10**5
    # A = np.array([0] *  N)

    @njit
    def func(A):
        #N = len(A)
        B = np.zeros_like(A)
        for i in range(N):
            l = max(0, i - A[i])
            r = min(i + A[i], N-1)
            B[l] += 1
            if r+1 < N:
                B[r+1] -= 1

        B = np.cumsum(B)
        return B

    for k in range(K):
        #print(k)
        A = func(A)
        if k >= 50:
            break

    print(" ".join(map(str, A)))

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

n,k,q=map(int, input().split()) #a1 a2 a3
ans = [int(input()) for i in range(q)]

mem=[k]*n

for a in ans:
  mem=[mem[i]-1 for i in range(n)]
  mem[a-1]+=1

for m in mem:
  print('Yes' if m>0 else 'No' )


### FIXED CODE ###

n,k,q=map(int, input().split()) #a1 a2 a3
ans = [int(input()) for i in range(q)]

mem=[0]*n

for a in ans:
  mem[a-1]+=1


print("\n".join("Yes" if k-q+m>0 else "No" for m in mem))
### BUGGY CODE ###

def count(P, idx, score, G, mn, cnt):
    # print(idx, score, mn, cnt)
    if score >= G and mn > cnt:
        return cnt
    if idx > len(P)-1:
        return mn
    for i in range(P[idx][0]+1):
        tmp = P[idx][1] if i == P[idx][0] else 0
        # print(idx, i)
        mn = count(P, idx+1, score+idx*100*i+tmp, G, mn, cnt+i)
    return mn

D,G = map(int, input().split())
P = [0]
for i in range(D):
    p,c = map(int, input().split())
    P.append([p,c])
print(count(P, 1, 0, G, 10**9, 0))


### FIXED CODE ###

from math import ceil
d,g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = float('INF')
inf = float('INF')
for i in range(2**d):
    tmp = 0
    cnt = 0
    for j in range(d):
        p,c = pc[j]
        if i & (1 << j):
            tmp += p * (j+1) * 100 + c
            cnt += p
    if g <= tmp and cnt < ans:
        ans = cnt
    if g > tmp:
        tmp_cnt = inf 
        tmp_ = 0
        gg = (g - tmp) / 100
        for j in range(d):
            p,c = pc[j]
            if i & (1 << j):
                continue
            if ceil(gg / (j+1)) < min(p,tmp_cnt):
                cc = ceil(gg / (j+1))
                tmp_ = cc * (j+1) * 100
                tmp_cnt = cc
            elif gg - c / 100 <= p * (j+1) and p < tmp_cnt:
                tmp_ = p * (j+1) * 100 + c
                tmp_cnt = p
        if g <= tmp + tmp_ and cnt + tmp_cnt < ans:
            ans = cnt + tmp_cnt

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

# ABC106D
import numpy as np
N,M,Q = map(int,input().split())

s = np.zeros([M,N])
f = np.zeros([M,N])
for m in range(M):
    L,R = map(int,input().split())
    s[m,:L] = 1
    f[m,R-1:] = -1

for x in range(Q):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    ans = s[:,p]-f[:,q]
    print(len(ans[ans==2]))

### FIXED CODE ###

N,M,Q = map(int,input().split())

train = [[0 for i in range(N)] for j in range(N)]
for m in range(M):
    L,R = map(int,input().split())
    train[L-1][R-1] += 1

c = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    cnt = 0
    for j in range(N):
        cnt += train[i][j]
        c[i][j] = cnt

for x in range(Q):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    cnt2 = 0
    for i in range(p,q+1):
        if p == 0:
            cnt2 += c[i][q]
        else:
            cnt2 += c[i][q] - c[i][p-1]
    print(cnt2)
### BUGGY CODE ###

M = 10 ** 9 + 7
s = input().strip()

num = 0
q_list = []
d = 1
for i in range(len(s) - 1, -1, -1):
	c = s[i]
	if c != "?":
		num = (num + int(c) * d) % 13
	else:
		q_list.append(d)
	d = (d * 10) % 13

counts = [0] * 13
counts[0] = 1
counts_save = [0] * 13
for d in q_list:
	for i in range(13):
		counts_save[i] = counts[i] % M
	for n in range(1, 10):
		r = (d * n) % 13
		for m in range(13):
			counts[(r + m) % 13] += counts_save[m]

print(counts[(13 + 5 - num) % 13] % M)


### FIXED CODE ###


M = 10 ** 9 + 7
s = raw_input().strip()

num = 0
q_list = []
d = 1
for i in range(len(s) - 1, -1, -1):
	c = s[i]
	if c != "?":
		num = (num + int(c) * d) % 13
	else:
		q_list.append(d)
	d = (d * 10) % 13

counts = [0] * 13
counts[0] = 1
counts_save = [0] * 13
for d in q_list:
	for i in range(13):
		counts_save[i] = counts[i] % M
	for n in range(1, 10):
		r = (d * n) % 13
		for m in range(13):
			counts[(r + m) % 13] += counts_save[m]

print(counts[(13 + 5 - num) % 13] % M)
### BUGGY CODE ###

import sys
from collections import deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, M = map(int, readline().split())
graph = [[0] * N for _ in range(N)]
for i in range(M):
    A, B = map(int1, readline().split())
    graph[A][B] = 1
    graph[B][A] = 1
ans = [None] * (N)

visited = [False] * N
visited[0] = True

que = deque([0])

while len(que) > 0:
    acc = que.popleft()
    for i, pos in enumerate(graph[acc]):
        if pos == 0 or visited[i]:
            continue

        ans[i] = acc + 1
        visited[i] = True
        que.append(i)

if sum(visited) == len(visited):
    print("Yes")
    for sign in ans[1:]:
        print(sign)
else:
    print("No")

### FIXED CODE ###

import sys
from collections import deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, M = map(int, readline().split())
graph = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int1, readline().split())
    graph[A].append(B)
    graph[B].append(A)
ans = [None] * (N)

visited = [False] * N
visited[0] = True

que = deque([0])

while len(que) > 0:
    acc = que.popleft()
    for connected in graph[acc]:
        if visited[connected]:
            continue

        ans[connected] = acc + 1
        visited[connected] = True
        que.append(connected)

if sum(visited) == len(visited):
    print("Yes")
    for sign in ans[1:]:
        print(sign)
else:
    print("No")
### BUGGY CODE ###

N = int(input())

S = []
cnt = 0
for n in range(N):
  temp = input()
  if not (temp in S):
    S.append(temp)
    cnt += 1

print(cnt)

### FIXED CODE ###

N = int(input())

S = []
cnt = 0
for n in range(N):
  temp = input()
  S.append(temp)

S = set(S)
print(len(S))
### BUGGY CODE ###

def resolve():
    s = int(input())
    ans = [s]
    count = 0
    while s != 4:
        if ans[count]%2 == 0:
            ans.append(ans[count]/2)
        else:
            ans.append(ans[count]+3)
        count += 1
        if ans[count] < 1:
            ans[count] = ans[count-1]
    print(count+4)
resolve()

### FIXED CODE ###

def resolve():
    s = int(input())
    ans = [s]
    count = 0
    while True:
        if ans[count]%2 == 0:
            ans.append(ans[count]/2)
        else:
            ans.append(ans[count]*3+1)
        count += 1
        for i in range(count):
            if ans[i] == ans[count]:
                print(count+1)
                exit()
resolve()
### BUGGY CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

mod = 10**9 +7
n, k = map(int, input().split())
a = list(map(int, input().split()))
ascA = sorted(a)

sum_ = 0
for i in range(n-k+1):
    for j in range(i+k-1, n):
        f = ascA[j]-ascA[i]
        c = cmb(j-i-1, k-2)
        #print("%d %d"%(f,c))
        sum_ = (sum_ + (f*c) % mod) % mod

print(sum_)

### FIXED CODE ###

def cmb(n,k, MOD):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

MOD = 10**9+7
n, k = map(int, input().split())
a = list(map(int, input().split()))
ascA = sorted(a)

MAX_N = n
fac  = [0 for _ in range(MAX_N)]
finv = [0 for _ in range(MAX_N)]
inv  = [0 for _ in range(MAX_N)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_N):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

sum_ = 0
for i in range(n-k+1):
    f = ascA[n-i-1] - ascA[i]
    c = cmb(n-i-1, k-1, MOD)
    sum_ = (sum_ + (f*c)%MOD) % MOD
    '''
    for j in range(i+k-1, n):
        f = ascA[j]-ascA[i]
        c = cmb(j-i-1, k-2, MOD)
        #print("%d %d"%(f,c))
        sum_ = (sum_ + (f*c) % MOD) % MOD
    '''

print(sum_)