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

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

# x = 0 に v = 0 の寿司があると考える
X = [0]
V = [0]

for _ in range(N):
    x, v = map(int, input().split())
    X.append(x)
    V.append(v)
# print(X)
# print(V)

# 0, v_1, v_1+v_2, v_1+v_2+v_3, ...
cumsum1 = [0]
for i in range(1, N + 1):
    cumsum1.append(cumsum1[-1] + V[i])

# 0, v_N, v_N+v_N-1, v_N+v_N-1+v_N-2, ...
cumsum2 = [0]
for i in range(N, 0, -1):
    cumsum2.append(cumsum2[-1] + V[i])

# print(cumsum1)
# print(cumsum2)

# 歩く範囲を弧ABと考える(A<=B)
# x_A = 0, x_1, x_2, ..., x_N
# x_B = x_A, ..., x_N
ans = 0

for i in range(N + 1):
    for j in range(i + 1, N + 1):
        # print(i, j)
        a = X[i]
        b = X[j]
        if i == 0:
            # 反時計回り(反転しない)
            ans = max(ans, cumsum1[j] - b)
            # 時計回り(反転しない)
            ans = max(ans, cumsum2[N + 1 - j] - (C - b))
        else:
            # O -> A -> B(反転)
            ans = max(ans, cumsum1[i] + cumsum2[N + 1 - j] - 2 * a - (C - b))
            # O -> B -> A(反転)
            ans = max(ans, cumsum1[i] + cumsum2[N + 1 - j] - 2 * (C - b) - a)

print(ans)


### FIXED CODE ###

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

# x = 0 に v = 0 の寿司があると考える
X = [0]
V = [0]

for _ in range(N):
    x, v = map(int, input().split())
    X.append(x)
    V.append(v)

# 0, v_1, v_1+v_2, v_1+v_2+v_3, ...
cumsum1 = [0]
for i in range(1, N + 1):
    cumsum1.append(cumsum1[-1] + V[i])

# 0, v_N, v_N+v_N-1, v_N+v_N-1+v_N-2, ...
cumsum2 = [0]
for i in range(N, 0, -1):
    cumsum2.append(cumsum2[-1] + V[i])

# 歩く範囲を弧ABと考える(A<=B)
# x_A = 0, x_1, x_2, ..., x_N
# x_B = x_A, ..., x_N

# 0, v_1-x_1, v_1+v_2-x_2, v_1+v_2+v_3-x_3, ...
f1 = [0]
# 0, v_1-2*x_1, v_1+v_2-2*x_2, v_1+v_2+v_3-2*x_3, ...
f2 = [0]
for i in range(1, N + 1):
    f1.append(cumsum1[i] - X[i])
    f2.append(cumsum1[i] - 2 * X[i])

f1_max = [0]
for i in range(1, N + 1):
    f1_max.append(max(f1_max[-1], f1[i]))
f2_max = [0]
for i in range(1, N + 1):
    f2_max.append(max(f2_max[-1], f2[i]))

ans = 0
# Bを全探索（固定する）
for i in range(N + 1):
    if i == 0:
        continue
    else:
        # 0 -> B(反時計回り、反転なし)
        ans = max(ans, cumsum1[i] - X[i])
        # 0 -> B(時計回り、反転なし)
        ans = max(ans, cumsum2[N + 1 - i] - (C - X[i]))
        # 0 -> A -> B(反転)
        ans = max(ans, f2_max[i - 1] + cumsum2[N + 1 - i] - (C - X[i]))
        # 0 -> B -> A(反転)
        ans = max(ans, f1_max[i - 1] + cumsum2[N + 1 - i] - 2 * (C - X[i]))

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

a, b, k = map(int, input().split())

for _ in range(1, k+1):
    if a >= 1:
        a-=1
    elif b >= 1:
        b-=1

print(str(a) + " " + str(b))

### FIXED CODE ###

a, b, k = map(int, input().split())

if a >= k:
    a-=k
    print(a, b)
else:
    k -= a
    a = 0
    b = max(0, (b - k))
    print(a, b)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = []
for i in range(n):
    plus = 0
    minus = 0
    mod = i%2
    for j in range(n):
        if (i+j) % 2 == mod:
            plus += l[(i+j)%n]
        else:
            minus += l[(i+j)%n]
    ans.append(plus-minus)

print(*ans)



### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = []
plus = sum(l)
minus = 0
for j in range(1,n,2):  
        
    minus += l[(j)%n]
ans.append(plus-2*minus)
for i in range(1,n):
    ans.append(2*l[i-1]-ans[i-1])

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

a,b=map(int,input().split())
c=[int(x) for x in input().split()]
se=set()
import itertools
ok=False
for j in range(b):
    for i in itertools.permutations(c,r=j+1):
        if sum(i)>=a:
            ok=True
            break
    if ok:
        break
if ok:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a,b=map(int,input().split())
c=[int(x) for x in input().split()]

if sum(c)>=a:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

M=10**9+7
n=int(input())
l=list(map(int,input().split()))
a=0
for i in range(60):
  t=sum(j>>i&1 for j in l)
  a+=(t*(n-t)<<i)%M
print(a%M)

### FIXED CODE ###

M=10**9+7
n=int(input())
l=list(map(int,input().split()))
a=0
for i in range(60):
  t=sum((l[j]>>i)%2 for j in range(n))
  a+=(t*(n-t)<<i)%M
print(a%M)
### BUGGY CODE ###

lst = list(map(int, input().split()))
a_lst = list(map(int, input().split()))
b_lst = list(map(int, input().split()))
c_lst = list(map(int, input().split()))

k = lst[3]
candidate = []
for n, a in enumerate(sorted(a_lst, reverse=True)):
    for m, b in enumerate(sorted(b_lst, reverse=True)):
        if (n+1)*(m+1) > k:
            break
        else:
            for l, c in enumerate(sorted(c_lst, reverse=True)):
                if (n+1)*(m+1)*(l+1) > k:
                    break
                else:
                    candidate.append(a+b+c)
for i in sorted(candidate, reverse=True)[:k]:
    print(i)

### FIXED CODE ###

x,y,z,k = map(int, input().split())
a_lst = sorted(list(map(int, input().split())), reverse=True)
b_lst = sorted(list(map(int, input().split())), reverse=True)
c_lst = sorted(list(map(int, input().split())), reverse=True)

candidate = []
for n in range(x):
    for m in range(y):
        if (n+1)*(m+1) > k:
            break
        else:
            for l in range(z):
                if (n+1)*(m+1)*(l+1) > k:
                    break
                else:
                    candidate.append(a_lst[n]+b_lst[m]+c_lst[l])
for i in sorted(candidate, reverse=True)[:k]:
    print(i)
### BUGGY CODE ###

N=int(input())
A=input().split()
answer=1
for i in range(N):
  answer=answer*int(A[i])
if answer>1*10**18:
  print(-1)
else:
  print(answer)


### FIXED CODE ###

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

import re
number=input()
number=number.replace("?",".",100000)
length=len(number)
i=0
sumnum=0
while True:
    checknum=str(13*i+5)
    checklength=len(checknum)
    if checklength<length:
        while len(checknum)!=length:
            checknum="0"+checknum

    if len(checknum)==length:
        m=re.match(number,checknum)
        if m:
            sumnum+=1
            sumnum=sumnum%1000000007
    
            
    if len(checknum)>length:
        break
    i+=1
    
print(sumnum)
    

### FIXED CODE ###

#数字はnumberに格納
number=input()
length=len(number)


#調整のための数字
sizemin=1000000007

#まずはからのDPリストを用意
dp=[[0 for i in range(13)] for j in range(length)]

#1桁目の情報を入力
if number[-1]=="?":
    for i in range(10):
        dp[0][i]=1
else:
    dp[0][int(number[-1])]=1

#１０〜９０の、13modリストを作る
modlist=[(i*10)%13 for i in range(10)]


        
#二桁目からの情報を更新していく。
for n in range(length-1):
    #n桁目の情報があれば、次のようにn+1行目を更新。

    #n+1のくらいの数をchecknumとする
    checknum=number[-1*(n+1)-1]
#     print(checknum)

    #n+1の位が整数であれば
    if checknum!="?":
        
        #n[m]の値をn+1[m+(その整数)]にすればいい
        for m in range(13):
            dp[n+1][(m+modlist[int(checknum)])%13]=dp[n][m]
#         print(dp)
        
        
        
        
        
    #n+1のくらいが？の時
    else:
    #？が０〜９までの可能性を全て試す  
    
        for checknum in range(10):
            for m in range(13):
                dp[n+1][(m+modlist[int(checknum)])%13]=(dp[n+1][(m+modlist[int(checknum)])%13]+dp[n][m])%sizemin
#             print(dp)

    #modlistを更新
    modlist=[(j*10)%13 for j in modlist]


print(dp[-1][5])
### BUGGY CODE ###

n = int(input())
ans = 0
p = [0,0]
now = [0,0]
p[0] = n%10
p[1] = 10 - n%10
n = n//10
ans = min(p[0], p[1] + 1)
while n > 0:
  now[0] = min(p[0] + n%10, p[1] + n%10 + 1)
  now[1] = min(p[0] + 10 - n%10, p[1] + 9 - n%10)
  ans = min(now[0], now[1] + 1)
  n = n//10
  p[0],p[1] = now[0],now[1]
print(ans)


### FIXED CODE ###

import sys
n = [int(i) for i in sys.stdin.readline().rstrip()[::-1]]
ans = 0
i = 0
p = [n[i],10 - n[i]]
now = [0,0]
i += 1
ans = min(p[0], p[1] + 1)
for i in range(1,len(n)):
  now[0] = min(p[0] + n[i]%10, p[1] + n[i]%10 + 1)
  now[1] = min(p[0] + 10 - n[i]%10, p[1] + 9 - n[i]%10)
  ans = min(now[0], now[1] + 1)
  p[0],p[1] = now[0],now[1]
print(ans)
### BUGGY CODE ###

import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

S = input()
N = len(S)

# dp[i][k]: i桁目までのkで割った余りの数
dp = create_grid(N+1, 13)

dp[0][0] = 1 # 0桁目

for i in range(N):
    c = S[N-i-1]
    if c == "?":
        v = range(10)
    else:
        v = [int(c)]
    for vi in v:
        for j in range(13):
            amari = (vi*(10**i) + j) % 13
            dp[i+1][amari] += dp[i][j]
    
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[N][5])



### FIXED CODE ###

import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

S = input()
N = len(S)

# dp[i][k]: i桁目までのkで割った余りの数
dp = create_grid(N+1, 13)

dp[0][0] = 1 # 0桁目

s = [1]
for i in range(N):
  s.append((s[-1]*10)%13)

for i in range(N):
    c = S[N-i-1]
    if c == "?":
        v = range(10)
    else:
        v = [int(c)]
    for vi in v:
        for j in range(13):
            amari = (vi*s[i] + j) % 13
            dp[i+1][amari] = (dp[i][j] + dp[i+1][amari]) % MOD

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

import numpy as np

N = int(input())
L = np.array(list(map(int, input().split())))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += sum(L[j+1:] < (L[i]+L[j]))
print(answer)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect_left(L[j+1:], L[i]+L[j])
print(answer)
### BUGGY CODE ###

Q=int(input())
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
l=[]
r=[]
for i in range(Q):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)
ml=[]
c=[0 for i in range(10**5+1)]
for i in range(1,10**5+1,2):
    ml=make_divisors(i)
    if len(ml)==2:
        n=make_divisors((i+1)//2)
        if len(n)==2:
            c[i]=1
#print(c)
ans=[]
for i in range(Q):
    ad=sum(c[l[i]:r[i]+1])
    ans.append(ad)
    print(ans[i])

### FIXED CODE ###

M=10**6
p=[1]*M
p[0]=p[1]=0
for i in range(2,4*10**4):
    if p[i]:
        for j in range(i*i,M,i):
            p[j]=0
C=[0]*M
for i in range(2,M):
    if p[i] and p[(i+1)//2]:
        C[i]=C[i-1]+1
    else:
        C[i]=C[i-1]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(C[r]-C[l-1])
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = [0]*q
score = [k]*n
for i in range(q):
    a[i] = int(input())
    for j in range(n):
        if j != a[i]-1:
            score[j] -= 1

for i in range(n):
    if score[i] <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n,k,q = map(int,input().split())
a = [0]*q
# score = [k]*n
count = [0]*n
for i in range(q):
    a[i] = int(input())
    count[a[i]-1] += 1

g = k-q

for i in range(n):
    if g > 0:
        print('Yes')
    else:
        if count[i] > abs(g):
            print('Yes')
        else:
            print('No')
### BUGGY CODE ###

S=list(input())
Q=int(input())
for i in range(Q):
    T=input().split()
    if T[0]=="1":
        S=list(reversed(S))
        continue
    if T[1]=="1":
        S=[T[2]]+S
        continue
    S=S+[T[2]]
print("".join(S))

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
r=1
for i in range(Q):
    T=input().split()
    if T[0]=="1":
        r*=-1
        continue
    t=T[2]
    if T[1]=="1":
        if r==1:
            S.appendleft(t)
        else:
            S.append(t)
        continue
    if r==1:
        S.append(t)
    else:
        S.appendleft(t)
if r==1:
    print("".join(list(S)))
else:
    S.reverse()
    print("".join(list(S)))
### BUGGY CODE ###

def main():
    n = int(input())
    al = list(map(int, input().split()))

    base_2_cnt = [0]*60 
    for a in al:
        for i in range(60):
            if ((a >> i) & 1): base_2_cnt[i] += 1

    ans = 0
    curr_2 = 1
    for i in range(60):
        base_01_comb = base_2_cnt[i] * (n-base_2_cnt[i])
        ans += base_01_comb * curr_2
        ans %= 10**9+7
        curr_2*=2

    print(ans%(10**9+7))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    MOD = 10**9+7
    n = int(input())
    al = list(map(int, input().split()))

    base_2_cnt = [0]*60 
    for a in al:
        for i in range(60):
            if ((a >> i) & 1): base_2_cnt[i] += 1

    ans = 0
    curr_2 = 1
    for i in range(60):
        base_01_comb = base_2_cnt[i] * (n-base_2_cnt[i])
        ans += base_01_comb * curr_2
        ans %= MOD
        curr_2*=2
        curr_2%=MOD

    print(ans%MOD)

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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Feb 10 10:05:08 2019

@author: shinjisu
"""


# ARC 077 C
def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def dmp(x):
    global debug
    if debug:
        print(x)


def probC_TLE():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    b = []
    for i in range(N):
        b.append(A[i])
        b.reverse()
        dmp(b)
    return b


def probC():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    former, latter = [], []
    for i in range(-1, -N-1, -1):
        if i % 2 == 0:
            latter = [A[i]] + latter
        else:
            former.append(A[i])
        full = former + latter
        dmp((former, latter, full))
    return full


debug = False
for n in probC():
    print(n, end=' ', flush=True)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Feb 10 10:05:08 2019

@author: shinjisu
"""


# ARC 077 C
def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def dmp(x):
    global debug
    if debug:
        print(x)


def probC_TLE():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    b = []
    for i in range(N):
        b.append(A[i])
        b.reverse()
        dmp(b)
    return b


def probC_TLE2():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    former, latter = [], []
    for i in range(-1, -N-1, -1):
        if i % 2 == 0:
            latter = [A[i]] + latter
        else:
            former.append(A[i])
        full = former + latter
        dmp((former, latter, full))
    return full


def probC_TLE3():
    N = getInt()
    A = [x for x in input().split()]
    dmp((N, A))
    former, latter = '', ''
    for i in range(-1, -N-1, -1):
        if i % 2 == 0:
            latter = A[i] + ' ' + latter
        else:
            former = former + ' ' + A[i]
        dmp((former, latter))
    return former[1:] + ' ' + latter


def probC():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    b = zeros(N)
    for i in range(-1, -N-1, -1):
        if i % 2 == 0:
            b[i//2] = A[i]
        else:
            b[-i//2] = A[i]
        dmp(b)
    return b


debug = False
# print(probC())
for n in probC():
    print(n, end=' ', flush=True)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [0]*M
b = [0]*M
c = [0]*M
for i in range(M):
    a[i], b[i] = map(int, input().split())
    cc = list(map(int, input().split()))
    for ccc in cc:
        ccc -= 1
        c[i] += (1 << ccc)

INF = float('inf')
dp = [[INF]*5000 for _ in range(M+1)]
dp[0][0] = 0

for i in range(M):
    for j in range((1 << N)):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        nj = j | c[i]
        dp[i+1][nj] = min(dp[i+1][nj], dp[i][j] + a[i])
if dp[M][(1 << N)-1] == INF:
    print(-1)
else:
    print(dp[M][(1 << N)-1])


### FIXED CODE ###

N, M = map(int, input().split())
a = [0]*M
b = [0]*M
c = [0]*M
for i in range(M):
    a[i], b[i] = map(int, input().split())
    cc = list(map(int, input().split()))
    for ccc in cc:
        ccc -= 1
        c[i] += (1 << ccc)

INF = float('inf')
dp = [[INF]*5000 for _ in range(M+1)]
dp[0][0] = 0

for i in range(M):
    for j in range((1 << N)):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        nj = j | c[i]
        dp[i+1][nj] = min(dp[i+1][nj], dp[i][j] + a[i])
if dp[M][(1 << N)-1] == INF:
    print(-1)
else:
    print(dp[M][(1 << N)-1])
### BUGGY CODE ###

N = int(input())
S = list(input())
i = 1
cnt = 0
while i < len(S):
    if S[i-1] == S[i]:
        cnt += 1
    else:
        cnt = 0
    if cnt >= 4:
        S.pop(i)
    else:
        i += 1
#print(S)
pin = [0] * 1000
for i in range(len(S) - 2):
    for j in range(i + 1 , len(S) - 1):
        for k in range(j + 1 , len(S)):
            now = S[i] + S[j] + S[k]
            pin[int(now)] = 1
            if all(pin):
                print(sum(pin))
                exit()
print(sum(pin))


### FIXED CODE ###

N = int(input())
S = input()
pattern = [False] * 1000

for i in range(1000):
    str_i = str(i)
    str_i = str_i.zfill(3)
    now = 0
    for c in S:
        if c == str_i[now]:
            now += 1
        if now == 3:
            pattern[i] = True
            break
print(sum(pattern))
### BUGGY CODE ###

import collections
N = int(input())
s = [collections.Counter(input()) for i in range(N)]
ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        if s[i] == s[j]:
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
s = [sorted(input()) for i in range(N)]
s.sort()
ans = 0
for i in range(N-1):
    if s[i] == s[i+1]:
        start = i
        end = N-1
        while start != end:
            center = (start + end) // 2
            if s[center] == s[i]:
                if s[center+1] == s[i]:
                    start = center+1
                else:
                    start = end = center
            else:
                end = center
        ans += start - i
print(ans)
### BUGGY CODE ###

from collections import deque

n = int(input())
e = [list(map(int, input().split())) for _ in range(n-1)]
c = [0 for _ in range(n-1)]

cmap = [[0 for _ in range(n)] for _ in range(n)]
for l in e:
    cmap[l[0]-1][l[1]-1] = cmap[l[1]-1][l[0]-1]=-1
    
d = deque()
d.append(1)
while(d):
    ed = d.pop() -1
    clist = list()
    usedc = set()
    for i in range(n):
        if cmap[ed][i]:
            clist.append([i, cmap[ed][i]])
            usedc.add(cmap[ed][i])
    for color in clist:
        if color[1] == -1:
            d.append(color[0]+1)
            cn = 1
            while(1):
                if cn in usedc:
                    cn+=1
                else:
                    usedc.add(cn)
                    break

            cmap[ed][color[0]] = cmap[color[0]][ed] = cn

for i in range(n-1):
    c[i] = cmap[e[i][0]-1][e[i][1]-1]

print(max(c))
for num in c:
    print(num)

### FIXED CODE ###

from collections import deque
n = int(input())

ls = [list() for _ in range(n)]
ls2 = [list() for _ in range(n)]
edge = []
for i in range(n-1):
    x,y = map(int,input().split())
    ls[x-1].append(i)
    ls2[y-1].append(i)
    edge.append([x-1,y-1])

d = deque()
color = [0]*(n-1)
d.append(0)
while len(d):
    c = d.pop()
    cl = []
    for i in ls2[c]:
        if color[i]:
            cl.append(color[i])
    idx = 1
    for i in ls[c]:
        while(1):
            if not idx in cl:
                break
            else:
                idx += 1
        color[i] = idx
        cl.append(idx)
        d.append(edge[i][1])

print(max(color))
for i in color:
    print(i)
### BUGGY CODE ###

def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 200000, 250000,300000,350000, 400000,450000, 500000,550000,600000,630000,675000,750000,800000,850000,900000,925000,950000,975000,1000000]
datas = [0,23,473,7053,93643,1166714, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,7354651,8075420,8509899,9164377,10261678,10997400,11736253,12478098,12850013,13222660,13595947,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])


### FIXED CODE ###

def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 150000,200000, 250000,300000,350000, 400000,450000, 500000,550000,600000,630000,675000,700000,720000,750000,800000,825000,850000,875000,900000,912500,925000,950000,975000,987500,1000000]
datas = [0,23,473,7053,93643,1166714, 1810893, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,7354651,8075420,8509899,9164377,9529244,9821778,10261678,10997400,11366472,11736253,12106789,12478098,12664043,12850013,13222660,13595947,13782871,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])
### BUGGY CODE ###

X, K, D = map(int, input().split())

X = abs(X)

final = -1

for n in range(K):
  X = abs(X - D)
  if X <= D / 2:
    if (K-n) % 2 == 0:
      final = abs(X-D)
      break
    else:
      final = X
      break

if final >= 0:
  print(final)
else:
  print(X)

### FIXED CODE ###

X, K, D = map(int, input().split())

X = abs(X)

final = -1

q, n = X % D, X // D

if n >= K:
  print(X - K * D)
else:
  if q <= X / 2:
    if (K - n) % 2 == 0:
      print(q)
    else:
      print(D - q)
  else:
    if (K - n) % 2 == 0:
      print(q)
    else:
      print(D - q)