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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k,*alst = map(int,read().split())
alst.sort()
lst1=alst[k-1:]
lst2=alst[n-k::-1]
mod = 10 ** 9 + 7
res=0
prep=1
for i in range(n-k+1):
  res+=prep*(lst1[i]-lst2[i])
  res%=mod
  prep=prep*(i+k)//(i+1)

print(res)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,k,*alst = map(int,read().split())
alst.sort()
lst1=alst[k-1:]
lst2=alst[n-k::-1]
mod = 10 ** 9 + 7
res=0
prep=1
for i in range(n-k+1):
  res+=prep*(lst1[i]-lst2[i])
  res%=mod
  prep=prep*(i+k)*pow(i+1,mod-2,mod)
  prep%=mod

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

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(j) for j in  bin(A[i])[2:]]
    B[i]= [0]*(20-len(B[i]))+B[i]

ans=n
#累積和
R=[[] for i in range(n+1)]
R[0]=[0]*20
for i in range(n):
    R[i+1] = [l+k for l,k in zip(R[i], B[i])]
###

#転置
TR=[[0]*(n+1) for i in range(20)]
for i in range(n+1):
    for j in range(20):
        TR[j][i]=R[i][j]

from bisect import bisect_left as bi
for i in range(n,1,-1):
    now=R[i] ; #print(now)
    # score=
    ans+=i-max([bi(TR[k],now[k]-1) for k in range(20)])-1
    #print(ans)

print(ans)

### FIXED CODE ###

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(j) for j in  bin(A[i])[2:]]
    B[i]= [0]*(20-len(B[i]))+B[i]

ans=n
#累積和
R=[[] for i in range(n+1)]
R[0]=[0]*20
for i in range(n):
    R[i+1] = [l+k for l,k in zip(R[i], B[i])]
###

#転置
TR=[[0]*(n+1) for i in range(20)]
for i in range(n+1):
    for j in range(20):
        TR[j][i]=R[i][j]

from bisect import bisect_left as bi
for i in range(n,1,-1):
    now=R[i] ; #print(now)
    # score=
    ans+=i-max([bi(TR[k],now[k]-1) for k in range(20)])-1
    #print(ans)

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

if __name__ == '__main__':
	n = int(input())
	lists = list()

	for i in range(n):
		a = int(input())
		lists.append(a)
	
	m = None

	for i in range(n - 1):
		for j in range(i + 1, n):
			m = lists[j] - lists[i] if m is None or m < lists[j] - lists[i] else m
	print(m)





### FIXED CODE ###

if __name__ == '__main__':
	n = int(input())
	lists = list()

	for i in range(n):
		a = int(input())
		lists.append(a)

	S = None
	while len(lists) > 1:
		mini = min(lists)
		mini_ind = lists.index(mini)
		l = len(lists)

		if mini_ind + 1 == l:
			if S is None or S < lists[mini_ind] - lists[mini_ind - 1]:
				S = lists[mini_ind] - lists[mini_ind - 1]
			lists.pop(mini_ind)
			continue


		maxi = max(lists[mini_ind : l])
		T = maxi - mini

		if S is None or S < T:
			S = T

		lists = lists[0 : mini_ind]
		continue

	print(S)
### BUGGY CODE ###

s = list(input())[::-1]
word = ["dream", "dreamer", "erase", "eraser"]
dream = list("dream")[::-1]
dreamer = list("dreamer")[::-1]
erase = list("erase")[::-1]
eraser = list("eraser")[::-1]
while True:
    if s[:5] == dream or s[:5] == erase:
        s = s[5:]
        continue
    elif s[:6] == eraser:
        s = s[6:]
        continue
    elif s[:7] == dreamer:
        s = s[7:]
        continue
    break
if len(s) == 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

s = input()[::-1]
word = ["dream", "dreamer", "erase", "eraser"]
dream = "dream"[::-1]
dreamer = "dreamer"[::-1]
erase = "erase"[::-1]
eraser = "eraser"[::-1]
while True:
    if s[:5] == dream or s[:5] == erase:
        s = s[5:]
        continue
    elif s[:6] == eraser:
        s = s[6:]
        continue
    elif s[:7] == dreamer:
        s = s[7:]
        continue
    break
if len(s) == 0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

N = int(input())
A = tuple(map(int,input().split()))
b = 0
num = 10**9 + 7
for i in range(N-1):
    #print(i)
    for j in range(i+1,N):
        #print(j)
        b += A[i] ^ A[j]
        #b %= num
if b >= num:
    print(b%num)
else:
    print(b)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
ans = 0
for k in range(60):
    A_0 = 0
    A_1 = 0
    for i in range(N):
        if A[i]>>k&1:
            A_1 += 1
        else:
            A_0 += 1
    num = A_1 * A_0
    ans += (num * 2 ** k)
ans %=  mod
print(ans)
### BUGGY CODE ###

import numpy as np

N, W = map(int, raw_input().split())
dp = np.zeros((W+1, N))

for i in range(N):
    w, v = map(int, raw_input().split())
    max_temp = 0
    for j in range(w):
        dp[j][i] = dp[j][i-1]
    for j in range(w, W+1):
        dp[j][i] = max(dp[j][i-1], dp[j-w][i-1]+v, max_temp)
        max_temp = dp[j][i]
 
print int(dp[-1][-1])


### FIXED CODE ###

def main():

    N, W = map(int, raw_input().split())
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()
### BUGGY CODE ###

N = int(input())
SS = []
G1,G2,G3,G4 = [],[],[],[]
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        G1.append([MIN,cnt])
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        G3.append([MIN,cnt])
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])

# print(G1,G2,G3,G4)

cnt = 0
for L in G1:
    cnt += L[1]
G2.sort(reverse=True)
for L in G2:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]
G4.sort()
for L in G4:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]
        
cnt += sum(L[0] for L in G3)

if cnt == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = int(input())
G2,G4 = [],[]
cnt2 = 0
cnt3 = 0
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        cnt2 += cnt
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        cnt3 += cnt
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])


G2.sort(reverse=True)
for L in G2:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]
for L in G4:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]

cnt2 += cnt3

if cnt2 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import fractions
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
  return reduce(lcm, numbers, 1)         
         
lcm_ans = lcm_list(A)
ans = 0

for i in range(N):
  ans += (lcm_ans // A[i]) % MOD
  ans = ans % MOD
        
print(ans)         

### FIXED CODE ###

from fractions import gcd
from functools import reduce
 
N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
 
answer = sum(lcm//x for x in A)
answer %= MOD
print(answer)
### BUGGY CODE ###

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

values = [0] * N
links = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    links[a - 1].append(b - 1)
    links[b - 1].append(a - 1)
for _ in range(Q):
    p, x = map(int, input().split())
    values[p - 1] += x

s = [(0, -1)]
while s:
    i, p = s.pop(0)
    for j in links[i]:
        if j == p:
            continue
        values[j] += values[i]
        s.append((j, i))
print(*values)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
def main():
  _map = map
  _input = input
  _int = int
  def calc_results(results, pvalue, i):
    results[i] = pvalue + values[i]
    for j in childrens[i]:
      calc_results(results, results[i], j)
  n, q = _map(_int, _input().split())
  values = [0] * (n + 1)
  results = [0] * (n + 1)
  childrens = [[] for _ in range(n + 1)]
  for i in range(n - 1):
    a, b = _map(_int, _input().split())
    childrens[a].append(b)
  for _ in range(q):
    p, x = _map(_int, _input().split())
    values[p] += x
  calc_results(results, 0, 1)
  print(*[results[i] for i in range(1, n + 1)])
main()
### BUGGY CODE ###

import sys
import numpy as np
from fractions import gcd
from functools import reduce

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

input()
A = list(map(int, input().split()))
lcm = lcm_list(A)

print((lcm // np.array(A, dtype=np.int64) % LARGE).sum() % LARGE)


### FIXED CODE ###

import sys
from fractions import gcd

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

def lcm(x, y):
    return (x * y) // gcd(x, y)

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

l = 1
for a in A:
    l = lcm(l, a)

total = 0
for a in A:
    total += l // a

print(total % LARGE)
### BUGGY CODE ###

import sys
def I(): return int(input())  # '123' -> 123
def Is(): return map(int, input().split())  # '123 456' -> 123, 456
def LI(): return list(map(int, input().split()))  # '123 456' -> [123, 456]
def TI(): return tuple(map(int, input().split()))  # '123 456' -> (123, 456)
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()  # 'aa bb' -> 'aa','bb' or ['aa','bb']
def LS(): return list(input())  # 'abc123' -> ['a','b','c','1','2','3']
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(1000000)
MOD = 1000000007
INF = float('inf')

s = S()
q = I()
flag = 0

for i in range(q):
    query = input()
    if query[0] == '1':
        flag = flag ^ 1  # flagを反転
    else:
        if (query[2] == '1' and not flag) or (query[2] == '2' and flag):
            s = query[4] + s
        else:
            s = s + query[4]

if not flag:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations, accumulate
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
import sys
def I(): return int(input())  # '123' -> 123
def Is(): return map(int, input().split())  # '123 456' -> 123, 456
def LI(): return list(map(int, input().split()))  # '123 456' -> [123, 456]
def TI(): return tuple(map(int, input().split()))  # '123 456' -> (123, 456)
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()  # 'aa bb' -> 'aa','bb' or ['aa','bb']
def LS(): return list(input())  # 'abc123' -> ['a','b','c','1','2','3']
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(1000000)
MOD = 1000000007
INF = float('inf')

s = S()
q = I()
flag = 0
ans = deque(s)

for i in range(q):
    query = input()
    if query[0] == '1':
        flag = flag ^ 1  # flagを反転
    else:
        if (query[2] == '1' and not flag) or (query[2] == '2' and flag):
            ans.appendleft(query[4])
        else:
            ans.append(query[4])

if not flag:
    print("".join(ans))
else:
    print("".join(reversed(ans)))
### BUGGY CODE ###

N = int(input())
A = input().split()
C = {}

def func01(S,key,C):
    #すでに計算済みの数字ならば計算結果を参照
    #計算未ならば 計算して 計算結果を追加
    if key in C.keys():
        sum_count = C.get(key)

    else:
        sum_count = 0
        B = set(S)

        if len(B) == N:
            sum_count = 0
        else:
            for s in B:
                count_s = S.count(s)
                sum_count += (count_s * (count_s - 1) // 2)
            C.update({key: sum_count})
    print(sum_count)


for i in range(N):
    X = A[0:i] + A[i + 1:N]
    func01(X, A[i], C)

### FIXED CODE ###

import collections

N = int(input())
A = input().split()

#A_set = set(A)

#ボールに書かれている 数字の内訳を辞書に登録
A_dic = collections.Counter(A)

#すべてのボールから同じボールを取り出す方法数
all_count = 0

for a in A_dic.keys():
    count_a = A_dic.get(a)
    all_count += (count_a * (count_a - 1) // 2)

#n個あるボールから 1個取り除いた場合の方法数
#すべてのボールから取り出す方法数 - (n-1)通り

for i in range(N):
    print(all_count - A_dic.get(A[i])+1)
### BUGGY CODE ###

from heapq import heappush, heappop
from collections import defaultdict

INF = float('inf')
def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    dist = {v: INF for v in V}
    heap = []
    dist[s] = 0; rem = len(V);
    heappush(heap, (0, s))
    while heap and rem:
        d, v = heappop(heap)
        # don't need to check when the stored value is greater than provisional distance
        if d > dist[v]: continue
        rem -= 1;
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(heap, (temp, u))
    return dist

N, M = map(int, input().split())
V = list(range(N))
E = defaultdict(dict)
for _ in range(M):
    l, r, c = map(int, input().split())
    l, r = l-1, r-1
    E[l][r] = min(c, E[l].setdefault(r, INF))
    for i in range(l, r+1):
        E[i+1][i] = 0
dist = dijkstra(V, E, 0)
print(dist[N-1] if dist[N-1] != INF else -1)

### FIXED CODE ###

from heapq import heappush, heappop
from collections import defaultdict

INF = float('inf')
def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    dist = {v: INF for v in V}
    heap = []
    dist[s] = 0; rem = len(V);
    heappush(heap, (0, s))
    while heap and rem:
        d, v = heappop(heap)
        # don't need to check when the stored value is greater than provisional distance
        if d > dist[v]: continue
        rem -= 1;
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(heap, (temp, u))
    return dist

N, M = map(int, input().split())
V = list(range(N))
E = defaultdict(dict)
for i in range(N):
    E[i+1][i] = 0
for _ in range(M):
    l, r, c = map(int, input().split())
    l, r = l-1, r-1
    E[l][r] = min(c, E[l].setdefault(r, INF))
dist = dijkstra(V, E, 0)
print(dist[N-1] if dist[N-1] != INF else -1)
### BUGGY CODE ###

import sys  
input = sys.stdin.readline  

N, Q = list(map(int, input().split()))
S = input()
l = [None]*Q
r = [None]*Q
for i in range(Q):
    l[i], r[i] = list(map(int, input().split()))

S.split("AC")

s = list(S)

for k in range(Q):
    z = "".join(s[l[k]-1:r[k]])
    print(len(z.split("AC"))-1)


### FIXED CODE ###

import sys  
from itertools import accumulate
input = sys.stdin.readline  

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

l = [None]*Q
r = [None]*Q
for i in range(Q):
    l[i], r[i] = list(map(int, input().split()))

s = list(S)
ac = [0] * N

for i in range(N-1):
    if s[i] == 'A':
        if s[i+1] == 'C':
            s[i] = "AC"
            ac[i] += 1

ans = list(accumulate(ac))
ans = [0] + ans


for i in range(Q):
    print(ans[r[i]-1]- ans[l[i]-1])
### BUGGY CODE ###

import math

def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = math.gcd(a,l[i])
    return a

K = int(input())
list_A=[]
for i in range(K):
    for j in range(K):
        for k in range(K):
            list_A.append(gcdlist([i+1,j+1,k+1]))
print(sum(list_A))

### FIXED CODE ###

import math


K = int(input())
S=0
for i in range(1,K+1):
    for j in range(1,K+1):
        s=math.gcd(i,j)
        for k in range(1,K+1):
            S += math.gcd(s,k)

print(S)
### BUGGY CODE ###

import numpy as np
n=int(input())
s=[a for a in input()]
x = []
for a in s:
    if a == '.':
        x.append(0)
    else:
        x.append(1)
s = np.array(x)
ans = np.zeros(n).astype(np.uint8)
cnt = np.sum(s != ans)
for i in range(n):
    ans[-1 * (i+1)] = 1
    _cnt = np.sum(s != ans)
    if cnt > _cnt:
        cnt = _cnt
print(cnt)


### FIXED CODE ###

n=int(input())
s=input()
cnt =s.count('#')
l =[cnt]
for i in range(n):
    if s[n-i-1] == '#':
        cnt -= 1
        l.append(cnt)
    else:
        cnt+=1
        l.append(cnt)
print(min(l))
### BUGGY CODE ###

T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

ans = 0
d0 = 0
while True:
    d1 = d0 + (T1 * A1 - T1 * B1)
    d2 = d1 + (T2 * A2 - T2 * B2)
    # print(d0, d1, d2)

    if d2 == 0:
        ans = 'infinity'
        break

    c = 0
    if d0 == 0:
        if d1 == 0:
            c = 1
        elif d1 * d2 < 0:
            c = 1
    else:
        if d1 == 0:
            c = 1
        else:
            if d0 * d1 < 0:
                c += 1
            if d1 * d2 < 0:
                c += 1

    if c == 0:
        break
    else:
        ans += c
        d0 = d2

print(ans)


### FIXED CODE ###

T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

d = (T1 * A1 - T1 * B1) + (T2 * A2 - T2 * B2)
d1 = (T1 * A1 - T1 * B1)

import math
if d == 0:
    ans = 'infinity'
else:
    ans = 0

    # T1
    if d1 == 0:
        ans += 1
    elif d * d1 < 0:
        ans += abs(d1) // abs(d)

    # T2
    if d1 * d < 0:
        ans += math.ceil(abs(d1) / abs(d))

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

count = 0
scounts = []
N = int(input())
for n in range(N):
    s = sorted(input())
    found = False
    for scount in scounts:
        # print("s="+str(s))
        # print("scount[0]="+str(scount[0]))
        if scount[0] == s:
            found = True
            count += scount[1]
            scount[1] += 1
            break
    if not found:
        scounts.append([s, 1])
print(count)


### FIXED CODE ###

ss = []
N = int(input())
for n in range(N):
    s = sorted(input())
    ss.append(s)

ss = sorted(ss)

total = 0
count = 0
for n in range(N):
    if n==0:
        continue
    # print("ss["+str(n-1)+"]="+str(ss[n-1]))
    # print("ss["+str(n)+"]="+str(ss[n]))
    if ss[n-1]==ss[n]:
        count += 1
    else:
        total += int(count*(count+1)/2)
        count = 0
    # print("===")
total += int(count*(count+1)/2)
count = 0

print(int(total))
### BUGGY CODE ###

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

answer = 0
mod = 1000000007
for i in range(N-1):
  for j in range(i+1, N):
    answer += ((A[i] % mod) * (A[j] % mod)) % mod
    answer %= mod
print(int(answer))

### FIXED CODE ###

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

answer = 0
a_sum = sum(A)
mod = 10**9+7

for i in range(N-1):
  a_sum -= A[i]
  answer += a_sum * A[i]
print(str(answer % mod))
### BUGGY CODE ###

S = input()
Q = int(input())

ans = S
for i in range(Q):
    qry = list(input().split())
    if qry[0] == '1':
        ans = ans[::-1]

    elif qry[0] == '2':
        if qry[1] == '1':
            ans = qry[2] + ans
        elif qry[1] == '2':
            ans += qry[2]

print(ans)

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())

flag = 1
for i in range(Q):
    qry = input().split()

    if qry[0] == '1':
        if flag:
            flag = 0
        else:
            flag = 1
    
    elif qry[0] == '2':
        if flag:
            if qry[1] == '1':
                S.appendleft(qry[2])
            else:
                S.append(qry[2])
        else:
            if qry[1] == '1':
                S.append(qry[2])
            else:
                S.appendleft(qry[2])

S = ''.join(S)

if flag:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(4100000)

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def findminsum(lst,K,N):
    inf=10**6
    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]


def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    # cards=list(filter(lambda x:x<K,cards))
    # N=len(cards)
    cards.sort()
    ci=list(range(N))
    def inneccesity(h):
        if cards[h]>=K:
            return False
        else:
            c=cards[h]
            cards[h]=0
            ret=findminsum(cards,K-c,N)>=K
            cards[h]=c
            return ret
    #nn=0
    nn=biser(ci,inneccesity)
    # for i in range(N):
    #     if cards[i]<K:
    #         c=cards[i]
    #         cards[i]=0
    #         if findminsum(cards,K-c,N)>=K:
    #             nn+=1
    #         cards[i]=c
    #     else:
    #         break
    print(nn+1)

if __name__=='__main__':
    main()


### FIXED CODE ###

#4 9
#1 3 5 6
#の時に1（正解は0）と出力されるがACになる

N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
mae = 1
for i in range(K):
    mae *= A[i]
for i in range(N-K):
    ato = mae/A[i]*A[i+K]
    if ato > mae:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(N-K):
    if A[i] < A[i+K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
s=1
for i in range(N):
    s*=A[i]
if s<=10**18:
    print(s)
else:
    print(-1)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
s=1
if 0 in A:
    print(0)
    exit()
for i in range(N):
    s*=A[i]
    if s>10**18:
        print(-1)
        exit()
print(s)
### BUGGY CODE ###

s = input()
n = int(input())
for _ in range(n):
    head = ''
    tail = ''
    q = input()
    if q[0] == '1':
        s = s[::-1]
    else:
        _, f, c = q.split()
        if f == '1':
            head = c
        else:
            tail = c
    s = head + s + tail
print(s)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#h,w,k = [int(i) for i in read().split()]


s = input()
u = ""
t = ""
q = int(input())
num = 0

for _ in range(q):
    a = readline().split()
    if len(a)==1:
        u,t = t,u
        num ^= 1
    else:
        f = int(a[1])
        c = a[2]
        if f==1:
            t += c
        else:
            u += c

if num:
    print(t[::-1]+s[::-1]+u)
else:
    print(t[::-1]+s+u)
### BUGGY CODE ###

# -*- using:utf-8 -*-
class main:
  def function(x, k, d):
    for i in range(k):
      if abs(x + d) > abs(x - d):
        x = x - d
      elif abs(x + d) < abs(x - d):
        x = x + d
      else:
        if (k - i) % 2 == 0:
          return abs(x)
          break
        else:
          return abs(x + d)
          break
    return abs(x)

if __name__ == "__main__":
  x, k, d = map(int, input().split())
  x = main.function(x, k, d)
  print(x)

### FIXED CODE ###

# -*- using:utf-8 -*-

class main:
  def function(x, k, d):
    if x >= k * d:
      ans = x - k * d
    else:
      r = x // d
      n = k - r
      if n % 2 == 0:
        ans = x % d
      else:
        ans = abs(x % d - d)
    return ans

if __name__ == "__main__":
  x, k, d = map(int, input().split())
  x = abs(x)
  ans = main.function(x, k, d)
  print(ans)