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

n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
ans=1
i=0
while(1):
    if a[i]==2:
        print(ans)
        exit()
    elif a[i]==1 or a[i]-1==i:
        print(-1)
        exit()
    else:
        i=a[i]-1
        ans+=1

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input())-1)
ans=1
i=0
b=[]
while(1):
    if ans==n:
        print(-1)
        exit()
    elif a[i]==1:
        print(ans)
        exit()
    else:
        ans+=1
        i=a[i]
### BUGGY CODE ###

import math
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
primes = primes(10**5)
anss = []
for p in primes:
    if (p+1)//2 in primes:
        anss.append(p)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in anss:
        cnt += 1
    dp[i] = cnt

    
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(dp[r]-dp[l-2])

### FIXED CODE ###

import math
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
primes = primes(10**5)
anss = []
for p in primes:
    if (p+1)//2 in primes:
        anss.append(p)
dp = [0]*(10**5+1)
cnt = 0
for i in range(1, 10**5+1, 2):
    if i in anss:
        cnt += 1
    dp[i] = cnt

    
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(dp[r]-dp[l-2])
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import count, combinations

for case in count(1):
    W = int(stdin.readline().strip())
    if not W:
        break

    N = int(stdin.readline().strip())
    data = []
    for _ in xrange(N):
        data.append([int(s) for s in stdin.readline().strip().split(',')])
    data.sort(key=lambda (v,w): w)

    value, weight = 0, W
    for i in xrange(1, N+1):
        for cmb in combinations(data, i):
            tv, tw = 0, 0
            for v, w in cmb:
                tv += v
                tw += w
            if W < tw:
                break
            if W >= tw and (tv > value) or (tv == value and tw < weight):
                value, weight = tv, tw

    print('Case {}:\n{}\n{}'.format(case, value, weight))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from itertools import count

def douteki(limit, data):
    V = [[0 for w in xrange(limit+1)] for i in xrange(len(data)+1)]
    W = [[0 for w in xrange(limit+1)] for i in xrange(len(data)+1)]
    for i in xrange(len(data)+1):
        for w in xrange(limit+1):
            diff = w - data[i-1][1]
            if i - 1 >= 0 and diff >= 0:
                v1 = V[i-1][diff] + data[i-1][0]
                w1 = W[i-1][diff] + data[i-1][1]
            else:
                v1 = 0
                w1 = 0
            v2 = V[i-1][w]
            w2 = W[i-1][w]

            V[i][w], W[i][w] = (v1, w1) if v1 >= v2 else (v2, w2)
    return V[-1][-1], W[-1][-1]

for case in count(1):
    W = int(stdin.readline())
    if not W:
        break

    N = int(stdin.readline())
    data = []
    for _ in xrange(N):
        data.append([int(s) for s in stdin.readline().split(',')])

    value, weight = douteki(W, data)
    print('Case {}:\n{}\n{}'.format(case, value, weight))
### BUGGY CODE ###

n=int(input())
li=list(map(int,input().split()))
for i in range(n):
  print(li.count(i+1))
  

### FIXED CODE ###

n=int(input())
li=list(map(int,input().split()))
check=[0]*n
for i in li:
  check[i-1]+=1
for i in range(n):
  print(check[i])
### BUGGY CODE ###

from collections import defaultdict
d=defaultdict(int)
N,M=map(int,input().split())
ans=0
t=M
for i in range(N):
	a,b=map(int,input().split())
	d[a]+=b
while t>0:
	for i in range(d[min(d)]):
		ans+=min(d)
		t-=1
		if t==0:break
	d.pop(min(d))
print(ans)

### FIXED CODE ###

N,m=map(int,input().split())
L=sorted([list(map(int,input().split())) for _ in range(N)])
ans=0
for i in range(N):
	ans+=L[i][0]*min(m,L[i][1])
	m-=min(m,L[i][1])
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import numpy as np


s = input()
t = input()
l = len(s)

idx_dict = defaultdict(list)

#各文字の index を取得
for i, v in enumerate(s):
    idx_dict[v].append(i)

#リストを ndarray に変換
for key, value in idx_dict.items():
    idx_dict[key] = np.array(value)

l = len(s)
rnd = 0
idx = 0
ans = 0
p_v = ''
# index のリストを取り出し、現在の idx と比べる
# idx より大きい値がない場合は一周ふやす
for v in t:
    # idx_dict の key に　v が存在しなかったら -1
    if v not in idx_dict:
        ans = -1
        break
    # 同じ文字が続いたら idx を 1 増やす
    if v == p_v:
        idx += 1
    arr = idx_dict[v]
    ar = arr[arr >= idx]

    if ar.size > 0:
        idx = ar[0]
    else:
        idx = arr[0]
        rnd += 1
    p_v = v

if not ans:
        ans = ((rnd * l) + idx) + 1
        
print(ans)

### FIXED CODE ###

from collections import defaultdict
# import numpy as np
import bisect #bisect.bisect_left 値の挿入位置を返す関数


s = input()
t = input()
l = len(s)

idx_dict = defaultdict(list)

#各文字の index を取得
for i, v in enumerate(s):
    idx_dict[v].append(i)

#リストを ndarray に変換
#for key, value in idx_dict.items():
#    idx_dict[key] = np.array(value)

l = len(s)
rnd = 0
idx = 0
ans = 0
p_v = ''
# index のリストを取り出し、現在の idx と比べる
# idx より大きい値がない場合は一周ふやす
for v in t:
    # idx_dict の key に　v が存在しなかったら -1
    if v not in idx_dict:
        ans = -1
        break
    # 同じ文字が続いたら idx を 1 増やす
    if v == p_v:
        idx += 1
    arr = idx_dict[v]
    i = bisect.bisect_left(arr, idx)
    try:
        idx = arr[i]
    except IndexError:
        idx = arr[0]
        rnd += 1
    p_v = v

if not ans:
        ans = ((rnd * l) + idx) + 1
        
print(ans)
### BUGGY CODE ###

from bisect import *
from sys import stdin
readline = stdin.readline
N, Q = map(int, readline().split())
c = 1
B = [1]
ans = []
while c < 10**9:
    B.append(c+1)
    c = c*N + 1
for q in range(Q):
    v, w = map(int, readline().split())
    lv = bisect(B, v)
    lw = bisect(B, w)
    if lv < lw:
        w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
    while v != w:
        v = (v - 2 + N) // N
        w = (w - 2 + N) // N
    ans.append(str(v))
print("\n".join(ans))


### FIXED CODE ###

from bisect import *
from sys import stdin, stdout
readline = stdin.readline
N, Q = map(int, readline().split())
ans = []
if N == 1:
    for q in range(Q):
        v, w = map(int, readline().split())
        ans.append(str(v))
else:
    c = 1
    B = [1]
    while c < 10**9:
        B.append(c+1)
        c = c*N + 1
    for q in range(Q):
        v, w = map(int, readline().split())
        lv = bisect(B, v)
        lw = bisect(B, w)
        if lv < lw:
            w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
        while v != w:
            v = (v + (N - 2)) // N
            w = (w + (N - 2)) // N
        ans.append(str(v))
stdout.write("\n".join(ans))
stdout.write("\n")
### BUGGY CODE ###

h,w=map(int,input().split())
grid=[list(input()) for i in range(h)]

left=[[0]*w for _ in range(h)]
for i in range(h):
  cnt=0
  for j in range(w):
    if grid[i][j]=='.':
      cnt+=1
      left[i][j]=cnt
    else:
      cnt=0
      left[i][j]=cnt
      
right=[[0]*w for _ in range(h)]
for i in range(h):
  cnt=0
  for j in range(w):
    if grid[i][w-j-1]=='.':
      cnt+=1
      right[i][j]=cnt
    else:
      cnt=0
      right[i][j]=cnt

up=[[0]*w for i in range(h)]
for i in range(w):
  cnt=0
  for j in range(h):
    if grid[j][i]=='.':
        cnt+=1
        up[j][i]=cnt
    else:
        cnt=0
        up[j][i]=cnt

down=[[0]*w for i in range(h)]
for i in range(w):
  cnt=0
  for j in range(h):
    if grid[h-j-1][i]=='.':
        cnt+=1
        down[j][i]=cnt
    else:
        cnt=0
        down[j][i]=cnt

ans=0
for i in range(h):
  for j in range(w):
    if grid[i][j]=='.':
      tmp=left[i][j]+right[i][w-j-1]+up[i][j]+down[h-i-1][j]-3
      if tmp>ans:
        ans=tmp
    else:
      continue
print(ans)
    

### FIXED CODE ###

h,w=map(int,input().split())
grid=[list(input()) for i in range(h)]

left=[[0]*w for _ in range(h)]
for i in range(h):
  cnt=0
  for j in range(w):
    if grid[i][j]=='.':
      cnt+=1
      left[i][j]=cnt
    else:
      cnt=0
      left[i][j]=cnt
      
right=[[0]*w for _ in range(h)]
for i in range(h):
  cnt=0
  for j in range(w):
    if grid[i][w-j-1]=='.':
      cnt+=1
      right[i][j]=cnt
    else:
      cnt=0
      right[i][j]=cnt

up=[[0]*w for i in range(h)]
for i in range(w):
  cnt=0
  for j in range(h):
    if grid[j][i]=='.':
        cnt+=1
        up[j][i]=cnt
    else:
        cnt=0
        up[j][i]=cnt

down=[[0]*w for i in range(h)]
for i in range(w):
  cnt=0
  for j in range(h):
    if grid[h-j-1][i]=='.':
        cnt+=1
        down[j][i]=cnt
    else:
        cnt=0
        down[j][i]=cnt

ans=0
for i in range(h):
  for j in range(w):
    if grid[i][j]=='.':
      tmp=left[i][j]+right[i][w-j-1]+up[i][j]+down[h-i-1][j]-3
      if tmp>ans:
        ans=tmp
    else:
      continue
print(ans)
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[k]*n 
for i in range(q):
    t=int(input())
    for i in range((n)):
        if i!=t-1:
            a[i]-=1 
for i in a:
    if i>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[0]*n 
for i in range(q):
    t=int(input())
    a[t-1]+=1
#print(a)
for i in a:
    if k-(q-i)>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for _ in range(q):
  l,r=map(int,input().split())
  print(s[l-1:r].count('AC'))

### FIXED CODE ###

import sys
n,q=map(int,input().split())
s=input()
c=[0]*n
for i in range(2,n+1):
  if s[i-2:i]=='AC':
    c[i-1]=c[i-2]+1
  else:
    c[i-1]=c[i-2]
lr=sys.stdin.readlines()
for i in lr:
  l,r=map(int,i.split())
  print(c[r-1]-c[l-1])
### BUGGY CODE ###

import sys
import math

def isPrimeNumber(candidate):
    divisor = 2
    while divisor <= math.sqrt(candidate):
        if candidate % divisor == 0:
            return False
        else:
            divisor += 1
    return True

for line in sys.stdin:
    primeNumberCount = 0
    n = int(line.rstrip('\n'))
    candidate = 2
    while candidate <= n:
        if isPrimeNumber(candidate):
            primeNumberCount += 1
        candidate += 1
    print primeNumberCount

### FIXED CODE ###

import math
import sys

n = 999999
nums = [1] * (n+1)
nums[:2] = [0,0]
    
cnt = 0
while cnt <= math.sqrt(n):
    flg = nums[cnt]
    if flg == 1:
        k = 2
        while k*cnt <= n:
            nums[k*cnt] = 0
            k += 1
    cnt += 1


for line in sys.stdin:
    n = int(line)
    print sum(nums[:n+1])
### BUGGY CODE ###

n, s=map(int,input().split())
q=[list(map(int, input().split())) for i in range(n)]

import numpy as np
import itertools
import pprint

bit=[0,1]

cmp=list(itertools.product(bit, repeat=n))

cp=[0]*n
qt=[0]*n
cnt=[0]*2**n

for i in range(n):
	cp[i]=100*(i+1)*q[i][0]+q[i][1]
	qt[i]=q[i][0]

for i in range(2**n):
	score=np.dot(np.array(cp),np.array(cmp[i]).T)
	cnt[i]=np.dot(np.array(qt),np.array(cmp).T)[i]
	if score<s:
		j=n-1
		while score<s and j>=0:
			if cmp[i][j]==0:
				for k in range(qt[j]):
					score+=(j+1)*100
					cnt[i]+=1
					if score>=s:
						break
			j-=1
                
print(min(cnt))

### FIXED CODE ###

n, s=map(int,input().split())
q=[list(map(int, input().split())) for i in range(n)]

import numpy as np
import itertools
import pprint

bit=[0,1]

cmp=list(itertools.product(bit, repeat=n))

cp=[0]*n
qt=[0]*n
cnt=[0]*2**n

for i in range(n):
	cp[i]=100*(i+1)*q[i][0]+q[i][1]
	qt[i]=q[i][0]

cmp_cnt=np.dot(np.array(qt),np.array(cmp).T)

for i in range(2**n):
	score=np.dot(np.array(cp),np.array(cmp[i]).T)
	cnt[i]=cmp_cnt[i]
	if score<s:
		j=n-1
		while score<s and j>=0:
			if cmp[i][j]==0:
				for k in range(qt[j]):
					score+=(j+1)*100
					cnt[i]+=1
					if score>=s:
						j=0
						break
			j-=1
                
print(min(cnt))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
l = []
r = []
for i in range(Q):
    li, ri = map(int, input().split())
    l += [li]
    r += [ri]

S_tf = [S[ind:ind+2] == "AC" for ind in range(N)]

for ind in range(Q):
    print(sum(S_tf[max(0, l[ind]-1) : min(r[ind]-1, N)]))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
l = []
r = []
for i in range(Q):
    li, ri = map(int, input().split())
    l += [li]
    r += [ri]

S_tf = [0]*(N+1)
for ind in range(N):
    S_tf[ind + 1] = S_tf[ind] + (1 if S[ind:ind+2] == "AC" else 0)
for ind in range(Q):
    print(S_tf[max(0, r[ind]-1)] - S_tf[min(l[ind]-1, N)])
### BUGGY CODE ###

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

for i in range(k):
    if a > 0:
        a -= 1
    elif b > 0:
        b -= 1
    else:
        pass

print(a, b)


### FIXED CODE ###

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

if a < k:
    k -= a
    a = 0
else:
    a -= k
    k = 0

b = max(0, b-k)
print(a, b)
### BUGGY CODE ###

from math import factorial
from collections import Counter

def combinations_count(n, r):
    if n <= 1:
        return 0
    else:   
        return factorial(n) // (factorial(n - r) * factorial(r))

N = int(input())
A = list(input().split())
counter = Counter(A)

for k in range(N):
    sum = 0
    for key,value in counter.items():
        if key == A[k]:
            value = value - 1
        sum = sum + combinations_count(value,2)
    print(sum)


### FIXED CODE ###

from math import factorial
from collections import Counter

def combinations_count(n, r):
    if n <= 1:
        return 0
    else:
        return (n * (n-1)) // 2 
        #return factorial(n) // (factorial(n - r) * factorial(r))

N = int(input())
A = list(input().split())
sum = 0
counter = Counter(A)
for key,value in counter.items():
    sum = sum + combinations_count(value,2)

for k in range(N):
    add = 0
    add = sum - combinations_count(counter[A[k]],2) + combinations_count(counter[A[k]]-1,2) 
    print(add)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
if n % 2 == 0:
    for i in range(n):
        if i % 2 == 0:
            ans.append(a[i])
        else:
            ans.insert(0, a[i])
else:
    for i in range(n):
        if i % 2 != 0:
            ans.append(a[i])
        else:
            ans.insert(0, a[i])
print(" ".join(map(str, ans)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ev = a[1::2]
od = a[::2]
if n % 2 == 0:
    ev = ev[::-1]
    ans = ev + od
else:
    od = od[::-1]
    ans = od + ev
print(" ".join(map(str, ans)))
### BUGGY CODE ###

import sys
from collections import deque
import copy

input = sys.stdin.readline

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for _ in range(h)]

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(2,2), (2,1), (2,0), (2,-1), (2,-2), (1,2), (1,1), (1,-1), (1,-2), (0,2), (0,-2), (-1,2), (-1,1),(-1,-1), (-1,-2), (-2,2), (-2,1), (-2,0),(-2,-1),(-2,-2)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
q2 = [(ch-1, cw-1)]
q3 = []
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))

    for i,j in q2:
        for ii,jj in d2:
            if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp+1
                    q.append((i+ii,j+jj))
                    q3.append((i+ii,j+jj))
    if not q:
        break
    tmp += 1
    q2 = copy.copy(q3)

print(v[dh-1][dw-1])


### FIXED CODE ###

import sys
from collections import deque
import copy

input = sys.stdin.readline

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for _ in range(h)]

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(2,2), (2,1), (2,0), (2,-1), (2,-2), (1,2), (1,1), (1,-1), (1,-2), (0,2), (0,-2), (-1,2), (-1,1),(-1,-1), (-1,-2), (-2,2), (-2,1), (-2,0),(-2,-1),(-2,-2)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
q2 = [(ch-1, cw-1)]
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))

    cnt = 0
    for k in range(len(q2)):
        i,j = q2[k][0], q2[k][1]
        for ii,jj in d2:
            if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp+1
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))
                    cnt += 1
    if not q:
        break
    tmp += 1
    q2 = q2[-cnt:]
print(v[dh-1][dw-1])
### BUGGY CODE ###

n = int(input())
j = 1
for i in range(1,n+1):
  k = i * j
  j = k
print(k%(10**9+7))

### FIXED CODE ###

import math
n = int(input())
k = math.factorial(n)
print(k%(10**9+7))
### BUGGY CODE ###

def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    n,x,m=map(int,input().split())
    l=[]
    ans=0
    cnt=0
    while (x not in l)and(cnt<=n):
      l.append(x)
      ans+=x
      cnt+=1
      x=(x**2)%m
    for i in range(len(l)):
      if x==l[i]:
        break
    lc=l[i:].copy()
    lc_cnt=(n-cnt)//len(lc)
    ans+=lc_cnt*sum(lc)+sum(lc[:(n-cnt)-lc_cnt*len(lc)])
    print(ans)

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    n,x,m=map(int,input().split())
    l=[]
    ans=0
    cnt=0
    while (x not in l)and(cnt<=n):
      l.append(x)
      ans+=x
      cnt+=1
      x=(x**2)%m
    for i in range(len(l)):
      if x==l[i]:
        break
    lc=l[i:].copy()
    lc_cnt=(n-cnt)//len(lc)
    ans+=lc_cnt*sum(lc)+sum(lc[:(n-cnt)-lc_cnt*len(lc)])
    print(ans)

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

N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if i in ana:
        dp[i] = 0
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)



### FIXED CODE ###

N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if len(ana) >= 1 and i == ana[-1]:
        dp[i] = 0
        if len(ana) != 0:
            ana.pop(-1)
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)
### BUGGY CODE ###

n, a, b = map(int, input().split())
blue = 0
total = 0

for i in range(10**100):
  blue += a
  total += a
  if total == n:
    print(blue)
    exit(0)
  elif total > n:
    print(blue - (total - n))
    exit(0)
    
  total += b
  if total >= n:
    print(blue)
    exit(0)

### FIXED CODE ###

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

num = n//(a+b)
if (a+b)*num == n:
  print(a*num)
elif (a+b)*num + a <= n:
  print(a*(num+1))
else:
  print(a*num + n - (a+b)*num)
### BUGGY CODE ###

N,M = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]
for i in range(N):
    H[i] = H[i]%M
SumH = [0]
for i in range(N):
    SumH.append((SumH[i]+H[i])%M)
Ctr = []
Ans = {}
for i in range(N+1):
    if SumH[i] not in Ctr:
        Ctr.append(SumH[i])
        Ans[SumH[i]] = 1
    else:
        Ans[SumH[i]] += 1
ans = 0
for i in Ctr:
    ans += Ans[i]*(Ans[i]-1)//2
print(ans)


### FIXED CODE ###

def inpl(): return [int(i) for i in input().split()]

N,M = inpl()
H = {0: 1}
k = 0
ans = 0
for i in inpl():
    k += i
    t = k % M
    if t not in H:
        H[t] = 0
    H[t] += 1
    
for i in H.values():
   ans += i * (i - 1) // 2

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

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

x=0
y=[]
for i in range(n):
    y=y+[l[i]]
    if l[i]<=min(y):
        x+=1
print(x)
    






### FIXED CODE ###

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

x=0
y=[]
z=l[0]
for i in range(n):
    #y=y+[l[i]]
    z=min(z,l[i])
    if l[i]<=z:
        x+=1
print(x)
### BUGGY CODE ###

def main():
    import sys
    from collections import defaultdict
    from bisect import bisect_left
    input = sys.stdin.readline

    S = input().rstrip('\n')
    N = len(S)

    A = [ord(s)-97 for s in S]
    H = [0] * (N+1)
    h2i = defaultdict(list)
    for i in range(N):
        H[i+1] = H[i] ^ (1 << A[i])
        h2i[H[i+1]].append(i+1)

    dp = [N+1] * (N+1)
    dp[0] = 0
    for i in range(N):
        h = H[i]
        if h2i[h]:
            ii_list = h2i[h]
            ii = bisect_left(ii_list, i+1)
            if ii < len(ii_list):
                ii = ii_list[ii]
                if i:
                    dp[ii] = min(dp[ii], dp[i])
                else:
                    dp[ii] = 1
        for j in range(26):
            new_h = h ^ (1 << j)
            if h2i[new_h]:
                ii_list = h2i[new_h]
                ii = bisect_left(ii_list, i+1)
                if ii < len(ii_list):
                    ii = ii_list[ii]
                    dp[ii] = min(dp[ii], dp[i] + 1)
    print(dp[-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.readline

    S = input().rstrip('\n')
    N = len(S)

    A = [ord(s)-97 for s in S]
    H = [0] * (N+1)
    h2i = {}
    for i in range(N):
        H[i+1] = H[i] ^ (1 << A[i])
        if H[i+1] in h2i:
            h2i[H[i+1]].append(i+1)
        else:
            h2i[H[i+1]] = [i+1]

    dp = [N+1] * (N+1)
    dp[0] = 0
    pow2 = [2**i for i in range(26)]
    for i in range(N):
        h = H[i]
        if h in h2i:
            ii_list = h2i[h]
            ii = bisect_left(ii_list, i+1)
            if ii < len(ii_list):
                ii = ii_list[ii]
                if i:
                    dp[ii] = min(dp[ii], dp[i])
                else:
                    dp[ii] = 1
        for j in pow2:
            new_h = h ^ j
            if new_h in h2i:
                ii_list = h2i[new_h]
                ii = bisect_left(ii_list, i+1)
                if ii < len(ii_list):
                    ii = ii_list[ii]
                    dp[ii] = min(dp[ii], dp[i] + 1)
    print(dp[-1])


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

x,k,d = map(int, input().split())
line = [x]
for i in range(k):
  if x > 0:
    x -= d
  else:
    x += d
  line.append(x)
  if i != 0:
    if line[i-1] == line[i+1]:
      if (k - i + 1) % 2 == 0:
        x = line[i+1]
        break
      else:
        x = line[i]
        break
print(abs(x))

### FIXED CODE ###

x,k,d = map(int, input().split())
count = abs(x) // d
if count >= k:
  print(abs(x)-k*d)
else:
  if (k - count) % 2 == 0:
    print(abs(x)-count*d)
  else:
    print(abs(abs(x)-(count+1)*d))