Recently Maxim has found an array of n integers, needed by no one. He immediately come up with idea of changing it: he invented positive integer x and decided to add or subtract it from arbitrary array elements. Formally, by applying single operation Maxim chooses integer i (1 ≤ i ≤ n) and replaces the i-th element of array ai either with ai + x or with ai - x. Please note that the operation may be applied more than once to the same position.

Maxim is a curious minimalis, thus he wants to know what is the minimum value that the product of all array elements (i.e. <image>) can reach, if Maxim would apply no more than k operations to it. Please help him in that.

Input

The first line of the input contains three integers n, k and x (1 ≤ n, k ≤ 200 000, 1 ≤ x ≤ 109) — the number of elements in the array, the maximum number of operations and the number invented by Maxim, respectively.

The second line contains n integers a1, a2, ..., an (<image>) — the elements of the array found by Maxim.

Output

Print n integers b1, b2, ..., bn in the only line — the array elements after applying no more than k operations to the array. In particular, <image> should stay true for every 1 ≤ i ≤ n, but the product of all array elements should be minimum possible.

If there are multiple answers, print any of them.

Examples

Input

5 3 1
5 4 3 5 2


Output

5 4 3 5 -1 


Input

5 3 1
5 4 3 5 5


Output

5 4 0 5 5 


Input

5 3 1
5 4 4 5 5


Output

5 1 4 5 5 


Input

3 2 7
5 4 2


Output

5 11 -5 
__author__ = 'Think'
def respond():
	if len(arr)>0:
		if not arr[0][2]:
			print(-arr[0][0], end="")
		else:
			print(arr[0][0], end="")
		for i in arr[1:]:
			if i[2]:
				print(" "+str(i[0]), end="")
			else:
				print(" "+str(-i[0]), end="")
n, k, x=[int(i) for i in input().split()]
data=[int(i) for i in input().split()]
arr=[]
parity=0
for i in range(n):
	if data[i]<0:
		parity+=1
	arr.append([abs(data[i]), i, data[i]>=0])
ordered=sorted(arr, key=lambda n:abs(n[0]))

if ordered[0][0]>=k*x and (parity%2)==0:
	arr[ordered[0][1]][0]-=k*x
	respond()
else:
	start=0
	if (parity%2)==0:
		start=1
		c=ordered[0][0]
		ordered[0][0]=(x*((c//x)+1))-c
		k-=(c//x+1)
		arr[ordered[0][1]][2]=(not arr[ordered[0][1]][2])
	if k>0:
		total=0
		prev=0
		broken=False
		for m in range(len(ordered)):
			a=ordered[m][0]//x
			if a==prev:
				total+=a
				continue
			prev=a
			if m*a-total<k:
				total+=a
				continue
			else:
				broken=True
				break
		if not broken:
			m+=1
		base=(k+total)//m
		k-=(m*base-total)
		increm=sorted(ordered[:m], key=lambda n:(n[0]%x))
		for i in increm:
			pos=i[1]
			if k>0:
				arr[pos][0]=(base+1)*x+(arr[pos][0]%x)
				k-=1
			else:
				arr[pos][0]=base*x+(arr[pos][0]%x)
		respond()
	else:
		respond()



