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

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

def c(arr):
  arr.sort(reverse=True)
  l=len(arr)
  num=(l+1)//2 - 1
  return arr[num]

for i in range(n):
  a=x[:i]+x[i+1:]
  print(c(a))

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
arr=sorted(x)[n//2-1:n//2+1]
for i in range(n):
  if x[i]<=arr[0]:
    print(arr[1])
  elif x[i]>=arr[1]:
    print(arr[0])
### BUGGY CODE ###

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

ans = []

for i in range(1, N + 1):
    ans.append(A.index(i) + 1)

ans = list(map(str, ans))
print(" ".join(ans))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(range(1, N + 1))

A = dict(zip(A, B))
A = sorted(A.items())
ans = [str(x[1]) for x in A]


print(" ".join(ans))
### BUGGY CODE ###

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

### FIXED CODE ###

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

#input
H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

#output
M = max(A)
inf = 10**10
dp = [inf]*(H+(M+1))
dp[0] = 0
for i in range(N):
    for j in range(A[i], H+M):
        dp[j] = min(dp[j], dp[j-A[i]] + B[i])

answer = min(dp[H:(H+M+1)])
print(answer)

### FIXED CODE ###

#input
H, N = map(int, input().split())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())

#output
M = max(A)
inf = 10**10
dp = [inf]*(H+(M+1))
dp[0] = 0
for i in range(N):
    for j in range(A[i], H+M):
        dp[j] = min(dp[j], dp[j-A[i]] + B[i])

answer = min(dp[H:(H+M+1)])
print(answer)
### BUGGY CODE ###

h,w=map(int,input().split())

A=[]
for i in range(h):
    A.append(list(map(int,input().split())))

B=[]

for i in range(h):
    for j in range(w):
        if A[i][j]%2==1 :
            B.append([i,j])

C=[]
for i in range(len(B)//2):
    b00=B[2*i][0]
    b01=B[2*i][1]
    b10=B[2*i+1][0]
    b11=B[2*i+1][1]
    
    while b00>b10 :
        C.append([b00,b01,b00-1,b01])
        b00-=1

    while b00<b10 :
        C.append([b00,b01,b00+1,b01])
        b01+=1

    while b01>b11 :
        C.append([b00,b01,b00,b01-1])
        b01-=1

    while b01<b11 :
        C.append([b00,b01,b00,b01+1])
        b01+=1
print(len(C))
for i in range(len(C)):
    print(str(C[i][0]+1)+" "+str(C[i][1]+1)+" "+str(C[i][2]+1)+" "+str(C[i][3]+1))


### FIXED CODE ###

h,w=map(int,input().split())

A=[]
for i in range(h):
    A.append(list(map(int,input().split())))

if h==1 and w==1 :
    print(0)
else:


    aa=0
    C=[]
    ha=0
    s=1
    a=0
    b=0
    for i in range(h*w):
        if A[a][b]%2==1 :
            ha=(ha+1)%2
        if ha==1:
            if b+s<w and b+s>=0 :
                C.append([a,b,a,b+s])
            elif a<h :
                C.append([a,b,a+1,b])
        if ha==0 :
            aa=len(C)

        if b+s<w and b+s>=0 :
            b+=s
        else:
            a+=1
            s = -s

            
    print(aa)

    for i in range(aa):
        print(str(C[i][0]+1)+" "+str(C[i][1]+1)+" "+str(C[i][2]+1)+" "+str(C[i][3]+1))
### BUGGY CODE ###

N = int(input())

L = list(sorted(map(int, input().split()), key=lambda x: -x))

ret = 0


def is_ok(a, b, c):
    return a < b + c and b < a + c and c < a + b


for i in range(N - 2):
    for j in range(i + 1, N - 1):
        p = j + 1
        q = N + 1
        while q - p > 2:
            k = (p + q) // 2
            if is_ok(L[i], L[j], L[k]):
                p = k
            else:
                q = k

        if is_ok(L[i], L[j], L[p]):
            ret += p - j

print(ret)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(sorted(map(int, input().split())))

res = 0

for i in range(N):
    for j in range(i + 1, N):
        k = bisect_left(L, L[i] + L[j])

        res += k - j - 1

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

INF  = float("inf") # 正の無限大

N, K = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

H = list( map(int, input().split()) )	# 1 2 3 4 5 ...

C = [INF]*(N)
C[0] = 0

for i in range(N):
	for k in range(1, K+1):
		j = i + k
		if N<=j: break
		c = abs(H[i] - H[j])
		C[j] = min(C[j], C[i]+c)

print(C[-1])


### FIXED CODE ###

inf = float("inf") # 正の無限大

N,K=map(int, input().split())
H=[0]+list(map(int, input().split()))
#print(N,H)

dp=[inf]*(N+1)
dp[1]=0
dp[2]=abs(H[2]-H[1])

for i in range(3,N+1):
	for k in range(1,K+1):
		if (i-k)>0:
			a = dp[i-k]+abs(H[i]-H[i-k])
			if dp[i]>a: dp[i]=a

print( dp[N] )
### BUGGY CODE ###

import hashlib

n = int(input())
s = input()


objects = []
l = [[] for i in range(n//2+1)]


for i in range(n):
    objects.append(hashlib.md5())


for size in range(1, n//2+1):
    for i in range(n - size + 1):
        h = objects[i]
        h.update(s[i].encode())
        l[size].append(h.hexdigest())


def output():
    left, right = 0, n//2+1
    while left < right-1:
        mid = (left+right)//2
        if check(l[mid]):
            left = mid
        else:
            right = mid
    return left


def check(li):
        hashes = set()
        for h in li:
            if h in hashes:
                return True
            hashes.add(h)
        return False


print(output())

### FIXED CODE ###

import hashlib

n = int(input())
s = input()


def output():
    left, right = 0, n//2+1
    while left < right-1:
        mid = (left+right)//2
        if check(mid):
            left = mid
        else:
            right = mid
    return left


def check(x):
    hashes = set()
    for i in range(n - 2*x + 1):
        hashes.add(s[i: i+x])
        if s[i+x: i+2*x] in hashes:
            return True
    return False


print(output())
### BUGGY CODE ###

import sys
from collections import deque


H,W=map(int, raw_input().split())
A=[ list( sys.stdin.readline())  for i in range(H) ]


D=[ (-1,0),(1,0),(0,1),(0,-1)]


def bfs(h,w):
	V=[ [ 0 for j in range(W) ] for i in range(H)  ]
	K=[ [ 0 for j in range(W) ] for i in range(H)  ]  #Kyori
	q=deque()
	V[h][w]=1
	q.append( (h,w) )
	while q:
		h, w=q.popleft()	# newh , neww
		for dx,dy in D:
			if 0<=h+dx<H and 0<=w+dy<W:
				if A[h+dx][w+dy]=="#":
					return K[h][w]+1
				if A[h+dx][w+dy]=="." and V[h+dx][w+dy]==0:
					V[h+dx][w+dy]=1
					K[h+dx][w+dy]=K[h][w]+1
					q.append( (h+dx,w+dy) )	

ans=0	
for i in range(H):
	for j in range(W):
		ans=max(ans, bfs(i,j) )


print ans


### FIXED CODE ###

import sys
from collections import deque

H,W=map(int, raw_input().split())
A=[ list( sys.stdin.readline().strip())  for i in range(H) ]


D=[ (-1,0),(1,0),(0,1),(0,-1) ]
K=[ [ float("inf") for j in range(W) ] for i in range(H)  ]  #Kyori

q=deque()

for i in range(H):
	for j in range(W):
		if A[i][j]=="#":
			q.append( (i,j) )
			K[i][j]=0


while q:
	h,w=q.popleft()
	for dx,dy in D:
		if 0<=h+dx<H and 0<=w+dy<W and K[h+dx][w+dy]>K[h][w]+1:
				K[h+dx][w+dy]=K[h][w]+1
				q.append( (h+dx,w+dy) )	

ans=0
for x in K:
	ans=max(ans, max(x) )
print ans
### BUGGY CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


K = int(input())
sumGCD = K * K * K
for a in range(2, K + 1, 1):
    for b in range(2, K + 1, 1):
        for c in range(2, K + 1, 1):
            arr = [a, b, c]
            gcdNum = gcd(*arr)
            # if gcdNum != 1:
            # print(arr)
            # print(gcdNum)
            sumGCD += gcdNum - 1
print(sumGCD)


### FIXED CODE ###

import math

K = int(input())
sumGCD = K * K * K
for a in range(2, K + 1, 1):
    for b in range(2, K + 1, 1):
        for c in range(2, K + 1, 1):
            arr = [a, b, c]
            gcdNum = math.gcd(math.gcd(a, b), c)
            # if gcdNum != 1:
            # print(arr)
            # print(gcdNum)
            sumGCD += gcdNum - 1
print(sumGCD)
### BUGGY CODE ###

import bisect

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

cards = list(map(int, input().split()))
cards.sort()
ops = []
for i in range(M):
    B, C = map(int, input().split())
    ops.append({"B": B, "C": C})
ops.sort(key=lambda o: o["C"], reverse=True)
#print(cards)
#print(ops)

left = 0
for op in ops:
    length = bisect.bisect_left(cards, op["C"], lo=left) - left
    #print(length)
    # fill left..idx
    for i in range(op["B"]):
        if i < length:
            cards[left + i] = op["C"]
    left += min(length, op["B"])
#print(cards)
ans = 0
for val in cards:
    ans += val
print(ans)


### FIXED CODE ###

import bisect

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

cards = list(map(int, input().split()))
cards.sort()
ops = []
for i in range(M):
    B, C = map(int, input().split())
    ops.append({"B": B, "C": C})
ops.sort(key=lambda o: o["C"], reverse=True)
#print(cards)
#print(ops)

left = 0
for op in ops:
    length = bisect.bisect_left(cards, op["C"], lo=left) - left
    #print(length)
    # fill left..idx
    for i in range(min(length, op["B"])):
        cards[left + i] = op["C"]
    left += min(length, op["B"])
#print(cards)
ans = 0
for val in cards:
    ans += val
print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
a = deque( int(input()) for i in range(n))
for i in range(n):
    s = a.popleft()
    m = max(a)
    print(m)
    a.append(s)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m = max(a)
p = a.index(m)
a.remove(m)
s = max(a)
for i in range(n):
    if i != p:
        print(m)
    else:
        print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H,W = map(int,input().split())
#差分だけで良い，これを*1 or -1していく
diff = [list(map(int, input().split())) for _ in range(H)]

for i in range(H):
    B = list(map(int,input().split()))
    for j in range(W):
        diff[i][j] = abs(diff[i][j] - B[j])
        
 # i,jマスにおいて，偏りがkになれるかどうかでDP
K = 4001 #適当
kk = int((K-1)/2)
dp = [[[False]*K for _ in range(W)] for _ in range(H)]
 
dp[0][0][kk+diff[0][0]] = True
dp[0][0][kk-diff[0][0]] = True
 
for i in range(H):
    for j in range(W):
        a= min((i+j)*80,kk)
        for k in range(kk-a,kk+a+1):
            if i-1>=0:
                if k+diff[i][j]<K:
                    if dp[i-1][j][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i-1][j][k-diff[i][j]]:
                        dp[i][j][k] =True
            if j-1>=0:
                if k+diff[i][j]<K:
                    if dp[i][j-1][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i][j-1][k-diff[i][j]]:
                        dp[i][j][k] =True
ans = K

for k in range(K):
    if dp[-1][-1][k]:
        ans = min(ans,abs(k-kk))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H,W = map(int,input().split())
#差分だけで良い，これを*1 or -1していく
diff = [list(map(int, input().split())) for _ in range(H)]

for i in range(H):
    B = list(map(int,input().split()))
    for j in range(W):
        diff[i][j] = abs(diff[i][j] - B[j])
        
 # i,jマスにおいて，偏りがkになれるかどうかでDP
#dp[i][j]にはkという数字にたどり着けるかどうかを示す2進数を入れる

dp = [[False]*W for _ in range(H)]
ofs = 80*(H+W)


dp[0][0]=(1<<(ofs+diff[0][0]) | 1>>(ofs-diff[0][0]))
 
for i in range(H):
    for j in range(W):
        if i>0:
            dp[i][j]|=(dp[i-1][j]<<diff[i][j] | dp[i-1][j]>>diff[i][j])
        if j>0:
            dp[i][j]|=(dp[i][j-1]<<diff[i][j] | dp[i][j-1]>>diff[i][j])


#0のところから見て，最初に1が出てきたところが答え
for k in range(ofs):
    if (dp[-1][-1]>>(k+ofs)&1):
        print(k)
        break
### BUGGY CODE ###

import itertools
X, Y=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
MOD = 10**9 + 7
from math import factorial
# a = factorial(n+m) / factorial(n) / factorial(m)
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

# a = cmb(n, r)

if (X+Y)%3 != 0:
    print(0)
else:

    n = int((2*Y-X)/3)
    m = int((2*X-Y)/3)

    # print(f"n:{n}, m:{m}")

    if n<0 or m<0:
        print(0)
    else:
        # ret = 1
        # for i in range(m):
        #     ret = ret * ((X+Y)//3 - i) % MOD * pow(i + 1, MOD-2, MOD) % MOD
        # a = factorial(n+m) / factorial(n) / factorial(m)
        print(cmb(n+m, n)%MOD)

### FIXED CODE ###

import itertools
X, Y=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
MOD = 10**9 + 7
if (X+Y)%3 != 0:
    print(0)
else:

    n = int((2*Y-X)/3)
    m = int((2*X-Y)/3)

    # print(f"n:{n}, m:{m}")

    if n<0 or m<0:
        print(0)
    else:
        ret = 1
        for i in range(m):
            ret = ret * ((X+Y)//3 - i) % MOD * pow(i + 1, MOD-2, MOD) % MOD
        print(ret)
### BUGGY CODE ###

from collections import deque

H, W, K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = list(list(input())for _ in range(H))
cost = [[H*W+1]*W for _ in range(H)]
cost[x1-1][y1-1] = 0
queue = deque([[x1-1,y1-1]])
while queue:
    x,y = queue.popleft()
    for vecx,vecy in [[0,1],[1,0],[-1,0],[0,-1]]:
        for k in range(1,K+1):
            nx,ny = x+k*vecx, y+k*vecy
            if not(0<=nx<H) or not(0<=ny<W):
                break
            if c[nx][ny] == '@':
                break
            if cost[nx][ny] > cost[x][y]+1:
                cost[nx][ny] = cost[x][y]+1
                queue.append([nx,ny])
if cost[x2-1][y2-1] == H*W+1:
    print(-1)
else:
    print(cost[x2-1][y2-1])




### FIXED CODE ###

from collections import deque

H, W, K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = list(list(input())for _ in range(H))
cost = [[H*W+1]*W for _ in range(H)]
cost[x1-1][y1-1] = 0
queue = deque([[x1-1,y1-1]])
while queue:
    x,y = queue.popleft()
    for vecx,vecy in [[0,1],[1,0],[-1,0],[0,-1]]:
        for k in range(1,K+1):
            nx,ny = x+k*vecx, y+k*vecy
            if not(0<=nx<H) or not(0<=ny<W):
                break
            if c[nx][ny] == '@':
                break
            if cost[nx][ny] > cost[x][y]+1:
                cost[nx][ny] = cost[x][y]+1
                queue.append([nx,ny])
            elif cost[nx][ny] < cost[x][y]+1:
                break
if cost[x2-1][y2-1] == H*W+1:
    print(-1)
else:
    print(cost[x2-1][y2-1])
### BUGGY CODE ###

import heapq as hq
x, y, z, k = map(int,input().split())
arr_a = sorted(list(map(int,input().split())) ,reverse = True)
arr_b = sorted(list(map(int,input().split())) ,reverse = True)
arr_c = sorted(list(map(int,input().split())) ,reverse = True)

cnt = [[[0 for i in range(z)] for j in range(y)] for k in range(x)]
P_q = [[-(arr_a[0] + arr_b[0] + arr_c[0]),0,0,0]]

cnt[0][0][0] = 1
for _ in range(k):
    tmp = hq.heappop(P_q)
    t, i, j, k = -tmp[0],tmp[1],tmp[2],tmp[3]
    print(t)
    if i + 1 < x and cnt[i+1][j][k] == 0:
        hq.heappush(P_q,[-(arr_a[i+1] + arr_b[j] + arr_c[k]) ,i + 1,j,k])
        cnt[i+1][j][k] = 1
    if j + 1 < y and cnt[i][j + 1][k] == 0:
        hq.heappush(P_q,[-(arr_a[i] + arr_b[j+1] + arr_c[k]) ,i ,j + 1,k])
        cnt[i][j+1][k] = 1
    if k + 1 < z and cnt[i][j][k + 1] == 0:
        hq.heappush(P_q,[-(arr_a[i] + arr_b[j] + arr_c[k + 1]) ,i,j,k + 1])
        cnt[i][j][k + 1] = 1
        

### FIXED CODE ###

import heapq as hq
x, y, z, k = map(int,input().split())
arr_a = sorted(list(map(int,input().split())) ,reverse = True)
arr_b = sorted(list(map(int,input().split())) ,reverse = True)
arr_c = sorted(list(map(int,input().split())) ,reverse = True)

cnt = set()
P_q = [[-(arr_a[0] + arr_b[0] + arr_c[0]),0,0,0]]

cnt.add((0,0,0))
for _ in range(k):
    tmp = hq.heappop(P_q)
    t, i, j, k = -tmp[0],tmp[1],tmp[2],tmp[3]
    print(t)
    if i + 1 < x and (i+1,j,k) not in cnt:
        hq.heappush(P_q,[-(arr_a[i+1] + arr_b[j] + arr_c[k]) ,i + 1,j,k])
        cnt.add((i+1,j,k))
    if j + 1 < y and (i,j+1,k) not in cnt:
        hq.heappush(P_q,[-(arr_a[i] + arr_b[j+1] + arr_c[k]) ,i ,j + 1,k])
        cnt.add((i,j+1,k))
    if k + 1 < z and (i,j,k+1) not in cnt:
        hq.heappush(P_q,[-(arr_a[i] + arr_b[j] + arr_c[k + 1]) ,i,j,k + 1])
        cnt.add((i,j,k+1))
### BUGGY CODE ###

n,m = map(int,input().split())
l = [tuple(map(int,input().split())) for _ in range(m)]
d = [list() for _ in range(n)]
for x in l:
  d[x[0]-1].append(x[1])
for r in d:
  r.sort()
for x in l:
  p = x[0]
  y = d[x[0]-1].index(x[1]) + 1
  print("{:06}{:06}".format(p,y))

### FIXED CODE ###

n,m = map(int,input().split())
l = [tuple(map(int,input().split())) for _ in range(m)]
d = [list() for _ in range(n)]
dic = [dict() for _ in range(n)]
for x in l:
  d[x[0]-1].append(x[1])
for r in range(n):
  d[r].sort()
  dic[r] = dict(zip(d[r],range(1,len(d[r])+1)))
for x in l:
  p = x[0]
  y = dic[x[0]-1][x[1]]
  print("{:06}{:06}".format(p,y))
### BUGGY CODE ###

#
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n = int(input())
    s = input()
    if len(set(s)) == n:
        print(0)
        return

    if len(set(s)) == 1:
        print(n // 2)
        return 

    def same_length(i1, i2):
        i = 0
        count = 0
        while i1 + i < i2 and i2 + i < n:
            if s[i1 + i] != s[i2 + i]:
                break

            count += 1
            i += 1

        return count

    char_positions = defaultdict(list)
    for i, c in enumerate(s):
        char_positions[c].append(i)

    ans = 0
    for char in char_positions:
        char_count = len(char_positions[char])
        # print(char, char_count)
        if char_count < 2:
            continue
        for i in range(char_count - 1):
            for j in range(i + 1, char_count):
                ans = max(ans, same_length(char_positions[char][i], char_positions[char][j]))
                # print(char_positions[char][i], char_positions[char][j], ans)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n = int(input())
    s = input()
    if len(set(s)) == n:
        print(0)
        return

    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = -10**4

    for i in range(n):
        for j in range(i, n):
            if i == j:
                continue
            if s[i] == s[j]:
                if i > 0 and j > 0:
                    length = dp[i-1][j-1]
                    if j - length > i:
                        dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = 1

    ans = 0
    for d in dp:
        ans = max(ans, max(d))
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
blocks = []
for i in range(n):
    w_str, s_str, v_str = input().split(" ")
    w, s, v = int(w_str), int(s_str), int(v_str)
    blocks.append({"w": w, "s": s, "v": v})

def dp(blocks, max_s):
    max_val = 0
    for i in range(len(blocks)):
        taken =  blocks[i]

        # klo constraint nya
        new_max_s = 0
        if max_s is None:
            new_max_s = taken["s"]
        else:
            new_max_s = min(max_s-taken["w"], taken["s"])

        # ini constraint nya
        if new_max_s < 0:
            continue

        # remaining blocks, taruh sini, biar ga diitung kalau jelas ga mungkin
        remaining_blocks = [blocks[x] for x in range(len(blocks)) if x != i and blocks[x]["w"] <= new_max_s]

        # ini nilai tambahan
        taken_val = taken["v"]
        new_val = taken_val + dp(remaining_blocks, new_max_s)
        if new_val > max_val:
            max_val = new_val

    return max_val

print(dp(blocks, None))

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
WSV = list(tuple(map(int, input().split())) for _ in range(N))
WSV.sort(key=lambda x: x[0] + x[1])
U = 2 * 10 ** 4 + 100
dp = np.zeros(U, dtype=np.int64)
for w, s, v in WSV:
    dp[w:w+s+1] = np.maximum(dp[w:w+s+1], dp[:s+1] + v)
print(dp.max())
### BUGGY CODE ###

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

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

max_sum = 0
max_where = 0

#pi ~ pi+2の合計が最大のものが期待値も最大になる。
for i in range(0,n-k+1):
    temp_sum = sum(p[i:i+k])
    if temp_sum > max_sum:
        max_sum = temp_sum
        max_where = i

result = 0

for j in range(k):
    result += ((p[max_where + j] + 1) * p[max_where + j] / 2) / p[max_where + j]

print(result)

### FIXED CODE ###

from copy import deepcopy

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

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


max_sum = 0
temp_sum = 0

#最初の一組目を計算
for j in range(k):
    temp_sum += ((p[j] + 1) * p[j] / 2) / p[j]

if n == k:
    max_sum = temp_sum
    print(max_sum)

else:
    #2組目以降を計算
    for i in range(1,n-k+1):
        temp_sum = temp_sum - ((p[i-1] + 1) * p[i-1] / 2) / p[i-1] + ((p[i+k-1] + 1) * p[i+k-1] / 2) / p[i+k-1]

        if temp_sum > max_sum:
            max_sum = temp_sum


    print(max_sum)




#n,k = map(int,input().split())
#
#p = list(map(int,input().split()))
#
#max_sum = 0#for j in range(k):
#    result += ((p[max_where + j] + 1) * p[max_where + j] / 2) / p[max_where + j]
#max_where = 0
#
##pi ~ pi+2の合計が最大のものが期待値も最大になる。
#for i in range(0,n-k+1):
#    temp_sum = sum(p[i:i+k])
#    if temp_sum > max_sum:
#        max_sum = temp_sum
#        max_where = i
#
#result = 0
#

#
#print(result)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
base_point = 1
new_point = 1
time = N-K
for i in range(K):
    base_point *= A[K-1-i]
for i in range(time):
    new_point = A[K+i] * base_point//A[i]
    if(new_point>base_point):
        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[K+i]>A[i]):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
mn = max(a)
for i in range(n):
    if a[i] == mn:
        tmp = a[:i] + a[i+1:]
        print(max(tmp))
    else: print(mn)


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
mx = max(a)
mxi = a.index(mx)
mx2 = max(a[:mxi] + a[mxi+1:])

for i in range(n):
    if i == mxi: print(mx2) 
    else: print(mx)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    x, k, d = map(int, input().split())

    for i in range(k):
        if x > 0:
            x -= d
            if x < 0 and (k-1-i)%2 == 0:
                print(abs(x))
                return
            elif x < 0 and (k-1-i)%2 == 1:
                print(abs(x+d))
                return
        else:
            x += d
            if x > 0 and (k-1-i)%2 == 0:
                print(abs(x))
                return
            elif x > 0 and (k-1-i)%2 == 1:
                print(abs(x-d))
                return
    print(abs(x))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    x, k, d = map(int, input().split())
    desired = abs(x) // d
    if k <= desired:
        if x < 0:
            x += k * d
        else:
            x -= k * d
        print(abs(x))
        return
    if x < 0:
        x += desired * d
    else:
        x -= desired * d
    if (k - desired) % 2 == 0:
        print(abs(x))
        return
    if x == 0:
        print(d)
    elif x > 0:
        x -= d
        print(abs(x))
    elif x < 0:
        x += d
        print(abs(x))


if __name__ == '__main__':
    main()