Lucy lives in house number X. She has a list of N house numbers in the society. Distance between houses can be determined by studying the difference between house numbers. Help her find out K closest neighbors.
Note: If two houses are equidistant and Lucy has to pick only one, the house with the smaller house number is given preference.
Example 1:
Input:
N = 5, X = 0, K = 4
a[] = {-21, 21, 4, -12, 20}, 
Output:
-21 -12 4 20
Explanation:
The closest neighbour is house
number 4. Followed by -12 and 20. -21 and 21 
are both equal distance from X=0. Therefore, 
Lucy can only pick 1. Based on the given 
condition she picks -21 as it is the smaller 
of the two. 
Example 2:
Input:
N = 6, X = 5, K = 3 
a[] = {10, 2, 14, 4, 7, 6},
Output:
4 6 7 
Your Task:  
You don't need to read input or print anything. Complete the function  Kclosest() which takes the array arr[], size of array N, X, and K as input parameters, and returns the list of numbers in sorted order.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ K ≤ N ≤ 10^{5} 
-10^{4} ≤ X, arr[i] ≤ 10^{4}

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

class Solution:
    def Kclosest(self, arr, n, x, k):
        # Your code goes here


Solutions:
import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		maxheap = []
		ans = []
		for i in range(0, n):
			diff = abs(arr[i] - x)
			heapq.heappush(maxheap, (-diff, -arr[i]))
		while len(maxheap) > k:
			heapq.heappop(maxheap)
		while len(maxheap) > 0:
			ele = heapq.heappop(maxheap)
			ans.append(ele[1] * -1)
		ans.sort()
		return ans


class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		for i in range(n):
			heapq.heappush(heap, (abs(arr[i] - x), arr[i]))
		ans = []
		while len(ans) < k:
			ans.append(heapq.heappop(heap)[1])
		ans.sort()
		return ans


class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		for num in arr:
			curDist = abs(num - x)
			curNum = num
			if len(heap) < k:
				heapq.heappush(heap, [-1 * curDist, -1 * curNum])
			else:
				topDist = -1 * heap[0][0]
				topNum = -1 * heap[0][1]
				if curDist < topDist or (curDist == topDist and curNum < topNum):
					heapq.heappop(heap)
					heapq.heappush(heap, [-1 * curDist, -1 * curNum])
		res = []
		for l in heap:
			res.append(-1 * l[1])
		res.sort()
		return res


class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		for num in arr:
			if len(heap) < k:
				heapq.heappush(heap, [-1 * abs(num - x), -1 * num])
			else:
				dist = -1 * heap[0][0]
				hno = -1 * heap[0][1]
				if abs(num - x) < dist or (abs(num - x) == dist and num < hno):
					heapq.heappop(heap)
					heapq.heappush(heap, [-1 * abs(num - x), -1 * num])
		res = []
		for l in heap:
			res.append(-1 * l[1])
		res.sort()
		return res


class Solution:

	def Kclosest(self, arr, n, x, k):
		import heapq
		pq = []
		ans = []
		for i in arr:
			heapq.heappush(pq, (abs(x - i), i))
		for i in range(k):
			(d, h) = heapq.heappop(pq)
			ans.append(h)
		ans.sort()
		return ans


class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		for i in arr:
			heap.append([abs(i - x), i])
			heapq._siftdown_max(heap, 0, len(heap) - 1)
			if len(heap) > k:
				heapq._heappop_max(heap)
		res = []
		for l in heap:
			res.append(l[1])
		res.sort()
		return res


from heapq import heapify, heappush, heappop

class Solution:

	def swapLeft(self, heap):
		leftChild = heap[1]
		root = heap[0]
		if leftChild[0] == root[0] and leftChild[1] > root[1]:
			(leftChild[1], root[1]) = (root[1], leftChild[1])

	def swapRight(self, heap):
		rightChild = heap[2]
		root = heap[0]
		if rightChild[0] == root[0] and rightChild[1] > root[1]:
			(rightChild[1], root[1]) = (root[1], rightChild[1])

	def Kclosest(self, arr, n, x, k):
		heap = []
		heapify(heap)
		for num in arr:
			heappush(heap, [-1 * abs(x - num), num])
			if len(heap) == k + 1:
				if 1 < len(heap):
					self.swapLeft(heap)
				if 2 < len(heap):
					self.swapRight(heap)
				heappop(heap)
		ans = []
		while len(heap):
			ans.append(heappop(heap)[1])
		return sorted(ans)


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		d = {}
		for item in arr:
			d[abs(item * 10 - x * 10 + 1)] = item
		heap = list(d.keys())
		heapq.heapify(heap)
		output = []
		for _ in range(k):
			output.append(d[heapq.heappop(heap)])
		return sorted(output)


from heapq import heappush, heappop

class Solution:

	def Kclosest(self, a, n, x, k):
		h = []
		for i in range(k):
			heappush(h, (-abs(a[i] - x), -a[i]))
		for i in range(k, n):
			diff = abs(a[i] - x)
			if -h[0][0] > diff:
				heappop(h)
				heappush(h, (-diff, -a[i]))
			elif -h[0][0] == diff and h[0][1] < -a[i]:
				heappop(h)
				heappush(h, (-diff, -a[i]))
		ans = []
		while h:
			ans.append(-heappop(h)[1])
		ans.sort()
		return ans


from heapq import heappush, heappop

class Solution:

	def Kclosest(self, a, n, x, k):
		h = []
		ans = []
		for i in range(n):
			heappush(h, (abs(x - a[i]), a[i]))
		while h and k:
			(dis, val) = heappop(h)
			ans.append(val)
			k -= 1
		ans.sort()
		return ans


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		h1 = []
		heapq.heapify(h1)
		for i in arr:
			heapq.heappush(h1, (abs(x - i), i))
		res = []
		while k > 0:
			res.append(heapq.heappop(h1)[1])
			k -= 1
		res.sort()
		return res


from heapq import *

class Solution:

	def Kclosest(self, arr, n, x, k):
		h = []
		for i in range(n):
			h.append((abs(x - arr[i]), arr[i]))
		heapify(h)
		res = []
		for i in range(k):
			res.append(heappop(h)[1])
		return sorted(res)


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		res = []
		for i in arr:
			heapq.heappush(heap, (-abs(x - i), -i))
			if len(heap) > k:
				heapq.heappop(heap)
		while k > 0:
			res.append(heapq._heappop_max(heap)[1] * -1)
			k -= 1
		return sorted(res)


class Solution:

	def Kclosest(self, arr, n, x, k):
		d = sorted(((abs(x - i), i) for i in arr))
		return sorted(map(lambda x: x[1], d[:k]))


from heapq import heappush, heappop

class Solution:

	def Kclosest(self, arr, n, x, k):
		h = []
		res = []
		for i in arr:
			heappush(h, (-1 * abs(x - i), -1 * i))
			if len(h) > k:
				heappop(h)
		for i in h:
			res.append(-1 * i[1])
		res.sort()
		return res


class Solution:

	def Kclosest(self, arr, n, x, k):
		from heapq import heapify, heappush, heappop
		heap = []
		for i in arr:
			heapq.heappush(heap, (-abs(x - i), -i))
			if len(heap) > k:
				heapq.heappop(heap)
		ans = []
		for ele in heap:
			ans.append(-ele[1])
		return sorted(ans)


class Solution:

	def Kclosest(self, arr, n, x, k):
		from heapq import heappush, heappop
		minheap = []
		for i in arr:
			heappush(minheap, [abs(x - i), i])
		l = []
		print
		while k > 0:
			(a, b) = heappop(minheap)
			l.append(b)
			k -= 1
		l.sort()
		return l


class Solution:

	def Kclosest(self, arr, n, x, k):
		from heapq import heappop, heappush
		l = []
		min_heap = []
		for i in arr:
			heappush(min_heap, [abs(x - i), i])
		for i in range(k):
			(a, b) = heappop(min_heap)
			l.append(b)
		l.sort()
		return l


class Solution:

	def Kclosest(self, arr, n, x, k):
		d = {}
		for i in arr:
			if i not in d.keys():
				d[i] = abs(x - i)
		l = []
		for j in list(d.keys()):
			l.append([d[j], j])
		l.sort()
		t = []
		for h in l:
			t.append(h[1])
		return sorted(t[:k])


import random

def qselect_kth_smallest(arr, k):
	if len(arr) == 0:
		return []
	pivot = random.randint(0, len(arr) - 1)
	left_sub_array = [arr[i] for i in range(0, len(arr)) if pivot != i and arr[i] < arr[pivot]]
	right_sub_array = [arr[i] for i in range(0, len(arr)) if pivot != i and arr[i] >= arr[pivot]]
	if len(left_sub_array) == k - 1:
		return arr[pivot]
	elif len(left_sub_array) > k - 1:
		return qselect_kth_smallest(left_sub_array, k)
	else:
		return qselect_kth_smallest(right_sub_array, k - len(left_sub_array) - 1)

def find(arr, x, k):
	distances = [abs(e - x) for e in arr]
	kth_smallest_element = qselect_kth_smallest(distances, k)
	out1 = [arr[idx] for idx in range(0, len(arr)) if distances[idx] < kth_smallest_element]
	out2 = [arr[idx] for idx in range(0, len(arr)) if distances[idx] == kth_smallest_element]
	out1.sort()
	out2.sort()
	out = []
	i = 0
	j = 0
	while i < len(out1) and j < len(out2) and (len(out) < k):
		if out1[i] < out2[j]:
			out.append(out1[i])
			i += 1
		else:
			out.append(out2[j])
			j += 1
	while i < len(out1) and len(out) < k:
		out.append(out1[i])
		i += 1
	while j < len(out2) and len(out) < k:
		out.append(out2[j])
		j += 1
	return out

class Solution:

	def Kclosest(self, arr, n, x, k):
		return find(arr, x, k)


from heapq import heappush, heappop

class Solution:

	def Kclosest(self, arr, n, x, k):
		pq = []
		r = []
		for i in range(n):
			diff = abs(arr[i] - x)
			heapq.heappush(pq, (-diff, -arr[i]))
			if len(pq) > k:
				heapq.heappop(pq)
		while len(pq) != 0:
			s = heapq.heappop(pq)
			r.append(-s[1])
		return sorted(r)


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		arr.sort()
		h = []
		l = []
		heapq.heapify(h)
		for i in arr:
			heapq.heappush(h, (abs(i - x), i))
		for i in range(k):
			m = heapq.heappop(h)
			l.append(m[1])
		l.sort()
		return l


import heapq

class Solution:

	def Kclosest(self, a, n, x, k):
		lst1 = []
		lst2 = []
		for i in range(n):
			y = a[i] - x
			if y <= 0:
				lst1.append(-1 * y)
			else:
				lst2.append(y)
		heapq.heapify(lst1)
		heapq.heapify(lst2)
		res = []
		while k > 0 and lst1 and lst2:
			if lst1[0] <= lst2[0]:
				y = -1 * lst1[0]
				res.append(y + x)
				heapq.heappop(lst1)
			else:
				y = lst2[0]
				res.append(y + x)
				heapq.heappop(lst2)
			k -= 1
		while k > 0 and lst1:
			y = -1 * lst1[0]
			res.append(y + x)
			heapq.heappop(lst1)
			k -= 1
		while k > 0 and lst2:
			y = lst2[0]
			res.append(y + x)
			heapq.heappop(lst2)
			k -= 1
		return sorted(res)


class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		import heapq
		for i in range(k):
			heap.append((-1 * abs(arr[i] - x), -1 * arr[i]))
		heapq.heapify(heap)
		for i in range(k, n):
			dist = heap[0][0] * -1
			hno = heap[0][1] * -1
			if abs(arr[i] - x) < dist or (abs(arr[i] - x) == dist and arr[i] < hno):
				heapq.heappop(heap)
				heapq.heappush(heap, (-1 * abs(arr[i] - x), -1 * arr[i]))
		ans = []
		for i in range(k):
			ans.append(heap[i][1] * -1)
		ans.sort()
		return ans


from heapq import heappush, heappop

class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		for e in arr:
			heappush(heap, [abs(e - x), e])
		ans = []
		for i in range(k):
			ans.append(heappop(heap)[1])
		return sorted(ans)


class Solution:

	def Kclosest(self, arr, n, x, k):
		dis = []
		for e in arr:
			dis.append([abs(x - e), e])
		dis.sort()
		ans = []
		for i in range(k):
			ans.append(dis[i][1])
		return sorted(ans)


from heapq import heappop, heappush, heapify

class Solution:

	def Kclosest(self, arr, n, x, k):
		b = []
		heapify(b)
		s = {}
		for i in arr:
			d = abs(i - x)
			if d not in s:
				s[d] = [i]
				heappush(b, d)
			else:
				s[d].append(i)
		c = []
		for i in range(k):
			a = heappop(b)
			s[a].sort()
			f = 0
			for m in s[a]:
				c.append(m)
				if len(c) == k:
					f = 1
					break
			if f == 1:
				break
		c.sort()
		return c


import heapq
import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		res = []
		for i in arr:
			heapq.heappush(heap, (-abs(x - i), -i))
			if len(heap) > k:
				heapq.heappop(heap)
		while k > 0:
			res.append(heapq._heappop_max(heap)[1] * -1)
			k -= 1
		return sorted(res)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input().strip().split()
		n = int(line[0])
		x = int(line[1])
		k = int(line[2])
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		result = obj.Kclosest(arr, n, x, k)
		for i in result:
			print(i, end=' ')
		print()


import heapq
from heapq import nlargest, nsmallest
import math

class Solution:

	def Kclosest(self, arr, n, x, k):
		hm = {}
		for i in range(n):
			tmp = abs(x - arr[i])
			if arr[i] not in hm:
				hm[arr[i]] = tmp
		heap = []
		for (key, value) in hm.items():
			heap.append((value, key))
		largest = nsmallest(k, heap)
		ans = []
		for i in largest:
			(a, b) = i
			ans.append(b)
		ans.sort()
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input().strip().split()
		n = int(line[0])
		x = int(line[1])
		k = int(line[2])
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		result = obj.Kclosest(arr, n, x, k)
		for i in result:
			print(i, end=' ')
		print()


import heapq
import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		(maxHeap, result) = ([], [])
		for element in arr:
			maxHeap.append((abs(element - x), element))
		heapq.heapify(maxHeap)
		for i in range(k):
			result.append(heapq.heappop(maxHeap)[1])
		return sorted(result)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		line = input().strip().split()
		n = int(line[0])
		x = int(line[1])
		k = int(line[2])
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		result = obj.Kclosest(arr, n, x, k)
		for i in result:
			print(i, end=' ')
		print()


from heapq import heappop, heappush

class Solution:

	def Kclosest(self, arr, n, x, k):
		minHeap = []
		for num in arr:
			absDifference = abs(num - x)
			heappush(minHeap, (absDifference, num))
		ans = []
		while k > 0:
			ans.append(heappop(minHeap)[1])
			k -= 1
		return sorted(ans)


import heapq as hq

class Solution:

	def Kclosest(self, arr, n, x, k):
		temp = []
		hq.heapify(temp)
		for i in arr:
			hq.heappush(temp, (-abs(x - i), -i))
			if len(temp) > k:
				hq.heappop(temp)
		ans = []
		while len(temp):
			ans.append(hq._heappop_max(temp)[1] * -1)
		return sorted(ans)


class Solution:

	def Kclosest(self, arr, n, x, k):
		arr.sort()
		a = [[-abs(x - i), i] for i in arr]
		res = a[:k]
		heapq.heapify(res)
		for i in range(k, n):
			if -a[i][0] < -res[0][0]:
				heapq.heappop(res)
				heapq.heappush(res, a[i])
		res = [val[1] for val in res]
		res = sorted(res)
		return res


class Solution:

	def Kclosest(self, arr, n, x, k):
		a = []
		for i in range(n):
			dist = abs(arr[i] - x)
			a.append([dist, arr[i]])
		a.sort(key=lambda x: (x[0], x[1]))
		ans = []
		for i in range(k):
			ans.append(a[i][1])
		ans.sort()
		return ans


import heapq
from collections import defaultdict

class Solution:

	def Kclosest(self, arr, n, x, k):
		heapq.heapify(arr)
		mp = defaultdict(lambda : [])
		while len(arr) > 0:
			d = heapq.heappop(arr)
			c = abs(d - x)
			mp[c].append(d)
		ans = []
		i = 0
		l = list(mp.keys())
		l.sort()
		c = 0
		for i in range(len(l)):
			if c < k:
				l1 = mp[l[i]]
				ans = ans + l1
			c += len(mp[l[i]])
		ans.sort()
		return ans[:k]


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		ak = []
		ans = []
		for i in range(n):
			heapq.heappush(ak, (-abs(x - arr[i]), -arr[i]))
			if len(ak) > k:
				heapq.heappop(ak)
		while k > 0:
			ans.append(heapq._heappop_max(ak)[1] * -1)
			k -= 1
		return sorted(ans)


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		a = arr
		n = len(a)
		b = []
		c = []
		for i in range(n):
			res = abs(x - a[i])
			heapq.heappush(b, [res, arr[i]])
		for i in range(k):
			m1 = heapq.heappop(b)
			c.append(m1[1])
		c.sort()
		return c


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		arr.sort()
		for el in arr:
			if len(heap) < k:
				heapq.heappush(heap, (-abs(el - x), el))
			elif abs(el - x) < -heap[0][0]:
				heapq.heappop(heap)
				heapq.heappush(heap, (-abs(el - x), el))
		ans = []
		for el in heap:
			ans.append(el[1])
		ans.sort()
		return ans


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		heapq.heapify(heap)
		for i in arr:
			heapq.heappush(heap, (-abs(x - i), -i))
			if len(heap) > k:
				heapq.heappop(heap)
		res = []
		for item in heap:
			res.append(item[1] * -1)
		return sorted(res)
		return []


class Solution:

	def Kclosest(self, arr, n, x, k):
		maxheap = []
		ans = []
		for i in arr:
			heapq.heappush(maxheap, (-abs(x - i), -i))
			if len(maxheap) > k:
				heapq.heappop(maxheap)
		while k > 0:
			ans.append(heapq._heappop_max(maxheap)[1] * -1)
			k -= 1
		ans.sort()
		return ans


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		max_heap = []
		for num in arr:
			heapq.heappush(max_heap, (abs(num - x) * -1, num * -1))
			if len(max_heap) > k:
				heapq.heappop(max_heap)
		res = []
		while max_heap:
			res.append(heapq.heappop(max_heap)[1] * -1)
		return sorted(res)


class Solution:

	def Kclosest(self, arr, n, x, k):
		pair = []
		arr.sort()
		for y in arr:
			pair.append([abs(y - x), y])
		pair.sort()
		res = []
		for i in range(k):
			res.append(pair[i][1])
		res.sort()
		return res


from collections import Counter
import heapq as h

class Solution:

	def Kclosest(self, a, n, x, k):
		s = {}
		for i in range(n):
			try:
				h.heappush(s[abs(x - a[i])], a[i])
			except:
				s[abs(x - a[i])] = [a[i]]
		p = list(s.keys())
		h.heapify(p)
		x = []
		t = 1
		while p:
			i = h.heappop(p)
			while s[i]:
				x.append(h.heappop(s[i]))
				t += 1
				if t > k:
					x.sort()
					return x
		return x


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		maxHeap = []
		for i in range(n):
			dis = abs(x - arr[i])
			if i < k:
				heapq.heappush(maxHeap, (-dis, -arr[i]))
			else:
				pair = maxHeap[0]
				(dist, val) = (-pair[0], -pair[1])
				if dis < dist:
					heapq.heapreplace(maxHeap, (-dis, -arr[i]))
				elif dis == dist:
					if arr[i] < val:
						heapq.heapreplace(maxHeap, (-dis, -arr[i]))
		ans = []
		while maxHeap:
			pair = heapq.heappop(maxHeap)
			(dist, val) = (-pair[0], -pair[1])
			ans.append(val)
		ans.sort()
		return ans


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		for i in range(k):
			heapq.heappush(heap, (-abs(arr[i] - x), -arr[i]))
		for i in range(k, n):
			dif = abs(arr[i] - x)
			heapq.heappushpop(heap, (-dif, -arr[i]))
		op = []
		for i in range(k):
			(key, value) = heapq.heappop(heap)
			op.append(-value)
		return sorted(op)


class Solution:

	def Kclosest(self, arr, n, x, k):
		max_heap = [(-1 * abs(x - arr[i]), -1 * arr[i]) for i in range(k)]
		heapq.heapify(max_heap)
		for i in range(k, n):
			dist = -1 * max_heap[0][0]
			hno = -1 * max_heap[0][1]
			if abs(arr[i] - x) < dist or (abs(arr[i] - x) == dist and arr[i] < hno):
				heapq.heappop(max_heap)
				heapq.heappush(max_heap, (-1 * abs(x - arr[i]), -1 * arr[i]))
		ret = [-1 * x[1] for x in max_heap]
		ret.sort()
		return ret


class Solution:

	def Kclosest(self, arr, n, x, k):
		lst = []
		for i in arr:
			diff = abs(x - i)
			lst.append((diff, i))
		lst.sort()
		ans = []
		for i in range(k):
			ans.append(lst[i][1])
		ans.sort()
		return ans


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		res = []
		i = 0
		while i < n:
			heapq.heappush(heap, (abs(x - arr[i]), arr[i]))
			i += 1
		i = 0
		while i < k:
			res.append(heapq.heappop(heap)[1])
			i += 1
		res.sort()
		return res


class Solution:

	def Kclosest(self, a, n, x, k):
		ans = []
		b = a.copy()
		for i in range(n):
			b[i] = a[i] - x
		for i in range(n):
			s = 1
			if b[i] < 0:
				b[i] = -b[i]
				s = -1
			ans.append([b[i], a[i]])
		ans.sort()
		finalans = []
		finalans.append(ans[0][1])
		i = 1
		j = 0
		while j < k - 1 and i < n:
			finalans.append(ans[i][1])
			j += 1
			i += 1
		finalans.sort()
		return finalans


class Solution:

	def Kclosest(self, arr, n, x, k):
		h = [(-1 * abs(arr[i] - x), -1 * arr[i]) for i in range(k)]
		heapq.heapify(h)
		for i in range(k, n):
			distance = -1 * h[0][0]
			element = -1 * h[0][1]
			if abs(arr[i] - x) < distance or (abs(arr[i] - x) == distance and arr[i] < element):
				heapq.heappop(h)
				heapq.heappush(h, (-1 * abs(x - arr[i]), -1 * arr[i]))
		ans = [-1 * x[1] for x in h]
		ans.sort()
		return ans


from heapq import heappush, heappop, heapify

class Solution:

	def Kclosest(self, arr, n, x, k):
		temp = []
		for i in range(k):
			temp.append([-abs(arr[i] - x), -arr[i]])
		heapify(temp)
		for i in range(k, n):
			if temp[0][0] < -abs(arr[i] - x):
				heappop(temp)
				heappush(temp, [-abs(arr[i] - x), -arr[i]])
			elif temp[0][0] == -abs(arr[i] - x) and temp[0][1] < -arr[i]:
				heappop(temp)
				heappush(temp, [-abs(arr[i] - x), -arr[i]])
		ans = [-temp[i][1] for i in range(len(temp))]
		ans.sort()
		return ans


class Solution:

	def Kclosest(self, arr, n, x, k):
		d = {}
		ans = []
		arr.sort()
		dis = [0] * n
		for i in range(len(arr)):
			dis[i] = abs(arr[i] - x)
			d[arr[i]] = dis[i]
		if x == 0:
			d1 = sorted(d.items(), key=lambda x: x[0])
		else:
			d1 = sorted(d.items(), key=lambda x: x[1])
		for i in range(k):
			ans.append(d1[i][0])
		ans.sort()
		return ans


class Solution:

	def Kclosest(self, arr, n, x, k):
		a = []
		for i in arr:
			a.append([abs(i - x), i])
		a.sort()
		b = [i[1] for i in a[:k]]
		return sorted(b)


class Solution:

	def Kclosest(self, arr, n, x, k):
		l = []
		for i in range(len(arr)):
			l.append((arr[i], abs(arr[i] - x)))
		l = sorted(l, key=lambda item: item[0])
		l = sorted(l, key=lambda item: item[1])
		ans = []
		for (i, j) in l:
			ans.append(i)
		return sorted(ans[:k])


class Solution:

	def Kclosest(self, arr, n, x, k):
		from collections import defaultdict
		from bisect import bisect_left
		di = defaultdict(list)
		for i in arr:
			ind = bisect_left(di[abs(x - i)], i)
			di[abs(x - i)].insert(ind, i)
		ref = list()
		lis = sorted(list(di.keys()))
		for i in lis:
			ref += di[i]
		return sorted(ref[:k])


class Solution:

	def Kclosest(self, arr, n, x, k):
		from collections import defaultdict
		di = defaultdict(list)
		for i in arr:
			di[abs(x - i)].append(i)
		lis = sorted(list(di.keys()))
		for i in di:
			di[i] = sorted(di[i])
		ref = list()
		for i in lis:
			ref += di[i]
		ans = ref[:k]
		return sorted(ans)


class Solution:

	def Kclosest(self, arr, n, x, k):
		dic = {}
		for i in range(n):
			dic[arr[i]] = abs(arr[i] - x)
		d = sorted(dic, key=dic.get)
		a = d[:k - 1]
		if len(dic) > k and dic[d[k - 1]] == dic[d[k]]:
			if d[k - 1] < d[k]:
				a.append(d[k - 1])
			else:
				a.append(d[k])
		else:
			a.append(d[k - 1])
		return sorted(a)


class Solution:

	def Kclosest(self, arr, n, x, k):
		arrCopy = {}
		for num in arr:
			arrCopy[num] = num
		for key in arrCopy.keys():
			arrCopy[key] -= x
		for key in arrCopy.keys():
			arrCopy[key] = abs(arrCopy[key])
		arrCopy = sorted(arrCopy.items(), key=lambda x: x[0])
		arrCopy = sorted(arrCopy, key=lambda x: x[1])
		ret = []
		for i in range(k):
			ret.append(arrCopy[i][0])
		return sorted(ret)


class Solution:

	def Kclosest(self, arr, n, x, k):
		d = {}
		for i in arr:
			diff = abs(x - i)
			d[i] = diff
		l = sorted(d.items(), key=lambda x: (x[1], x[0]))
		c = 0
		ans = []
		for i in l:
			if c == k:
				break
			ans.append(i[0])
			c = c + 1
		ans.sort()
		return ans


class Solution:

	def Kclosest(self, arr, n, x, k):
		dt = {}
		for i in arr:
			dist = abs(i - x)
			try:
				dt[dist].append(i)
			except KeyError:
				dt[dist] = [i]
		ans = []
		for (key, value) in sorted(dt.items(), key=lambda x: x[0]):
			if len(value) > 1:
				value.sort()
				i = 0
				while i < len(value) and len(ans) < k:
					ans.append(value[i])
					i += 1
			else:
				ans.append(value[0])
			if len(ans) == k:
				break
		return sorted(ans)


class Solution:

	def Kclosest(self, l, n, x, k):
		t = []
		for i in l:
			t.append([abs(x - i), i])
		t.sort()
		ans = []
		for i in range(k):
			ans.append(t[i][1])
		ans.sort()
		return ans


class Solution:

	def Kclosest(self, arr, n, x, k):
		closest = []
		for i in arr:
			m = abs(x - i)
			closest.append([m, i])
		closest.sort()
		answer = [i[1] for i in closest][:k]
		answer.sort()
		return answer


class Solution:

	def Kclosest(self, arr, n, x, k):
		dist = {}
		arr.sort()
		for (index, el) in enumerate(arr):
			temp = abs(x - el)
			if temp in dist:
				dist[temp].append(el)
			else:
				dist[temp] = [el]
		x = sorted(dist.items(), key=lambda x: x[0])
		res = []
		for el in x:
			for i in el[1]:
				if k:
					res.append(i)
					k -= 1
				else:
					break
		res.sort()
		return res


class Solution:

	def Kclosest(self, arr, n, x, k):
		dicti = {}
		res = []
		ar = []
		for e in arr:
			dis = abs(x - e)
			ar.append((dis, e))
		ar.sort()
		i = 0
		while i < k:
			res.append(ar[i][1])
			i += 1
		res.sort()
		return res


class Solution:

	def Kclosest(self, arr, n, x, k):
		diff = [(abs(i - x), i) for i in arr]
		heapq.heapify(diff)
		return sorted([i for (d, i) in heapq.nsmallest(k, diff)])


import sys

class Solution:

	def Kclosest(self, arr, n, x, k):
		arr.append(x)
		arr.sort()
		find = arr.index(x) + 1
		bind = find - 2
		ans = []
		while not k == 0:
			bdiff = abs(x - arr[bind]) if bind >= 0 else sys.maxsize
			fdiff = abs(x - arr[find]) if find <= n else sys.maxsize
			if fdiff < bdiff:
				ans.append(arr[find])
				k -= 1
				find += 1
				continue
			else:
				ans.append(arr[bind])
				k -= 1
				bind -= 1
				continue
		ans.sort()
		return ans


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		li = []
		for i in arr:
			li.append((abs(i - x), i))
		heapq.heapify(li)
		ans = []
		for i in range(k):
			ans.append(heapq.heappop(li)[1])
		return sorted(ans)


class Solution:

	def Kclosest(self, arr, n, x, k):
		arr.sort()
		(low, high) = (0, n - k)
		while low < high:
			mid = low + (high - low) // 2
			if x - arr[mid] > arr[mid + k] - x:
				low = mid + 1
			else:
				high = mid
		return arr[low:low + k]


class Solution:

	def Kclosest(self, arr, n, x, k):
		mheap = [(-1 * abs(x - arr[i]), -1 * arr[i]) for i in range(k)]
		heapq.heapify(mheap)
		for i in range(k, n):
			dist = -1 * mheap[0][0]
			nub = -1 * mheap[0][1]
			if abs(arr[i] - x) < dist or (abs(arr[i] - x) == dist and arr[i] < nub):
				heapq.heappop(mheap)
				heapq.heappush(mheap, (-1 * abs(x - arr[i]), -1 * arr[i]))
		res = [-1 * x[1] for x in mheap]
		res.sort()
		return res


import heapq

class Neigh:

	def __init__(self, val, x):
		self.val = val
		self.dist = abs(val - x)

	def __lt__(self, other):
		return self.dist == other.dist and self.val < other.val or self.dist < other.dist

class Solution:

	def Kclosest(self, arr, n, x, k):
		heap = []
		heapq.heapify(heap)
		for el in arr:
			heapq.heappush(heap, Neigh(el, x))
		res = []
		for _ in range(k):
			res.append(heapq.heappop(heap).val)
		return sorted(res)


import heapq

class Solution:

	def Kclosest(self, arr, n, x, k):
		diff = []
		for i in range(n):
			diff.append([abs(arr[i] - x), arr[i]])
		diff.sort()
		res = []
		for i in range(k):
			res.append(diff[i][1])
		res.sort()
		return res


class Solution:

	def findcross(self, arr, low, high, x):
		if arr[low] > x:
			return low
		if arr[high] <= x:
			return high
		mid = (low + high) // 2
		if arr[mid] <= x and arr[mid + 1] > x:
			return mid
		if arr[mid] < x:
			return self.findcross(arr, mid + 1, high, x)
		return self.findcross(arr, low, mid - 1, x)

	def Kclosest(self, arr, n, x, k):
		arr.sort()
		l = self.findcross(arr, 0, n - 1, x)
		r = l + 1
		res = []
		count = 0
		while l >= 0 and r < n and (count < k):
			if x - arr[l] == arr[r] - x:
				res.append(arr[l])
				l -= 1
			elif x - arr[l] < arr[r] - x:
				res.append(arr[l])
				l -= 1
			else:
				res.append(arr[r])
				r += 1
			count += 1
		while l >= 0 and count < k:
			res.append(arr[l])
			l -= 1
			count += 1
		while r < n and count < k:
			res.append(arr[r])
			r += 1
			count += 1
		res.sort()
		return res