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

from collections import defaultdict 
n,q=map(int,input().split())
s=input()
l=[list(map(int,input().split())) for _ in range(q)]
d= defaultdict(int)
for i in range(n-1):
  if s[i]=="A" and s[i+1]=="C":
    d[i]=1
for j in range(q):
  sm=0
  for k in range(l[j][0]-1,l[j][1]-1):
    sm+=d[k]
  print(sm)


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
d=[0]*(n+1)
for i in range(1,n):
  if s[i]=="C" and s[i-1]=="A":
    d[i]=d[i-1]+1
  else:
    d[i]=d[i-1]

for j in range(q):
  l,r=map(int,input().split())
  print(d[r-1]-d[l-1])
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[]
dp.append(0)
for i in range(1,n):
  dp.append(min(dp[j]+abs(h[i]-h[j]) for j in range(max(i-k,0),i)))
print(dp[n-1])

### FIXED CODE ###

def main():
	N, K = map(int, input().split())
	h = list(map(int, input().split()))
	dp=[0]*N
	for i in range(1,N):
		dp[i] = min(dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i))
	print(dp[N-1])
main()
### BUGGY CODE ###



N=int(input())

S_list = []
S_count = []
max = 1
temp_list = []
#for i in range(N):
#    s = input()
#    temp_list.append(s)

for i in range(N):
    s = input()
    #temp_list = []
    #temp_list.append(s)
    try:
        index = S_list.index(s)
        S_count[index] += 1
        if max < S_count[index]:
            max = S_count[index]
    except ValueError:
        S_list.append(s)
        S_count.append(1)
    
     
#print(S_list)
#print(S_count)
#print(max)
S_max = []
for j in range(len(S_list)):
    if S_count[j] == max:
        S_max.append(S_list[j])

S_max.sort()
for k in range(len(S_max)):
    print(S_max[k])

### FIXED CODE ###



N=int(input())

S_list = []
S_count = []
max = 1
temp_list = []
#for i in range(N):
#    s = input()
#    temp_list.append(s)
S_dict = {}
for i in range(N):
    s = input()
    if s in S_dict.keys():
        S_dict[s] += 1
        if max < S_dict[s]:
            max = S_dict[s]
    else:
        S_dict[s] = 1
    
     
#print(S_list)
#print(S_count)
#print(max)
S_max = []
for j in S_dict:
    if S_dict[j] == max:
        S_max.append(j)

S_max.sort()
for k in range(len(S_max)):
    print(S_max[k])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n=int(input())
h=list(map(int,input().split()))

z=0
for i in range(n-1):
        if h[i]-1>min(h[i+1:n]):
                print('No')
                break
        else:
                z+=1
                continue

if z==n-1:
        print('Yes')


### FIXED CODE ###

import sys
input = sys.stdin.readline

n=int(input())
h=list(map(int,input().split()))
l=h
s=[]
t=max(h)

for i in range(n-1):
        if l[i]-1==l[i+1]:
                l[i]=l[i]-1
                s.append(l[i])
        elif l[i]==l[i+1] and l[i]==t:
                l[i]=l[i]-1
                s.append(l[i])
        elif l[i]-1>l[i+1]:
                break
        elif l[i]-1<l[i+1]:
                s.append(l[i])
                continue

s.append(h[n-1])
s.sort()
if len(s)==n:
        if l==s:
                print('Yes')
        else:
                print('No')

else:
        print('No')
### BUGGY CODE ###

d=[0]*13
d[0]=1
mul=1
mulmod=1
t=list(input())
t.reverse()
zero=[0]*13
for c in t:
    e=zero[:]

    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            #e[(i*mul+j)%13]+=d[j]
            k=(i*mulmod+j)%13
            e[k]+=d[j]
            e[k]%=1000000007
    d=e[:]
    mul*=10
    mulmod=mul%13
print(d[5])



### FIXED CODE ###

# coding: utf-8
# Your code here!
 
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意
 
s = input()
l = len(s)
MOD = 10**9+7
 
dp = [0]*13
dp[0] = 1
for i in s:
    new = [0]*13
    if i == "?":
        for i in range(10):
            for j in range(13):
                new[(10*j+i)%13] += dp[j]
    else:
        i = int(i)
        for j in range(13):
            new[(i+10*j)%13] += dp[j]
    
    for i in range(13):
        new[i] %= MOD
    dp,new = new,dp
#    print(dp)
 
print(dp[5]%MOD)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def print_ans(L, R):
    """Test Case
    >>> print_ans(2020, 2040)
    2
    >>> print_ans(4, 5)
    20
    """
    tmp = R - L
    L = L % 2019
    R = L + tmp
    ans = 2019
    for i in range(L, R):
        for k in range(i + 1, R + 1):
            ans = min(ans, (i * k) % 2019)
            if ans == 0:
                break
    print(ans)



if __name__ == '__main__':
    L, R = map(int, input().rstrip().split())
    print_ans(L, R)


### FIXED CODE ###

import sys
input = sys.stdin.readline
def print_ans(L, R):
    """Test Case
    >>> print_ans(2020, 2040)
    2
    >>> print_ans(4, 5)
    20
    """
    tmp = R - L
    if tmp > 2019:
        print("0")
    else:
        L = L % 2019
        R = L + tmp
        ans = 2019
        flg = False
        for i in range(L, R):
            for k in range(i + 1, R + 1):
                ans = min(ans, (i * k) % 2019)
                if ans == 0:
                    flg = True
                    break
            if flg :
                break
        print(ans)



if __name__ == '__main__':
    L, R = map(int, input().rstrip().split())
    print_ans(L, R)
### BUGGY CODE ###

n, m = map(int, input().split())
a, b = [], []
for i in range(m):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  a.append(_)
  b.append(__)
  
# union-find

# 誰の肩に手を置いているか（先頭の場合は-1）
parent = [-1 for i in range(n)]

# kさんの「運転手」が誰かを調べる関数
def find_root(k):
  while parent[k] != -1:
    k = parent[k]
  return k 

for i in range(m):
  # a[i] と b[i] の合併
  root_a = find_root(a[i])
  root_b = find_root(b[i])
  # root_a が root_b に勝ったとする
  parent[root_b] = root_a
  
group = [find_root(i) for i in range(n)]

from collections import Counter
print(Counter(group).most_common()[0][1])

### FIXED CODE ###

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

# 隣接リストをつくる 
adj_list = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  adj_list[a].append(b)
  adj_list[b].append(a)
  
# どの連結成分に属してるかを把握するための配列
group = [-1 for i in range(n)]

# 各頂点 i から探索をする
for i in range(n):
  if group[i] != -1: continue
  # i から DFS
  newly_visited = [i]
  group[i] = i
  while len(newly_visited) > 0:
    now = newly_visited.pop()
    for j in adj_list[now]:
      if group[j] != -1: continue
      newly_visited.append(j)
      group[j] = i

hist = [0 for i in range(n)]
for g in group:
  hist[g] += 1
print(max(hist))
### BUGGY CODE ###

N = int(input())
Ai = list(map(int,input().split()))
Aisort = sorted(Ai) + [-1]
Aidic = {}
cnt = 1
for i in range(1,N+1):
    if Aisort[i] != Aisort[i-1]:
        Aidic.update([(str(Aisort[i-1]), cnt)])
        cnt = 1
    else:
        cnt = cnt + 1

for A in Ai:
    cnt = 0
    for i, indx in enumerate(Aidic):
        num = int(Aidic[indx])
        if str(A) == indx:
            cnt = cnt + (num-1)*(num-2)//2
        else:
            cnt = cnt + num*(num-1)//2
    print(cnt)
            

### FIXED CODE ###

N = int(input())
Ai = list(map(int,input().split()))
Aisort = sorted(Ai) + [-1]
Aidic = {}
cnt = 1
for i in range(1,N+1):
    if Aisort[i] != Aisort[i-1]:
        Aidic.update([(str(Aisort[i-1]), cnt)])
        cnt = 1
    else:
        cnt = cnt + 1

cnt = 0
for i, indx in enumerate(Aidic):
    num = int(Aidic[indx])
    cnt = cnt + num*(num-1)//2


for A in Ai:
    num = int(Aidic[str(A)])
    num = cnt - (num-1)
    print(num)
### BUGGY CODE ###

n=int(input())
a = list(map(int,input().split()))
ans=a[0]
for s in range(1,n):
  ans *=a[s]
if ans > 10**18:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
ans=a[0]
if 0 in a:
  print(0)
  exit()
for s in range(1,n):
  ans *=a[s]
  if ans > 10**18:
    print(-1)
    exit()

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

S = input()
Q = int(input())
Query = list(input().split() for i in range(Q))
ans = S
sentou = 0
for i in range(Q):
    if Query[i][0] == "1":
        sentou += 1
    if Query[i][0] == "2":
        if Query[i][1] == "1":
            if sentou % 2:
                ans = ans + Query[i][2]
            else:
                ans = Query[i][2] + ans
        if Query[i][1] == "2":
            if sentou % 2:
                ans = Query[i][2] + ans
            else:
                ans = ans + Query[i][2]
if sentou % 2:
    print(ans[::-1])
else:
    print(ans)

### FIXED CODE ###

from collections import deque
S = deque([input()])
Q = int(input())
Query = list(input().split() for i in range(Q))
sentou = 0
for i in range(Q):
    if Query[i][0] == "1":
        sentou += 1
    if Query[i][0] == "2":
        if Query[i][1] == "1":
            if sentou % 2:
                S.append(Query[i][2])
            else:
                S.appendleft(Query[i][2])
        if Query[i][1] == "2":
            if sentou % 2:
                S.appendleft(Query[i][2])
            else:
                S.append(Query[i][2])
ans = ""
for i in S:
    ans += i
if sentou % 2:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

import queue

BLACK = '#'
WHITE = '.'
vec_x = [1, 0, -1, 0]
vec_y = [0, 1, 0, -1]
vec_num = len(vec_x)

def solve():
    count = 0
    for i in range(H):
        for j in range(W):
            if used[i][j]:
                continue
            b = 0
            w = 0
            que = queue.Queue()
            used[i][j] = True
            que.put((i, j))

            while not que.empty():
                next_i, next_j = que.get()

                #黒か白かをカウント
                if(S[next_i][next_j] == BLACK):
                    b += 1
                else:
                    w += 1

                #隣接するマスの色が現在のマスと違うならキューに追加
                for d in range(vec_num):
                    d_i = next_i + vec_y[d]
                    d_j = next_j + vec_x[d]
                    if not check(next_i, next_j, d_i, d_j) or used[d_i][d_j]:
                        continue
                    que.put((d_i, d_j))
                    used[d_i][d_j] = True
            count += b * w
    return count

def check(i, j, d_i, d_j):
    if not isIn(d_i, d_j):
        return False
    if S[i][j] == S[d_i][d_j]:
        return False
    return True

def isIn(i, j):
    return 0 <= i < H and 0 <= j < W



if __name__ == "__main__":
    H, W = map(int, input().split())
    S = [[]] * H
    used = [[]] * H
    for h in range(H):
        S[h] = list(input())
        used[h] = [False] * W
    print(solve())


### FIXED CODE ###

from collections import deque

BLACK = '#'
WHITE = '.'
vec_x = [1, 0, -1, 0]
vec_y = [0, 1, 0, -1]
vec_num = len(vec_x)

def solve():
    count = 0
    for i in range(H):
        for j in range(W):
            if used[i][j]:
                continue
            b = 0
            w = 0
            que = deque([(i, j)])
            used[i][j] = True

            while que:
                next_i, next_j = que.popleft()

                #黒か白かをカウント
                if(S[next_i][next_j] == BLACK):
                    b += 1
                else:
                    w += 1

                #隣接するマスの色が現在のマスと違うならキューに追加
                for d in range(vec_num):
                    d_i = next_i + vec_y[d]
                    d_j = next_j + vec_x[d]
                    if not check(next_i, next_j, d_i, d_j) or used[d_i][d_j]:
                        continue
                    que.append((d_i, d_j))
                    used[d_i][d_j] = True
            count += b * w
    return count

def check(i, j, d_i, d_j):
    if not (0 <= d_i < H and 0 <= d_j < W):
        return False
    if S[i][j] == S[d_i][d_j]:
        return False
    return True



if __name__ == "__main__":
    H, W = map(int, input().split())
    S = [[]] * H
    used = [[]] * H
    for h in range(H):
        S[h] = list(input())
        used[h] = [False] * W
    print(solve())
### BUGGY CODE ###

n = int(input())
v = list(map(int,input().split()))
vodd = v[0::2]
veven = v[1::2]

set_vodd = list(set(vodd))
set_veven = list(set(veven))
cnt_vodd = [0] * len(set_vodd)
cnt_veven = [0] * len(set_veven)

if len(set_vodd) == 1 and set_vodd == set_veven:
    print(int(n/2))
else:
    for i in range(len(set_vodd)):
        cnt_vodd[i] = vodd.count(set_vodd[i])
    sort_cnt_vodd = sorted(cnt_vodd)
    ans_vodd = (n/2) - (sort_cnt_vodd[-1])

    for i in range(len(set_veven)):
        cnt_veven[i] = veven.count(set_veven[i])
    sort_cnt_veven = sorted(cnt_veven)
    ans_veven = (n/2) - (sort_cnt_veven[-1])
    
    print(int(ans_vodd) + int(ans_veven))

### FIXED CODE ###

import collections

n = int(input())
v = list(map(int,input().split()))
vodd = v[0::2]
veven = v[1::2]

set_vodd = list(set(vodd))
set_veven = list(set(veven))
cnt_vodd = collections.Counter(vodd)
cnt_veven = collections.Counter(veven)

if len(set_vodd) == 1 and set_vodd == set_veven:
    print(n//2)
else:
    if cnt_vodd.most_common(1)[0][0] != cnt_veven.most_common(1)[0][0]:
        ans_vodd = (n//2)- cnt_vodd.most_common(1)[0][1]
        ans_veven = (n//2)- cnt_veven.most_common(1)[0][1]
        print(ans_vodd + ans_veven)
    elif len(set_vodd)>=2 and len(set_veven)>=2:
        ans_vodd_1 = (n//2)- cnt_vodd.most_common(1)[0][1]
        ans_veven_1 = (n//2)- cnt_veven.most_common(2)[1][1]
        ans_vodd_2 = (n//2)- cnt_vodd.most_common(2)[1][1]
        ans_veven_2 = (n//2)- cnt_veven.most_common(1)[0][1]
        print(min(ans_vodd_1+ans_veven_1,ans_vodd_2+ans_veven_2))
### BUGGY CODE ###

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    #return d
a , b , c = map(int,input().split())

n = a
w = a #n:頂点数　w:辺の数

d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n-1):
    x = i
    y = i+1
    d[x][y] = 1
    d[y][x] = 1
d[b-1][c-1] = 1
d[c-1][b-1] = 1

for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
    
warshall_floyd(d)

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += d[j].count(i)
    print(ans//2)

### FIXED CODE ###

n , x , y = map(int,input().split())
p = [0 for i in range(n)]
for i in range(1,n+1):
    for j in range(1,i+1):
        p[min(abs(i-j),abs(i-x)+1+abs(j-y),abs(j-x)+1+abs(i-y))] += 1
for i in range(1,n):
    print(p[i])
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(int(input()) for i in range(N))
h.sort(reverse=True)
cnt = 0
ans = []
dif = float('inf') 
for i in range(N):
    if K-1<=i:
        if dif>ans[0]-h[i]:
            dif = ans[0]-h[i]
        del ans[0]
    ans.append(h[i])
print(dif) 

### FIXED CODE ###

N,K = map(int,input().split())
h = list(int(input()) for i in range(N))
h.sort(reverse=True)
dif = float('inf') 
for i in range(K-1,N):
    dif = min(dif,h[i-K+1]-h[i])
print(dif)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
x,y,z,k = map(int,readline().split())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]
c = [int(i) for i in readline().split()]
from bisect import bisect_left,insort
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

stop = 0
ans = []
cn = 0
for i in a:
  for j in b:
    for l in c:
      if i+j+l <= stop:
        break
      if cn >= k:
        if bisect_left(ans,i+j+l) > 0:
          insort(ans,i+j+l)
        else:
          stop = i+j+l
      else:
        insort(ans,i+j+l)
        cn += 1
        
ans = ans[::-1]
for i in ans[:k]:
  print(i)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
x,y,z,k = map(int,readline().split())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]
c = [int(i) for i in readline().split()]
from heapq import heappush,heappop,heapify
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

chk = [(-(a[0]+b[0]+c[0]),0,0,0)]
heapify(chk)
C = set((0,0,0))
ans = []
for i in range(k):
  p,q,r,s = heappop(chk)
  ans.append(-p)
  if not (q+1,r,s) in C and q < x-1:
    C.add((q+1,r,s))
    heappush(chk,(-(a[q+1]+b[r]+c[s]),q+1,r,s))
  if not (q,r+1,s) in C and r < y-1:
    C.add((q,r+1,s))
    heappush(chk,(-(a[q]+b[r+1]+c[s]),q,r+1,s))
  if not (q,r,s+1) in C and s < z-1:
    C.add((q,r,s+1))
    heappush(chk,(-(a[q]+b[r]+c[s+1]),q,r,s+1))
    
for i in ans:
  print(i)
### BUGGY CODE ###

R,G,B,N=(int(x) for x in input().split())
cnt=0
for r in range((N//R)+1):
    for g in range((N//G)+1):
        if (N-R*r-G*g)<0: continue
        if (N-R*r-G*g)%B==0:
            cnt=cnt+1
print (cnt)

### FIXED CODE ###

R,G,B,N=list(map(int,input().split()))
cnt=0
for r in range((N//R)+1):
    for g in range(((N-R*r)//G)+1):
        if (N-R*r-G*g)%B==0:
            cnt=cnt+1
print (cnt)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
A = [0 for _ in range(n-1)]
for i in range(n-1):
  if s[i:i+2] == 'AC':
    A[i] = 1
LR = []
for i in range(q):
  LR.append(list(map(int, input().split())))
  print(sum(a for a in A[LR[i][0]-1:LR[i][1]-1]))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
A = [0 for _ in range(n+1)]
for i in range(n-1):
  A[i+1] = A[i] + (1 if s[i:i+2] == 'AC' else 0)
for j in range(q):
  l, r = map(int, input().split())
  print(A[r-1] - A[l-1])
### BUGGY CODE ###

from collections import deque
from collections import defaultdict
N,K,L=map(int, raw_input().split())

nl=[ [] for i in range(N+1) ]

c1=set()

for i in range(K):
	p,q=map(int, raw_input().split())
	nl[p].append(q)
	nl[q].append(p)
	c1.add(p)
	c1.add(q)

nl2=[ [] for i in range(N+1) ]
c2=set()

for i in range(L):
	p,q=map(int, raw_input().split())
	nl2[p].append(q)
	nl2[q].append(p)
	c2.add(p)
	c2.add(q)


road=[ None for i in range(N+1) ]
railway=[ None for i in range(N+1) ]
l1=defaultdict(lambda: [])
l2=defaultdict(lambda: [])

def bfs(start,nl,type):
	V=[ None for i in range(N+1)]
	q = deque([]) 
	V[start]=1
	tmp=[]
	tmp.append(start)

	if type=="road": road[start]=start
	elif type=="railway": railway[start]=start

	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				tmp.append(i)
				if type=="road": road[i]=start
				elif type=="railway": railway[i]=start

	if type=="road": l1[start]=tmp
	elif type=="railway": l2[start]=tmp				
	return V




for i in c1:
	if road[i] is None: bfs(i,nl,"road")


for i in c2:
	if railway[i] is None: bfs(i,nl2,"railway")



for idx,i in enumerate( zip(road,railway) ):
	x=i[0]; y=i[1]
	if idx==0: continue
	if (x and y) is None:
		print 1,
	else:
		print len( set(l1[x]) & set(l2[y]) ),
	
	



### FIXED CODE ###

from collections import deque
from collections import Counter

N,K,L=map(int, raw_input().split())

nl=[ [] for i in range(N+1) ]

for i in range(K):
	p,q=map(int, raw_input().split())
	nl[p].append(q)
	nl[q].append(p)

nl2=[ [] for i in range(N+1) ]

for i in range(L):
	p,q=map(int, raw_input().split())
	nl2[p].append(q)
	nl2[q].append(p)


v1=[ None for i in range(N+1) ]
v2=[ None for i in range(N+1) ]


def bfs(start,nl,V,l):
	q = deque([]) 
	V[start]=1
	l[start]=start
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				l[i]=start
			
	return V

l1=[ "" for i in range(N+1) ]
l2=[ "" for i in range(N+1) ]


for i in range(1,N+1):
	if v1[i] is None:
		bfs(i,nl,v1,l1)

for i in range(1,N+1):
	if v2[i] is None:
		bfs(i,nl2,v2,l2)


c=[]
for idx,i in enumerate( zip(l1,l2) ):
	x=i[0]; y=i[1]
	if idx==0: continue
	c.append( (x,y) )


C=Counter(c)

for idx,i in enumerate( zip(l1,l2) ):
	x=i[0]; y=i[1]
	if idx==0: continue
	print C[(x,y)],
### BUGGY CODE ###

import collections


N=int(input())
D=list(map(int,input().split()))
M=int(input())
T=list(map(int,input().split()))

TS=collections.Counter(T)

for i,k in TS.items():
    if k > D.count(i):
        print('NO')
        exit()

print('YES')


### FIXED CODE ###

import collections

N=int(input())
D=list(map(int,input().split()))
M=int(input())
T=list(map(int,input().split()))

DS=collections.Counter(D)
TS=collections.Counter(T)

for i,k in TS.items():

    if k > DS[i]:
        print('NO')
        exit()

print('YES')
### BUGGY CODE ###

# coding: utf-8

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

ans = 1
for i in range(N):
    ans *= A[i]

if ans > 10**18:
    ans = -1

print(ans)


### FIXED CODE ###

# coding: utf-8

N = int(input())
A = sorted(list(map(int,input().split())))
if A[0] == 0:
    ans = 0
else:
    ans = 1
    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            ans = -1
            break

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

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

import itertools

p = itertools.combinations(a, k)

su=0
for i in p:
  su+=(max(i)-min(i))%MOD

print(su%MOD)

### FIXED CODE ###

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

a.sort(reverse=True)


fact = [1]
fact_inv = [1]
mod=10**9+7
for i in range(10**5+1):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))


def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

  
c=[]
for i in range(1,n-k+1+1):
  c.append(mod_comb_k(n-i,k-1,MOD))
lc=len(c)
#print(c,a)
sum=0
for i in range(lc):
  sum+=c[i]*(a[i]-a[-i-1])%MOD
  
print(sum%MOD)
### BUGGY CODE ###

import time
N,K=map(int,input().split())
dice = list(map(int, input().split()))#dic=[]


def calc(n):
    return (n+1)/2
t1=time.time()
data = list(map(calc, dice))
t2=time.time()
t3=time.time()
p=0
for j in range(N-K+1):
    su=sum(data[j:j+K])
    if su>p:
        p=su
t4=time.time()
print(p)


### FIXED CODE ###

N,K=map(int,input().split())
dice = list(map(int, input().split()))
a=sum(dice[0:K])

l = [a]
for i in range(1,N-K+1):
    a = a - dice[i-1] + dice[K-1+i]
    l.append(a)
print((max(l)+K)/2)
### BUGGY CODE ###

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

def max_pair(A):
    m1 = 0
    while A:
        m2 = max(A)
        A.remove(m2)
        if m1 == m2:
            return m1
        m1 = m2

    return 0

print(max_pair(A) * max_pair(A))


### FIXED CODE ###

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

def max_pair(Asc):
    m1 = 0
    while Asc:
        m2 = Asc.pop()
        if m1 == m2:
            return m1
        m1 = m2

    return 0

A.sort()
print(max_pair(A) * max_pair(A))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
P = list(map(int,input().split()))
for i in range(N-K+1):
  p = P[i:i+K]
  sum_ = (sum(p)+K)/2
  if i == 0:
    ans = sum_
  else:
    if sum_ > ans:
      ans = sum_
    else:
      continue
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
P = list(map(int,input().split()))
out_ = 0
p = P[0:K]
base = sum(p)
if N == K:
  answer = (sum(p)+K)/2
else:
  for i in range(N-K):
    out_ += P[i+K]-P[i]
    if i == 0:
      ans = out_
    else:
      if out_ > ans:
        ans = out_
      else:
        continue
  answer = (base+ans+K)/2
print(answer)
### BUGGY CODE ###

n,x = map(int,input().split())
li = list(map(int,input().split()))

s = 10**10

for i in range(n):
    s = min(s, abs(li[i] - x))
    
while True:
    for i in range(n):
        if abs(li[i]-x)%s != 0:
            break
    else:
        print(s)
        exit()
        
    s -= 1

### FIXED CODE ###

n,x = map(int,input().split())
li = list(map(int,input().split()))

res_abs = []
res = []

s = 10**10

for i in range(n):
    s = abs(li[i] - x)
    res_abs.append(s)
    
    s = li[i] - x
    res.append(s)
    
res.sort()

temp = 10**10

for i in range(n-1):
    temp = min(temp, res[i+1] - res[i])

    
s = min(min(res_abs), temp)
    
while True:
    for i in range(n):
        if res_abs[i]%s != 0:
            break
    else:
        print(s)
        exit()
        
    s -= 1