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 a_{i} either with a_{i} + x or with a_{i} - 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. $\prod_{i = 1}^{n} a_{i}$) 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 ≤ 10^9) — 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 a_1, a_2, ..., a_{n} ($|a_{i}|\leq 10^{9}$) — the elements of the array found by Maxim.


-----Output-----

Print n integers b_1, b_2, ..., b_{n} in the only line — the array elements after applying no more than k operations to the array. In particular, $a_{i} \equiv b_{i} \operatorname{mod} x$ 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

Difficulty: HARD
Tags: Greedy algorithms

Data structures

Mathematics

Constructive algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
def main():
	from heapq import heapify, heappop, heappushpop, heappush
	(n, k, x) = map(int, input().split())
	(l, sign, h) = (list(map(int, input().split())), [False] * n, [])
	helper = lambda : print(' '.join((str(-a if s else a) for (a, s) in zip(l, sign))))
	for (i, a) in enumerate(l):
		if a < 0:
			sign[i] = True
			h.append((-a, i))
		else:
			h.append((a, i))
	heapify(h)
	(a, i) = heappop(h)
	if 1 - sum(sign) % 2:
		j = min(a // x + (1 if a % x else 0), k)
		a -= j * x
		if a > 0:
			l[i] = a
			return helper()
		k -= j
		a = -a
		sign[i] ^= True
	for _ in range(k):
		(a, i) = heappushpop(h, (a, i))
		a += x
	l[i] = a
	for (a, i) in h:
		l[i] = a
	helper()

def __starting_point():
	main()
__starting_point()


import heapq
s = input().split()
n = int(s[0])
k = int(s[1])
x = int(s[2])
neg = 0
zeroes = 0
numbers = list(map(int, input().split()))
num = []
for i in numbers:
	if i < 0:
		neg += 1
	elif i == 0:
		zeroes += 1
for (i, x1) in enumerate(numbers):
	num.append([abs(x1), i])
heapq.heapify(num)
temp = []
steps = 0
if neg % 2 == 0:
	temp = heapq.heappop(num)
	if numbers[temp[1]] < 0:
		steps = min(abs(numbers[temp[1]]) // x + 1, k)
		k -= steps
		numbers[temp[1]] += steps * x
		heapq.heappush(num, [abs(numbers[temp[1]]), temp[1]])
	else:
		steps = min(abs(numbers[temp[1]]) // x + 1, k)
		k -= steps
		numbers[temp[1]] -= steps * x
		heapq.heappush(num, [abs(numbers[temp[1]]), temp[1]])
while k > 0:
	temp = heapq.heappop(num)
	if numbers[temp[1]] < 0:
		numbers[temp[1]] -= x
		heapq.heappush(num, [abs(numbers[temp[1]]), temp[1]])
	else:
		numbers[temp[1]] += x
		heapq.heappush(num, [abs(numbers[temp[1]]), temp[1]])
	k -= 1
for i in numbers:
	print(i, end=' ')


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def calc(n):
	if n >= 0:
		return 1
	return -1
(n, k, x) = map(int, input().split())
l = list(map(int, input().split()))
eq = 0
for i in l:
	if i < 0:
		eq += 1
e = [[abs(l[i]), i, calc(l[i])] for i in range(n)]
e.sort()
if eq % 2 == 0:
	k1 = int(math.ceil(e[0][0] / x))
	k1 = min(k, k1)
	e[0][0] -= k1 * x
	if e[0][0] <= 0:
		e[0][2] *= -1
	e[0][0] = abs(e[0][0])
	k -= k1
heapq.heapify(e)
while k > 0:
	w = heapq.heappop(e)
	w[0] += x
	heapq.heappush(e, w)
	k -= 1
ans = [0] * n
for i in e:
	(a, b, c) = i
	ans[b] = a * c
print(*ans)


import heapq
(n, k, v) = map(int, input().split())
num = list(map(int, input().split()))
sign = len([x for x in num if x < 0])
(minx, mini) = min([[abs(x), i] for (i, x) in enumerate(num)])
if sign % 2 == 0:
	if num[mini] < 0:
		c = min(minx // v + 1, k)
		k -= c
		num[mini] += v * c
	elif num[mini] >= 0:
		c = min(minx // v + 1, k)
		k -= c
		num[mini] -= v * c
heap = []
heapq.heapify(heap)
for (i, x) in enumerate(num):
	heapq.heappush(heap, [abs(x), i])
while k:
	(absx, curi) = heapq.heappop(heap)
	if num[curi] >= 0:
		num[curi] += v
	else:
		num[curi] -= v
	heapq.heappush(heap, [abs(num[curi]), curi])
	k -= 1
print(' '.join([str(x) for x in num]))


import heapq
inp = list(map(int, input().split()))
n = inp[0]
k = inp[1]
x = inp[2]
a = [int(i) for i in input().strip().split(' ')]
isPositive = True
nodes = [[abs(val), val, index] for (index, val) in enumerate(a)]
for el in a:
	if el < 0:
		isPositive = not isPositive
heapq.heapify(nodes)
for i in range(k):
	minNode = nodes[0]
	val = minNode[1]
	isCurPositive = val >= 0
	newVal = val
	if isPositive == isCurPositive:
		newVal -= x
	else:
		newVal += x
	minNode[1] = newVal
	if val >= 0 > newVal or val < 0 <= newVal:
		isPositive = not isPositive
	heapq.heapreplace(nodes, [abs(newVal), newVal, minNode[2]])
result = [None] * n
for node in nodes:
	result[node[2]] = str(node[1])
print(' '.join(result))


import heapq as hq
from math import ceil
(n, k, x) = [int(i) for i in input().strip().split(' ')]
arr = [int(i) for i in input().strip().split(' ')]
is_neg = False
for i in arr:
	if i < 0:
		is_neg = True if is_neg == False else False
narr = [[abs(i), pos, i < 0] for (pos, i) in enumerate(arr)]
hq.heapify(narr)
if is_neg:
	while k > 0:
		hq.heapreplace(narr, [narr[0][0] + x, narr[0][1], narr[0][2]])
		k -= 1
else:
	minode = hq.heappop(narr)
	mi = minode[0]
	kswitch = ceil(mi / x)
	if kswitch > k:
		kswitch = k
	else:
		minode[2] = False if minode[2] == True else True
	k -= kswitch
	hq.heappush(narr, [abs(mi - kswitch * x), minode[1], minode[2]])
	while k > 0:
		hq.heapreplace(narr, [narr[0][0] + x, narr[0][1], narr[0][2]])
		k -= 1
narr = sorted(narr, key=lambda x: x[1])
arr = [str(i[0] * (-1 if i[2] else 1)) for i in narr]
print(' '.join(arr))


f = lambda : map(int, input().split())
from heapq import *
(n, k, x) = f()
(t, h, p) = (0, [], list(f()))
for i in range(n):
	t ^= p[i] < 0
	heappush(h, (abs(p[i]), i))
for j in range(k):
	i = heappop(h)[1]
	d = p[i] < 0
	if not t:
		(d, t) = (1 - d, -x <= p[i] < x)
	if d:
		p[i] -= x
	else:
		p[i] += x
	heappush(h, (abs(p[i]), i))
for q in p:
	print(q)


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


import heapq
(n, k, x) = [int(val) for val in input().split()]
a = [int(val) for val in input().split()]
data = [(val, 1, i) if val >= 0 else (-1 * val, -1, i) for (i, val) in enumerate(a)]
heapq.heapify(data)
sign = sum([1 if s == -1 else 0 for (_, s, _) in data])
if sign % 2 == 1:
	for i in range(k):
		e = heapq.heappop(data)
		heapq.heappush(data, (e[0] + x, e[1], e[2]))
else:
	e = heapq.heappop(data)
	if e[0] < k * x:
		s = e[0] // x + 1
		k -= s
		heapq.heappush(data, (s * x - e[0], -1 * e[1], e[2]))
		for i in range(k):
			e = heapq.heappop(data)
			heapq.heappush(data, (e[0] + x, e[1], e[2]))
	else:
		heapq.heappush(data, (e[0] - k * x, e[1], e[2]))
output = [0] * n
for (val, s, i) in data:
	output[i] = s * val
print(' '.join([str(val) for val in output]))


import heapq
(n, k, X) = list(map(int, input().split()))
a = list(map(int, input().split()))
Q = []
sit = 0
for (i, x) in enumerate(a):
	if x < 0:
		sit += 1
	heapq.heappush(Q, (abs(x), x, i))
sit = sit % 2
while k > 0:
	(val, x, i) = heapq.heappop(Q)
	change = None
	if x < 0:
		if sit == 1:
			change = x - X
		else:
			change = x + X
	elif sit == 1:
		change = x + X
	else:
		change = x - X
	if x * change < 0 or (x < 0 and change == 0) or (x == 0 and change < 0):
		sit = (sit + 1) % 2
	heapq.heappush(Q, (abs(change), change, i))
	k -= 1
ans = [0] * n
for (val, x, i) in Q:
	ans[i] = str(x)
print(' '.join(ans))