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

import heapq


N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
x_list = []
time = 0
for q in range(Q):
  d = int(input())
  while time <= d:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
        heapq.heappush(x_list, x)
      else:
        x_set.remove(x)
      i += 1
  if x_set:
    while x_list and x_list[0] not in x_set:
      _ = heapq.heappop(x_list)
    print(x_list[0])
  else:
    print(-1)

### FIXED CODE ###

import sys
from heapq import heappop, heappush

input = sys.stdin.readline
N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

for i in range(Q):
  event_list.append([int(input()), 2, 0])

ans = []
event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      ans.append(x_list[0])
    else:
      ans.append(-1)

print(*ans, sep='\n')
### BUGGY CODE ###

import numpy as np
import sys
import math
read = sys.stdin.readline

X = int(input())


for a in range(1,10000):
    for b in range(0,10000):
        a4 = a ** 4
        b4 = b ** 4
        a3 = a ** 3
        b3 = b ** 3
        a2 = a ** 2
        b2 = b ** 2
        if ( (a-b)*( a4 + (a3*b) + (a2 * b2) + (b3 * a) + b4) ) == X:
            print(a,b)
            sys.exit()

        b = -1 * b
        b3 = -1 * b3
        if ( (a-b)*( a4 + (a3*b) + (a2 * b2) + (b3 * a) + b4) ) == X:
            print(a,b)
            flag = 1
            sys.exit()
        


### FIXED CODE ###

import numpy as np
import sys
import math
read = sys.stdin.readline

X = int(input())


for a in range(1,1000):
    for b in range(0,1000):
        a4 = a ** 4
        b4 = b ** 4
        a3 = a ** 3
        b3 = b ** 3
        a2 = a ** 2
        b2 = b ** 2
        if ( (a-b)*( a4 + (a3*b) + (a2 * b2) + (b3 * a) + b4) ) == X:
            print(a,b)
            sys.exit()

        b = -1 * b
        b3 = -1 * b3
        if ( (a-b)*( a4 + (a3*b) + (a2 * b2) + (b3 * a) + b4) ) == X:
            print(a,b)
            flag = 1
            sys.exit()
### BUGGY CODE ###

from itertools import permutations
INF = 10**8
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0
for i in range(m):
    a, b, c = list(map(int, input().split()))
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]-1][p[i+1]-1]
    ans = min(ans, ans_)
print(ans)


### FIXED CODE ###

from itertools import permutations

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = c
    dist[b][a] = c

from scipy.sparse import csgraph
dist = csgraph.floyd_warshall(dist)
# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(int(ans))
### BUGGY CODE ###

n = int(input())

def calc_luca(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return calc_luca(n - 1) + calc_luca(n - 2)

print(calc_luca(n))

### FIXED CODE ###

n = int(input())

ans = [0] * (n + 1)
ans[0] = 2
ans[1] = 1
for i in range(2, n + 1):
    ans[i] = ans[i - 1] + ans[i - 2]

print(ans[n])
### BUGGY CODE ###

class BIT():
	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def getsum(self, k):
		ret = 0
		while k:
			ret += self.bit[k]
			k -= k & -k
		return ret

	def p_sum(self, i, j):
		return self.getsum(j) - self.getsum(i - 1)

	def add(self, k, x):
		while k <= self.n:
			self.bit[k] += x
			k += k & -k

	def bisect(self, x):
		i, m = 0, 1 << (self.n.bit_length() - 1)
		while m:
			t = i + m
			if t < self.n and self.bit[t] < x:
				i = t
				x -= self.bit[i]
			m //= 2
		return i + 1

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter as get
n,q=map(int,input().split())
event=[]
Xs=[]
for _ in range(n):
	s,t,x=map(int,input().split())
	event.append((-2,s-x,x))
	event.append((-1,t-x,x))
	Xs.append(x)
Xs.sort()
for _ in range(q):
	d=int(input())
	event.append((0,d,None))
event.sort(key=get(1))
x_to_i={x:i for i,x in enumerate(Xs)}
bit=BIT(n+1)
Xs.append(-1)
bit.add(n,1)
ans=[]
for flg,time,x in event:
	if flg==-2:
		bit.add(x_to_i[x],1)
	elif flg==-1:
		bit.add(x_to_i[x],-1)
	else:
		i=bit.bisect(1)
		ans.append(Xs[i])
print("\n".join(map(str,ans)))




### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter as get
from heapq import *


def main():
	n, q = map(int, input().split())
	event = []
	Xs = []
	for _ in range(n):
		s, t, x = map(int, input().split())
		event.append((-2, s - x, x))
		event.append((-1, t - x, x))
		Xs.append(x)
	for _ in range(q):
		d = int(input())
		event.append((0, d, None))
	event.sort(key=get(1))
	active = {x: 0 for x in Xs}
	candidate = []
	ans = []
	for flg, time, x in event:
		if flg == -2:
			active[x] = 1
			heappush(candidate, x)
		elif flg == -1:
			active[x] = 0
		else:
			res = -1
			while candidate:
				c = heappop(candidate)
				if active[c]:
					heappush(candidate, c)
					res = c
					break
			ans.append(res)
	print("\n".join(map(str, ans)))


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

N=int(input())
S=input()

R=[]
G=[]
B=[]
for i in range(N):
    if S[i]=="R":
        R.append(i)
    elif S[i]=="G":
        G.append(i)
    else:
        B.append(i)

cnt0=len(B)
cnt=0
for i in R:
    for j in G:
        cnt+=cnt0
        koho=set()
        if (j+i)%2==0:
            koho.add((j+i)//2)
        if 0<=2*i-j<N:
            koho.add(2*i-j)
        if 0<=2*j-i<N:
            koho.add(2*j-i)
        for k in koho:
            if k in B:
                cnt-=1
            
                
print(cnt)

### FIXED CODE ###

N=int(input())
S=input()

R=[]
G=[]
B=[]
for i in range(N):
    if S[i]=="R":
        R.append(i)
    elif S[i]=="G":
        G.append(i)
    else:
        B.append(i)

cnt=len(R)*len(G)*len(B)
for i in R:
    for j in G:
        koho=set()
        if (j+i)%2==0:
            koho.add((j+i)//2)
        if 0<=2*i-j<N:
            koho.add(2*i-j)
        if 0<=2*j-i<N:
            koho.add(2*j-i)
        for k in koho:
            if k in B:
                cnt-=1
            
                
print(cnt)
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            ans += math.gcd(a, math.gcd(b, c))
print(ans)


### FIXED CODE ###

import math
k = int(input())
dp = [[1 for _ in range(k + 1)] for _ in range(k + 1)]
for i in range(1, k + 1):
    for j in range(1, k + 1):
        dp[i][j] = math.gcd(i, j)
ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            ans += dp[a][dp[b][c]]
print(ans)
### BUGGY CODE ###

import copy
N,W = map(int,input().split())
w = []
v = []
for i in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

d = [0]*(W+1)
dp = [copy.deepcopy(d) for j in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])

print(dp[N][W])

### FIXED CODE ###

n,W = map(int,input().split())
w = []
v = []
for i in range(n):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)

dp = [[0]*(W+1) for j in range(n+1)]

for i in range(n-1,-1,-1):
    for j in range(W+1):
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
print(dp[0][W])
### BUGGY CODE ###

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

### FIXED CODE ###

import collections
N = int(input())
A = [i for i in input().split()]
 
ans = collections.deque()
for i in range(N):
    if (i+1)%2==N%2:
        ans.appendleft(A[i])
    else:
        ans.append(A[i])
print(*ans)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[0] * (len(A) - i) for i in range(len(A))]

    for i in range(1, len(A)):
        s = sum(A[:i])
        for j in range(len(A) - i):
            s += A[i + j]
            dp[i][j] = min(dp[k][j] + dp[i - k - 1][j + k + 1] for k in range(i)) + s
            s -= A[j]
    print(dp[-1][0])


main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[0] * (len(A) - i) for i in range(len(A))]

    for i in range(1, len(A)):
        s = sum(A[:i])
        for j in range(len(A) - i):
            s += A[i + j]
            dp[i][j] = min(dp[k][j] + dp[i - k - 1][j + k + 1] for k in range(i)) + s
            s -= A[j]
    print(dp[-1][0])


main()
### BUGGY CODE ###

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

a = list(map(int,input().split()))
res = sum(a)
dis = 0
for v in range(M):
    a.sort(reverse=True)
    dis += a[0] - a[0]//2
    a[0] //=2
print(res-dis)


### FIXED CODE ###

import heapq

N,M = map(int,input().split())
a = list(map(int,input().split()))
a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)
for _ in range(M):
    heapq.heappush(a,((heapq.heappop(a)*(-1))//2)*(-1))
print(abs(sum(a)))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

for i in range(1, N+1):
  for j in range(N):
    if i == A[j]:
      print(j+1, end="")
      print(" ",end="")
      break
      
print()    

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
a = []

for i in range(0, N):
  a.append([i+1, A[i]])

a.sort(key = lambda x: x[1])  

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

x=input().split()
h=int(x[0])
n=int(x[1])
a=[]
b=[]
for k in range(n):
  x=input().split()
  a.append(int(x[0]))
  b.append(int(x[1]))  
m=max(a)  
dp=[10**8]*(h+m)
dp[0]=0
for k in range(h+m):
  temp=[]
  for i in range(n):
    if k-a[i]<0:
      continue
    if dp[k-a[i]]==10**8:
      continue
    temp.append(dp[k-a[i]]+b[i])
  if len(temp)>0:
    dp[k]=min(temp)
print(min(dp[h:h+m]))
      
      
  


### FIXED CODE ###

x=input().split()
h=int(x[0])
n=int(x[1])
import numpy as np
a=np.full(n,0,int)
b=np.full(n,0,int)
for k in range(n):
  x=input().split()
  a[k]=int(x[0])
  b[k]=int(x[1])
m=max(a)  
inf=10**8
dp=np.full(h+m,inf,int)
dp[0]=0
for k in range(1,h+m):
  dp[k]=(dp[k-a]+b).min()
print(dp[h:h+m].min())
### BUGGY CODE ###

import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = 61

    one_cnt = [0] * B
    for b in range(B):
        for i in range(N):
            one_cnt[b] += (A[i] >> b) & 1

    ans = 0
    for b in range(B):
        ans += 2 ** b * one_cnt[b] * (N - one_cnt[b])
        ans %= P
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

import numpy as np

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = np.array(A)

    ans = 0
    for b in range(60 + 1):
        cnt_1 = int(np.sum((A >> b) & 1))
        ans += 2 ** b * cnt_1 * (N - cnt_1)
        ans %= P
    print(ans)


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

h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])

dp = [[[False]*(80*(h+w)) for i in range(w)] for k in range(h)]
dp[0][0][mat[0][0]] = True
for y in range(h):
  for x in range(w):
    if x > 0:
      for k in range(80*(h+w)):
        if dp[y][x-1][k]:
          dp[y][x][k+mat[y][x]] = True
          dp[y][x][abs(k-mat[y][x])] = True
    if y > 0:
      for k in range(80*(h+w)):
        if dp[y-1][x][k]:
          dp[y][x][k+mat[y][x]] = True
          dp[y][x][abs(k-mat[y][x])] = True
for k in range(80*(h+w)):
  if dp[h-1][w-1][k]:
    print(k)
    exit()


### FIXED CODE ###

h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])
m = max(map(max, mat))
dp = [[0b0 for i in range(w)] for k in range(h)]
dp[0][0] |= 0b1 << mat[0][0]
for y in range(h):
  for x in range(w):
        if x > 0:
          dp[y][x] |= dp[y][x-1] << mat[y][x]
          dp[y][x] |= dp[y][x-1] >> mat[y][x]
          anded = dp[y][x-1] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        if y > 0:
          dp[y][x] |= dp[y-1][x] << mat[y][x]
          dp[y][x] |= dp[y-1][x] >> mat[y][x]
          anded = dp[y-1][x] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        #print(bin(dp[y][x]))

keta = 0
while dp[h-1][w-1] % 2 == 0:
  keta += 1
  dp[h-1][w-1] //= 2
print(keta)
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
ans=0
while a>0 and d>0 :
    ans+=1
    d=d-1
    a-=1
while d>0 and b>0:
    d=d-1
    b-=1
while d>0 and c>0:     
  
    ans-=1
    d=d-1
print(ans)     
  


### FIXED CODE ###

a,b,c,d=map(int,input().split())
ans=0
if d-a>=0:
  d=d-a
  ans+=a
  if d-b>0:
      d-=b
      if d-c==0:
          ans-=c
      else:
          ans=ans-d
else:
    ans+=d
print(ans)
### BUGGY CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

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()))

bimi = []
for a in range(X):
        for b in range(Y):
                bimi.append(A[a] + B[b])

bimi.sort(reverse=True)
ans = []
for x in range(min(K, len(bimi))):
        for c in range(Z):
                ans.append(bimi[x] + C[c])

ans.sort(reverse=True)

for i in range(K):
        print(ans[i])



### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

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

bimi = []

for a in range(X):
        for b in range(Y):
                if (a + 1) * (b + 1) > K:
                                break

                for c in range(Z):
                        if (a + 1) * (b + 1) * (c + 1) > K:
                                break

                        bimi.append(A[a] + B[b] + C[c])

bimi.sort(reverse=True)

for i in range(K):
        print(bimi[i])
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
now=1
count=0
a=0
l=[1]
b=0
c=0
while a==0and count<K:
    now=A[now-1]
    count+=1
    if now in l:
        a=1
    else:
        l.append(now)
        
b=l.index(now)
c=count-b
if count==K:
    print(now)
else:
    n= ((K-b)%c)
    print(l[b+n])



### FIXED CODE ###

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

s = [True] * n #訪れているかを判定するlist
c = [1] #訪ずれた順番を記録するlist
now = 0 #現在地
while s[now]:
    s[now] = False #訪ずれた地点を記録
    now = a[now] - 1
    c.append(now+1)

start_cycle = c.index(c[-1]) #ループに入る点
loop = c[start_cycle:-1] #ループのlist
cycle = len(loop)

if k < start_cycle: #ループまで到達できないK
    print(c[k])
else:
    k -= start_cycle
    k %= cycle
    print(loop[k])
### BUGGY CODE ###

n, _ = map(int, input().split())
CST = {} # {c:[max_t, [s,t],...[,]]}
for i in range(n):
    s, t, c = map(int, input().split())
    if c in CST: CST[c] += [[s,t]]
    else: CST[c] = [t, [s,t]]
    CST[c][0] = max(CST[c][0], t)
R = [0]*200002
for c, ST in CST.items():
    mx_t = ST[0]*2+2
    TZ = [0]*mx_t
    for s,t in ST[1:]:
        TZ[2*s - 1] += 1
        TZ[2*t] -= 1
    for i in range(mx_t - 1):
        TZ[i+1] += TZ[i]
        if TZ[i+1] > 0: R[i+1] += 1
print(max(R))


### FIXED CODE ###

N, C = map(int, input().split())
STC = [[*map(int, input().split())] for _ in range(N)]
mx_t = 200002
R = [0]*mx_t
for cc in range(1, C+1):
    TZ = [0]*mx_t
    for s,t,c in STC:
        if c == cc:
            TZ[2*s - 1] += 1
            TZ[2*t] -= 1
    for i in range(mx_t - 1):
        TZ[i+1] += TZ[i]
        if TZ[i+1] > 0: R[i+1] += 1
print(max(R))
### BUGGY CODE ###

from fractions import gcd
 
mod = 10**9+7
 
n = int(input())
a = list(map(int,input().split()))
d = 1
for i in range(n):
  d *= a[i] // gcd(a[i],d)
ans = 0
for i in range(n):
  ans += d//a[i]
  ans%=mod
 
print(ans%mod)


### FIXED CODE ###

def main():
  MOD=10**9+7
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**8)
    input=sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    num1,num2,num3=0,0,0
    for i in range(n):
        if a[i]==1:
            num1+=1
        elif a[i]==2:
            num2+=1
        else:
            num3+=1
    dp=[[[-1 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
    def f(n1,n2,n3):
        if dp[n1][n2][n3]>=0:
            return dp[n1][n2][n3]
        if n1==n2==n3==0:
            return 0
        ret=1/(1-(n-n1-n2-n3)/n)
        if n1>0:
            ret+=f(n1-1,n2,n3)*(n1/n)/(1-(n-n1-n2-n3)/n)
        if n2>0:
            ret+=f(n1+1,n2-1,n3)*(n2/n)/(1-(n-n1-n2-n3)/n)
        if n3>0:
            ret+=f(n1,n2+1,n3-1)*(n3/n)/(1-(n-n1-n2-n3)/n)
        dp[n1][n2][n3]=ret
        return dp[n1][n2][n3]
    print(f(num1,num2,num3))
if __name__=="__main__":
    main()

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

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

    val = [0] * 100000000
    val[0] = X
    #val = X
    #val_new = 0
    if K % 2 == 0 :
        limit = 4
    else :
        limit = 5
    i = 0
    if abs(X) > K * D :
        if X > 0 :
            print(X - K * D)
        else :
            print(abs(X + K * D))
    elif abs(X) == K * D :
        print("0")
    elif X == 0 :
        if limit == 4 :
            print('0')
        else :
            print(abs(D))
    else :
        syo = X // D
        #print(syo)
        if syo > 1 :
            if X > 0 :
                val[0] = X - (syo-2) * D
            else :
                val[0] = X + (syo - 2) * D
            #print(val[0])
            K = K -(syo-2)
            if K % 2 == 0:
                limit = 0
            else:
                limit = 1
        for j in val :
            #print(i)
            if abs(val[i] - D) < abs(val[i] + D) :
                val[i+1] = val[i] - D
            else :
                val[i+1] = val[i] + D
            #print(val[i+1])
            if (abs(val[i+1]) == abs(val[i-1])) and i > limit :
                #print("a")
                print(abs(val[i + 1]))
                break
            i += 1
            if i == K :
                #print("b")
                print(abs(val[i]))
                break


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    val = [0] * 100000000
    val[0] = X
    #val = X
    #val_new = 0
    if K % 2 == 0 :
        limit = 4
    else :
        limit = 5
    i = 0
    if abs(X) > K * D :
        if X > 0 :
            print(X - K * D)
        else :
            print(abs(X + K * D))
    elif abs(X) == K * D :
        print("0")
    elif X == 0 :
        if limit == 4 :
            print('0')
        else :
            print(abs(D))
    else :
        syo = abs(X) // D
        #print(syo)
        if syo > 3 :
            if X > 0 :
                val[0] = X - (syo-2) * D
            else :
                val[0] = X + (syo - 2) * D
            #print(val[0])
            K = K -(syo-2)
            if K % 2 == 0:
                limit = 2
            else:
                limit = 3
        for j in val :
            #print(i)
            if abs(val[i] - D) < abs(val[i] + D) :
                val[i+1] = val[i] - D
            else :
                val[i+1] = val[i] + D
            #print(val[i+1])
            if (abs(val[i+1]) == abs(val[i-1])) and i > limit :
                #print("a")
                print(abs(val[i + 1]))
                break
            i += 1
            if i == K :
                #print("b")
                print(abs(val[i]))
                break


if __name__ == '__main__':
    main()