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

# C
import copy

n, k = map(int, input().split())
a_list = [int(x) for x in input().split()]
o_list = copy.deepcopy(a_list)

for i in range(k):
    _o_list = [0]*n
    for j in range(n):
        _t = o_list[j]
        _s, _e = j-_t, j+_t
        for x in range(max(_s, 0), min(_e+1, n)):
            _o_list[x] += 1
    o_list = copy.deepcopy(_o_list)
    if o_list == [n]*n:
        break
print(*o_list)

### FIXED CODE ###

# C
import copy
import itertools

n, k = map(int, input().split())
a_list = [int(x) for x in input().split()]

for j in range(k):
    b_list = [0]*n
#     print("a:",*a_list)
    for i in range(n):
        l = max(0, i-a_list[i])
        r = min(n-1, i+a_list[i])
        b_list[l] += 1
        if r+1 < n:
            b_list[r+1] -= 1
#     print("b:",*b_list)
    cumsum = list(itertools.accumulate(b_list))
    if cumsum == [n]*n:
        break
    a_list = cumsum
print(*cumsum)
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    A=[list(map(int,input().split())) for i in range(n)]
    mod=10**9+7

    dp=[0]*(1<<n)
    dp[0]=1
    for s in range(1<<n):
        i=format(s,'b').count('1')
        for j in range(n):
            if (s>>j)&1 and A[i-1][j]==1:
              dp[s]+=dp[s^(1<<j)]
              dp[s]%=mod   
              
    print(dp[-1])
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    A=[list(map(int,input().split())) for i in range(n)]
    mod=10**9+7

    dp=[0]*(1<<n)
    dp[0]=1
    for s in range(1<<n):
        i=format(s,'b').count('1')
        for j in range(n):
            if (s>>j)&1 and A[i-1][j]==1:
              dp[s]+=dp[s^(1<<j)]
              dp[s]%=mod   
              
    print(dp[-1])
if __name__=='__main__':
    main()
### BUGGY CODE ###

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

R = 0
L = []
for i in range(N):
    if i == 0:
        L = [True] * N
    else:
        L = [L[j] and A[j]^A[i+j] == A[j]+A[i+j] and L[j+1] for j in range(N-i)] + [False]*(i) 
    R += sum(L)
    if sum(L) == 0:
        break
print(R)

### FIXED CODE ###

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

result = 0
Right = 0
tmp = 0
for left in range(N):
    for right in range(Right,N):
        if not (tmp & A[right]):
            tmp += A[right]
            Right = right + 1
        else:
            break
    tmp -= A[left]
    result += Right - left
print(result)
### BUGGY CODE ###

string=input()
length=len(string)
mod=[0]*2019
mod[0]=1
while length > 0:
  mod[int(string[length-1:])%2019]+=1
  length-=1
print(int(sum([(i*(i-1))/2 for i in mod])))


### FIXED CODE ###

string=input()
length=len(string)
mod=[1]+[0]*2018
s=0
for i in range(length):
  s=(s+int(string[-1-i])*pow(10,i,2019))%2019
  mod[s]+=1
print(sum([i*(i-1)//2 for i in mod]))
### BUGGY CODE ###

import math
from functools import reduce

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

K = int(input())
B = list()
a = int()
b = int()
c = int()
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            A = i,j,k
            B.append(A)
for i in range(len(B)):
    a = B[i][0]
    b = B[i][1]
    c = B[i][2]
    ans += gcd(a,b,c)
print(ans)

### FIXED CODE ###

import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
K = int(input())
B = list()
a = int()
b = int()
c = int()
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(i,j,k)
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
k = max(l)

ans = 0
for i in range(k + 1):
    ar = 0
    ab = 0
    for j in l:
        if j >= i:
          ar += 1
        else:
            ab += 1
    if ar == ab:
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
k = max(l)

a = sorted(l)
print(a[n // 2] - a[n // 2 - 1])
### BUGGY CODE ###

n = int(input())
query = [tuple(map(int, input().split())) for _ in range(n)]

x, y = 1, 1
for t, a in query:
    T, A = t, a
    while not (T >= x and A >= y):
        T += t
        A += a
    x = T
    y = A
print(x + y)

### FIXED CODE ###

n = int(input())
query = [tuple(map(int, input().split())) for _ in range(n)]

x, y = 1, 1
for t, a in query:
    if t >= x and a >= y:
        x = t
        y = a
    else:
        if t < x and a < y:
            x = t * max((x + t - 1) // t, (y + a - 1) // a)
            y = a * max((x + t - 1) // t, (y + a - 1) // a)
        elif t < x:
            x = t * ((x + t - 1) // t)
            y = a * ((x + t - 1) // t)
        else:
            x = t * ((y + a - 1) // a)
            y = a * ((y + a - 1) // a)
print(x + y)
### BUGGY CODE ###


from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append((sy, sx, 0))
        ans[sy][sx] = 0

        while q:
            sy, sx, cost = q.popleft()
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                if 0 <= ny < H and 0 <= nx < W:
                    if G[ny][nx] == "." and ans[ny][nx] > cost:
                        ans[ny][nx] = cost
                        q.append((ny, nx, cost))

            for dy8, dx8 in warp:
                ny8, nx8 = dy8 + sy, dx8 + sx
                if 0 <= ny8 < H and 0 <= nx8 < W:
                    if G[ny8][nx8] == "." and ans[ny8][nx8] > cost + 1:
                        ans[ny8][nx8] = cost + 1
                        q.append((ny8, nx8, cost + 1))

    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    gy, gx = map(lambda x: int(x) - 1, input().split())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()


### FIXED CODE ###


from collections import deque
def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else -1
    print(ans)


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

import copy

n = int(input())
la = [int(input()) for i in range(n)]

s_la = sorted(la, reverse=True)

for a in la:
	max_la = copy.copy(s_la)
	max_la.remove(a)
	print(max_la[0])

### FIXED CODE ###


n = int(input())
la = [int(input()) for i in range(n)]

s_la = sorted(la, reverse=True)

for a in la:
	if a == s_la[0]:
		print(s_la[1])
	else:
		print(s_la[0])
### BUGGY CODE ###

from collections import Counter
n=int(input())
A=list(map(int,input().split()))
C=Counter(A)
for i in range(n):
    D=C.copy()
    D[A[i]]-=1
    r=0
    for v in D.values():
        if v>=2:
            r+=v*(v-1)//2
    print(r)

### FIXED CODE ###

from collections import Counter
import sys
n=int(input())
s=sys.stdin.readlines()
A=list(map(int,s[0].split()))
C=Counter(A)
R=0
for v in C.values():
    R+=v*(v-1)//2
for i in range(n):
    r=C[A[i]]
    X=R
    if r>=2:
        x=((r-1)*(r-2)//2-(r)*(r-1)//2)
        X+=x
    print(X)
### BUGGY CODE ###

S = input()
n = len(S)

count = 0
while True:
    S = S.replace("BW", "#")
    tmp_count = S.count("#")
    count += tmp_count
    S = S.replace("#", "WB")

    if tmp_count == 0:
        break

print(count)

### FIXED CODE ###

S = input()

count = 0
out = 0
for cur_i, s in enumerate(S):
    if s == "W":
        out += (cur_i - count)
        count += 1

print(out)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

K=min(K,3000)
ab=[0]*K
abc=[]
i=0

for x in range(X):
  for y in range(Y):
    if i<=K-1:
    	ab[i]=A[x]+B[y]
    else:
      	ab.append(A[x]+B[y])
    i +=1

ab.sort(reverse=True)


abc=[ab[k]+C[z] for k in range(K) for z in range(Z)]



abc.sort(reverse=True)

for k in range(K):
	print(abc[k])


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

K=min(K,3000)

AB=[a+b for a in A for b in B]
AB.sort(reverse=True)

ABC=[ab+c for ab in AB[:K] for c in C[:K]]
ABC.sort(reverse=True)

for k in range(K):
	print(ABC[k])
### BUGGY CODE ###

from operator import itemgetter, attrgetter
#input
n = int(input())
H = [list(map(int, input().split())) for _ in range(n)]
C = sorted(H, key = itemgetter(0, 1), reverse = True)
A = sorted(H, key = itemgetter(1, 0), reverse = True)

ans_c = 0
ans_a = 0
turn = 0

while H != []:
    C = sorted(H, key = itemgetter(0, 1), reverse = True)
    A = sorted(H, key = itemgetter(1, 0), reverse = True)
    if turn % 2 == 0: #chokudai 
        if C[0][0] - A[0][0] >= A[0][1] - C[0][1]:
            chokudai = C.pop(0)
        else:
            chokudai = A.pop(0)
        ans_c += chokudai[0]
        H.remove(chokudai)
    else: #aoki
        if A[0][1] - C[0][1] >= C[0][0] - A[0][0]:
            aoki = A.pop(0)
        else:
            aoki = C.pop(0)
        ans_a += aoki[1]
        H.remove(aoki)
    turn += 1

print(ans_c - ans_a)


### FIXED CODE ###

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

H = sorted(H, reverse = True)
sum_c = 0
sum_a = 0

for i in range(n):
    if i % 2 == 0:
        sum_c += H[i][1]
    else:
        sum_a += H[i][2]

ans = sum_c - sum_a
print(ans)
### BUGGY CODE ###

A,B,Q=map(int,input().split())
s=[]
t=[]
for i in range(A):
  s.append(int(input()))
for i in range(B):
  t.append(int(input()))
for i in range(Q):
  x=int(input())
  s1=s[:]
  s1.append(x)
  s1.sort()
  j=s1.index(x)
  if j==0:
    kouhoA=[s[j]]
  elif j==A:
    kouhoA=[s[j-1]]
  else:
    kouhoA=[s[j],s[j-1]]
  t1=t[:]
  t1.append(x)
  t1.sort()
  k=t1.index(x)
  if k==0:
    kouhoB=[t[k]]
  elif k==B:
    kouhoB=[t[k-1]]
  else:
    kouhoB=[t[k],t[k-1]]
  if len(kouhoA)==1:
    
    if len(kouhoB)==1:
      a=abs(kouhoA[0]-kouhoB[0])
      ans=min([abs(x-kouhoA[0])+a,abs(x-kouhoB[0])+a])
    else:
      a=abs(kouhoA[0]-kouhoB[0])
      b=abs(kouhoA[0]-kouhoB[1])
      ans=min([abs(x-kouhoA[0])+a,abs(x-kouhoB[0])+a,abs(x-kouhoA[0])+b,abs(x-kouhoB[1])+b])
  else:
    if len(kouhoB)==1:
      a=abs(kouhoA[0]-kouhoB[0])
      c=abs(kouhoB[0]-kouhoA[1])
      ans=min([abs(x-kouhoA[0])+a,abs(x-kouhoB[0])+a,abs(x-kouhoA[1])+c,abs(x-kouhoB[0])+c])
    else:
      a=abs(kouhoA[0]-kouhoB[0])
      d=abs(kouhoA[1]-kouhoB[1])
      ans=min([abs(x-kouhoA[0])+a,abs(x-kouhoB[0])+a,abs(x-kouhoA[1])+d,abs(x-kouhoB[1])+d,abs(x-kouhoA[1])+abs(kouhoA[1]-kouhoB[0]),abs(x-kouhoB[0])+abs(kouhoB[0]-kouhoA[1]),abs(x-kouhoA[0])+abs(kouhoA[0]-kouhoB[1]),abs(x-kouhoB[1])+abs(kouhoB[1]-kouhoA[0])])
  print(ans)


### FIXED CODE ###

import bisect
A,B,Q=map(int,input().split())
s=[]
t=[]
for i in range(A):
  s.append(int(input()))
for i in range(B):
  t.append(int(input()))
for i in range(Q):
  x=int(input())
  j=bisect.bisect_left(s,x)
  if j==0:
    kouhoA=[s[j]]
  elif j==A:
    kouhoA=[s[j-1]]
  else:
    kouhoA=[s[j],s[j-1]]
  k=bisect.bisect_left(t,x)
  if k==0:
    kouhoB=[t[k]]
  elif k==B:
    kouhoB=[t[k-1]]
  else:
    kouhoB=[t[k],t[k-1]]
  if len(kouhoA)==1:
    
    if len(kouhoB)==1:
      a=abs(kouhoA[0]-kouhoB[0])
      ans=min([abs(x-kouhoA[0])+a,abs(x-kouhoB[0])+a])
    else:
      u=abs(x-kouhoA[0])
      a=abs(kouhoA[0]-kouhoB[0])
      b=abs(kouhoA[0]-kouhoB[1])
      ans=min([u+a,abs(x-kouhoB[0])+a,u+b,abs(x-kouhoB[1])+b])
  else:
    if len(kouhoB)==1:
      a=abs(kouhoA[0]-kouhoB[0])
      c=abs(kouhoB[0]-kouhoA[1])
      v=abs(x-kouhoB[0])
      ans=min([abs(x-kouhoA[0])+a,v+a,abs(x-kouhoA[1])+c,v+c])
    else:
      u=abs(x-kouhoA[0])
      a=abs(kouhoA[0]-kouhoB[0])
      b=abs(kouhoA[0]-kouhoB[1])
      c=abs(kouhoB[0]-kouhoA[1])
      d=abs(kouhoA[1]-kouhoB[1])
      v=abs(x-kouhoB[0])
      w=abs(x-kouhoA[1])
      y=abs(x-kouhoB[1])
      ans=min([u+a,v+a,w+d,y+d,w+c,v+c,u+b,y+b])
  print(ans)
### BUGGY CODE ###

memo = {}

def gcd(a, b):
    global memo

    ia = max(a, b)
    ib = min(a, b)

    if (ia, ib) in memo:
        return memo[(ia, ib)]

    while b != 0:
        t = b
        b = a % b
        a = t
    
    memo[(ia, ib)] = a    
    return a

def tgcd(a, b, c):
    return  gcd(a, gcd(b, c))

K = int(input())
total = 0

# 3 scenarios
# X-X-X
# X-X-Y
# X-Y-Z

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            total += tgcd(a, b, c)

        
print(total)
#total += sum(range(1, 201))
#print(total + sum(range(1,201)))
#print("diff", 10813692-total)

### FIXED CODE ###

def gcd(a, b):
    while b != 0:
        t = b
        b = a % b
        a = t
    return a

def tgcd(a, b, c):
    return  gcd(a, gcd(b, c))

K = int(input())
total = 0

# 3 scenarios
# X-X-X
# X-X-Y
# X-Y-Z

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            total += tgcd(a, b, c)

        
print(total)
#total += sum(range(1, 201))
#print(total + sum(range(1,201)))
#print("diff", 10813692-total)
### BUGGY CODE ###

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

k = [0]*N

"""
def kitaiti(n):
    sum = 0
    for i in range(1,n+1):
        sum += i
    return sum / n
""" 
def kitaiti(n):
    return 0.5*n + 0.5

ans = 0
index = 0
for i in range(N-K+1):
    if ans < sum(p[i:i+K]):
        ans = sum(p[i:i+K])
        index = i

ans = 0
for i in range(K):
    ans += kitaiti(p[index + i])
print(ans)


### FIXED CODE ###

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

def kitaiti(n):
    return 0.5*n + 0.5

ans = 0

s=[0]*(N+1)
for i in range(N):
    s[i+1] = s[i] + p[i]

for i in range(N-K+1):
    val = s[K+i] - s[i]
    if ans<val:
        ans = val

print(kitaiti(ans)+0.5*(K-1))
### BUGGY CODE ###

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

for i in range(q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

for i in range(q):
    A = [C[i] if a == B[i] else a for a in A]
    print(sum(A))


### FIXED CODE ###

from collections import Counter

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

for i in range(q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

sum_a = sum(A)
c = Counter(A)
for i in range(q):
    b_num = c[B[i]]
    diff = (C[i] - B[i]) * b_num
    c[C[i]] = c[C[i]] + c[B[i]]
    c[B[i]] = 0
    sum_a = sum_a + diff
    print(sum_a)
### BUGGY CODE ###

from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False
prime2017 = [0] * 100000
prime2017[0] = 0
prime2017[1] = 0
prime2017[2] = 0
for x in range(3,len(prime)):
    if prime[x] and prime[int((x+1)/2)]:
        prime2017[x] = 1
q=int(input())
lr_ary = []
for _ in range(q):
    l,r=list(map(int, input().split()))
    ret=sum(prime2017[l:r+1:2])
    print(ret)

### FIXED CODE ###

from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False
prime2017 = [0] * 100000
prime2017[0] = 0
prime2017[1] = 0
prime2017[2] = 0
ruiseki=0
for x in range(3,len(prime)):
    if prime[x] and prime[int((x+1)/2)]:
        ruiseki+=1
    prime2017[x] = ruiseki
q=int(input())
lr_ary = []
for _ in range(q):
    l,r=list(map(int, input().split()))
    print(prime2017[r]-prime2017[l-1])
### BUGGY CODE ###

num = int(input())
each_num = list(map(int, input().split(" ")))

ans = []

i = 1
for k in range(1, num+1):
    ans.append(each_num.index(k) + 1)
for i in range(num):
    print(ans[i], end = " ")



### FIXED CODE ###

n = int(input())
l = list(map(int, input().split(" ")))
a =[0]*n

for i in range(n):
    #print(i)
    a[l[i]-1] = i + 1 #each_numのi番目のインデックスに代入, -1 はi 番目が1,2,3 ...

for i in range(n):
    print(a[i], end = " ")
### BUGGY CODE ###

n, m, l = map(int, input().split())
abc_lst = [list(map(int, input().split())) for _ in range(m)]
q = int(input())
q_lst = [list(map(int, input().split())) for _ in range(q)]

edge_lst = []
for abc in abc_lst:
    a,b,c = abc
    if c <= l:
        edge_lst.append((a,b,c))
        edge_lst.append((b,a,c))
        
d_matrix = [[(-1, 10**10)] * (n+1) for _ in range(n+1)]
for i in range(n):
    d = [(-1, 10**10)] * (n+1)
    d[i+1] = (l, 0)
    while True:
        update = False
        for abc in edge_lst:
            a, b, c = abc
            if d[a][1] != 10**10:
                if d[a][0] < c:
                    cnt = d[a][1] + 1
                    f = l - c
                else:
                    cnt = d[a][1]
                    f = d[a][0] - c
                if d[b][1] == cnt:
                    if d[b][0] <= f:
                        d[b] = (f, cnt)
                        update = True
                if d[b][1] > cnt:
                    d[b] = (f, cnt)
                    update = True
        if not update:
            break
        d_matrix[i+1] = d

for q in q_lst:
    s, t = q
    print(d_matrix[s][t][1]) if d_matrix[s][t][1] != 10**10 else print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M, L = map(int, input().split())
INF = float('inf')
VD = [[INF] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    VD[a][b] = c
    VD[b][a] = c
for i in range(N):
    VD[i][i] = 0
 
for k in range(N):
    for i in range(N):
        for j in range(N):
            if VD[i][j] > VD[i][k] + VD[k][j]:
                VD[i][j] = VD[i][k] + VD[k][j]
 
WD = [[INF] * N for _ in range(N)]
for i in range(N):
    WD[i][i] = 0
    for j in range(i+1,N):
        d = VD[i][j]
        if d <= L:
            WD[i][j] = 1
            WD[j][i] = 1
 
for k in range(N):
    for i in range(N):
        for j in range(N):
            if WD[i][j] > WD[i][k] + WD[k][j]:
                WD[i][j] = WD[i][k] + WD[k][j]
 
Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    print(WD[s-1][t-1]-1 if WD[s-1][t-1] < INF else -1)
### BUGGY CODE ###

from collections import deque

def main():
    h, w = map(int, input().split())
    G = [list(input()) for i in range(h)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w)] for i in range(h)]
    que = deque()
    
    for i in range(h):
        for j in range(w):
            if G[i][j] == "#":
                dist[i][j] = 0
                que.append((i, j))
    
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if (ny < 0) or (h <= ny) or (nx < 0) or (w <= nx):
                continue
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    
    ans = 0
    for i in dist:
        for j in i:
            ans = max(ans, j)
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def main():
    h, w = map(int, input().split())
    G = [["#"]*(w+2)]+[["#"]+list(input())+["#"] for i in range(h)]+[["#"]*(w+2)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w+2)] for i in range(h+2)]
    que = deque()
    
    for i in range(1, h+1):
        for j in range(1, w+1):
            if G[i][j] == "#":
                dist[i][j] = 0
                que.append((i, j))
    
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    
    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            ans = max(ans, dist[i][j])
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

MOD = 10**9+7
s = input()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

dp=[[0]*13]
for i in range(len(s)):
    dp.append([0]*13)

dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    dp[i+1][k] %= MOD

#print(dp)
print(dp[len(s)][5]%MOD)


### FIXED CODE ###

MOD = 10**9+7
s = input()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

ind2 = list(range(13))
dp={}
#dp.setdefault(0, dict(zip(ind2,[0]*13)))
for i in range(len(s)+1):
    #dp.append(dict(zip(ind2,[0]*13)))
    dp.setdefault(i, dict(zip(ind2,[0]*13)))


#print(dp)
dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    dp[i+1][k] %= MOD

#print(dp)
print(dp[len(s)][5]%MOD)
### BUGGY CODE ###

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

while K > 0:
  if (X - K * D)**2 <= X**2:
    X -= D
  else:
    X += D
  
  K -= 1

print(abs(X))

### FIXED CODE ###

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

X = abs(X)
if X >= K * D:
  ans = X - K * D

else:
  n, d = divmod(X, D)
  ans = d
  if (K - n) % 2:
    ans = D - d


print(ans)